如何用c++求解整数划分问题？

Question

有例子最好

Answer 1

贴个C语言的：*
描述 Description �0�2
�0�2 将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
�0�2
�0�2 �0�2
�0�2 �0�2
�0�2输入格式 Input Format �0�2
�0�2 输入n，k (6<n<=200，2<=k<=6) �0�2
�0�2 �0�2
�0�2 �0�2
�0�2输出格式 Output Format �0�2
�0�2 一个整数，即不同的分法。�0�2
�0�2Input : 7 3
�0�2output: 4
*/

/*
解题思路：�0�2
我用的是一种比较慢的搜索扩展方法：
比如：
�0�27 = 1+6 6 又可以扩展成：6 = 1+5 很显然这是一个递归的过程
�0�27 = 2+5 5 --> 5= 2+3 不过要注意的是：只要在扩展过程中保证当前所扩展的值不小于前一个即可
�0�27 = 3+4
*/

#include <stdio.h>
#define MAX 101

int n,k ;
long total = 0 ;

void fenjie(int s,int t,int end,int *sum)
{
�0�2 int p,q ;
�0�2 �0�2
�0�2 if(t == k)/*找到一个*/
�0�2 {
�0�2 total ++ ;
�0�2 /*for(q = 1 ; q <= k ; q++)
�0�2 printf("%d ",sum[q]);
�0�2 printf(" ");*/
�0�2 }
�0�2 �0�2
�0�2 else
�0�2 {
�0�2 for(p=s ; p<=end/2 ; p++)
�0�2 {
�0�2 sum[t] = p;
�0�2 sum[t+1] = end-p;
�0�2 �0�2
�0�2 fenjie(p,t+1,sum[t+1],sum); /*方法是从当前结点扩展开出，递归进行求解*/
�0�2 }
�0�2 }
�0�2 �0�2
}

int main(void)
{
�0�2 int i,j,sum[MAX] = {0};
�0�2
�0�2 �0�2
�0�2 scanf("%d %d",&n,&k);
�0�2 �0�2
�0�2 for(i=1 ; i<=n/2 ; i++)
�0�2 {
�0�2 sum[1] = i ;
�0�2 sum[2] = n-i;
�0�2 �0�2
�0�2 fenjie(i,2,sum[2],sum);
�0�2 }
�0�2 printf("%ld ",total);/*output the result*/
�0�2 �0�2
�0�2 �0�2
�0�2 return 0 ;
}

Answer 2

#include<iostream> using namespace std; int f[201][7]; int main(){ int n, k, i, j; cin>>n>>k; for (i = 1; i <= n; i++) f[i][1] = 1;

f[0][0] = 1; for (i = 1; i <= n; i++){ for (j = 1; j <= k && j <= i; j++){ f[i][j] = f[i - 1][j - 1] + f[i - j][j]; } } cout<<f[n][k]<<endl; return 0; }

Answer 3

给你贴上：long long R1( int k, int m ){ if( record[k][m] ) return record[k][m]; if( k<1 || m<1 ) return 0; if( k<m ) return R1(k,k); if( k==m ) return R1(k,m-1) + 1; return R1(k,m-1) + R1( k-m, m );} 另外再补充一句，不要想着别人给你完整的程序，提高编程能力的秘诀是编程编程再编程。