数的拆分

来源：百度知道 编辑：UC知道 时间：2024/05/20 19:44:20
将正整数n拆分成k份（使k个非零数之和的等于n）,且每种拆分方案不能为空，任意两种拆分方案不能相同（不考虑顺序）。例如：n＝7，k＝3，共4种拆分方法为：①1、1、5； ②1、2、4； ③1、3、3； ④2、2、3。下面三种分法被认为是相同的：1、1、5； 1、5、1； 5、1、1；编程任务：
给定的正整数n，分成k分，编程计算有多少种不同的分法,并将每组数存入数组。
也可以不用存到数组入输出,只求出不同的分法.

若输出拆法，深度优先搜索，为(n,k)时则记录。
int n,k,num[100];
void number(int now,int nowk)
{ int i;
if(nowk==k&&now==0)
保存num数组;
for(i=now+1;i<=n;i++)
{ num[nowk]=i;
number(n-i,nowk+1);
}
}
调用：number(n,0);
若只要个数则用动态规划。

不输出拆法的话是用二重循环做。具体如何我记不清了（以前推导出来过，方法也有很多）

输出拆法就用搜索呗