把这个题AC了
你那个问题还是问题吗
http://acm.hit.
整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。
Input
每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
Output
对于每组输入,请输出六行。
第一行: 将n划分成若干正整数之和的划分数。
第二行: 将n划分成k个正整数之和的划分数。
第三行: 将n划分成最大数不超过k的划分数。
第四行: 将n划分成若干奇正整数之和的划分数。
第五行: 将n划分成若干不同整数之和的划分数。
第六行: 打印一个空行。
Sample Input
5 2Sample Output
7
2
3
3
3Hint:将5划分成若干正整数之和的划分为: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
将5划分成2个正整数之和的划分为: 3+2, 4+1
将5划分成最大数不超过2的划分为: 1+1+1+1+1, 1+1+1+2, 1+2+2
将5划分成若干奇正整数之和的划分为: 5, 1+1+3, 1+1+1+1+1
将5划分成若干不同整数之和的划分为: 5, 1+4, 2+3
程序代码:
#include <stdio.h>
#include <string.h>
int answer[7];
bool foot[50];
int q(int n,int m)
{
if((n<1)||(m<1) )return 0;
if(n==1||m==1) return 1;
if(n<m) return q(n,n);
if(n==m)return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
void dfs2(int n,int k,int depth,int front)
{
if(depth > k)return ;
if(0 == n)
{
if(depth == k)answer[2]++;
return ;
}
int i;
for(i = n;i;i--)
{
if(i<=front)
{
int temp = front;
front = i;
dfs2(n-i,k,depth+1,front);
front = temp;
}
}
}
void dfs4(int n,int k,int front)
{
if(0 == n)
{
answer[4]++;
return ;
}
int i;
for(i = n;i;i--)
{
if((i & 0x01) && i<=front)
{
int temp = front;
front = i;
dfs4(n-i,k,front);
front = temp;
}
}
}
void dfs5(int n,int k,int front)
{
if(0 == n)
{
answer[5]++;
return ;
}
int i;
for(i = n;i;i--)
{
if(!foot[i] && i<=front)
{
foot[i] = true;
int temp = front;
front = i;
dfs5(n-i,k,front);
front = temp;
foot[i] = false;
}
}
}
int main()
{
int n,k;
while(EOF != scanf("%d%d",&n,&k))
{
memset(answer,0,sizeof(answer));
memset(foot,0,sizeof(foot));
dfs2(n,k,0,100);
dfs4(n,k,100);
dfs5(n,k,100);
printf("%d\n",q(n,n));
printf("%d\n",answer[2]);
printf("%d\n",q(n,k));
printf("%d\n",answer[4]);
printf("%d\n\n",answer[5]);
}
return 0;
}