[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 飛天 閱讀(3033) 評論(1) 編輯 收藏 引用 所屬分類: ACM

