整数划分c语⾔程序递归，递归整数划分
递归实现整数划分
⽬录
递归实现整数划分
1.原理
2.Python实现
3.C实现
1.原理
拿6为例，可划分为：
6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1
共11种情况。
我们拿函数d(n,m)为例描述划分状态。n表⽰被划分的数，m表⽰划分出的集合中，每⼀种可能的最⼤加数为m。d(n,m)表⽰当被划分数为n，划分出的最⼤数为m时，能划分出的种数。
当n=1时，d(1,m) = 1
当m = 1时，d(n,1) = 1
当m > n时，d(n,m) = d(n,n)
当m=n时，d(n,m) = d(n,m-1) + 1
当m
其中，d(6,3)就是被⼤框包着的下⾯的⼩框，d(2,4)就是上⾯的⼩框。上⾯的⼩框，都有重复的4，若忽略4，它便是2的划分2，1+1这两条。 所以这个框的内容实际上就是对2的划分d(2,2) = 1 + d(2,1)(前⾯的1就是d(0,2)，即2本⾝这⼀种。⽽d(2,1)因为m为1，也当然只有⼀种，即1+1)。
总结：对任何⼀种算法，我们⾸先尽可能的建⽴相应的数学模型，这⾥的数学模型并不是说需要多么
⾼⼤上，⽽是把所需解决的问题转化为数学问题，类似于⼀种从具体到抽象的过程。  我们根据上⾯的⽰例可以发现：⽐如对整数6进⾏划分，我们在每次划分时，都分为两个部分，第⼀个数为⼀个部分，其余的为第⼆个部分，从6开始第⼀部分依次是6，5，4，3，2，1，那么第⼆部分就是(6-6)，(6-5)，(6-4)，(6-3)，(6-2)，(6-1)的且不超过相应的第⼀部分的划分。具体分析如下：
2.Python实现
def divison(n,m,string):
if n == 0:
print(string)
else:
if m > 1:
division(n,m-1,string)
if m <= n:
divison(n-m,m,string + ' ' + str(m))
n = int(input('请输⼊⼀个正整数：'))
m = n
print(n + '的划分如下')
division(n,m,'')
3.C实现
#include
int a[100];//创建⼀个数组储存拆分后的数
void divide(int num, int b, int c)//创建拆分函数进⾏递归
{
int i;
if(num!=0){//当初始数或上⼀次拆剩下的数不是零时接着拆分for(i=num;i>0;i--){
if(i<=b){//拆出来的数要⼩于等于上⼀个拆出来的数，以避免重复a[c]=i;//将拆出来的数储存在数组a中
divide(num-i,i,c+1);}//对拆剩下的数在进⾏拆分
}}
else{//当拆剩下的数等于零时，将数组a输出
for(i=0;i
printf("%d", a[i]);
printf("+");
}
printf("%d", a[c-1]);
printf("\n");递归函数c语言规则
}
}
int main(){
divide(6,6,0);
}
恳请批评指正。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。