飛天

快乐的生活......

 

[ACM 1015] 组合数算法

简单的事情
Time Limit:1000MS  Memory Limit:32768K

Description:

数学天才fans曾经说过一句话:组合数的计算是一件非常简单的事情。组合数的计算真的是一件非常简单的事情吗?请你自己去尝试一下吧!

Input:

输入中的一些整数对n,m(m≤n≤20)

Output:

输出其组合数。

Sample Input:

5 2
18 13

Sample Output:

10
8568
#include <cstdlib>
#include 
<iostream>
#include 
<string>
#include 
<vector>

using namespace std;

static char * num;
static int m,n;
static int sum=0;
             
void dfs(string subtree,int level)
{
     
   
int i=0;
   
if(level==n)
   
{
       
//cout<<subtree<<endl;
       sum++;
       
return;        
   }

   
if(subtree.size()==0) i=0;
   
else
   
{
   
for(i=0;i<m;i++)
      
if(subtree[subtree.size()-1]==num[i])
             
break;
   i
++;
   
   }

   
for(;i<m;i++)
   
{
      dfs(subtree
+num[i],level+1);            
   }

         
}


int main(int argc, char *argv[])
{
    
while(scanf("%d%d",&m,&n)!=EOF)
    
{
        
if(m<=20)
           
if(n<=m) 
           
{
              sum
=0;
              num
=new char[m];
                
for(int i=0;i<m;++i)
                  num[i]
=i+'1';
                dfs(
"",0);   
                cout
<<sum<<endl;      
                delete num;
                    }
           
    }

         
    
//system("PAUSE");
    return 0;
}

posted on 2008-01-26 14:39 飛天 阅读(2980) 评论(1)  编辑 收藏 引用 所属分类: ACM

评论

# re: [ACM 1015] 组合数算法 2009-12-27 10:48 wcdj

if(n<=m)
...
题目不是要求m<=n吗?

yangjia41@126.com
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

Blogs

搜索

最新评论

阅读排行榜

评论排行榜