文档介绍：--------------------------校验:_____________-----------------------日期:_____________拆分自然数的几种算法拆分自然数的几种算法【问题描述】自然数的拆分:任何一个大于1的自然数N,总可以拆分成若干个自然数之和,并且有多种拆分方法。例如自然数5,可以有如下一些拆分方法:【问题描述】自然数的拆分:任何一个大于1的自然数N,总可以拆分成若干个自然数之和,并且有多种拆分方法。例如自然数5,可以有如下一些拆分方法:5=1+1+1+1+15=1+1+1+25=1+2+25=1+45=2+3算法一用回溯法来实现针对所给问题,定义问题的解空间;如本题对5的拆分来说,1<=拆分的数<=5。确定易于搜索的解空间结构;如本题对5的拆分来说,用x[]数组来存储解,每个数组元素的取值范围都是1<=拆分的数<=5,从1开始搜索直到5。搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。如本题对5的拆分来说,为了避免重复,x>=x[j](i>j),如x[]={2,3}满足条件而x[]={3,2}就不满足条件不是可行解即无效。#include#includevoidsplitN(intn,intm);//n是需要拆分的数,m是拆分的进度。intx[1024]={0},total=0;//total用于计数拆分的方法数,x[]用于存储解voidmain(){intn;printf("pleaseinputthenaturalnumbern:");scanf("%d",&n);splitN(n,1);printf("Thereare%dwaystosplitnaturalnumber%d.",total,n);}voidsplitN(intn,intm){//n是需要拆分的数,m是拆分的进度intrest,i,j;for(i=1;i<=n;i++){//从1开始尝试拆分if(i>=x[m-1]){//拆分的数大于或等于前一个从而保证不重复x[m]=i;//将这个数计入结果中rest=n-i;//剩下的数是n-i,如果已经没有剩下的了,并且进度(总的拆分个数)大于1,说明已经得到一个结果了if(rest==0&&m>1){total++;printf("%d\t",total);for(j=1;j<m;j++){printf("%d+",x[j]);}printf("%d",x[m]); printf("\n");}else{splitN(rest,m+1);//否则将剩下的数进行进度为m+1拆分}x[m]=0;//取消本次结果,进行下一次拆分。环境恢复,即回溯}}}算法二用递归来实现任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和,试求n的所有拆分。用不完全归纳法n=2可拆分成2=1+1n=3可拆分成3=1+2=1+1+1n=4可拆分成4=1+3=1+1+2=1+1+1+1=2+2……n=7可拆分成7=1+6=1+1+5=1+1+1+4=1+1+1+1+3=1+1+1+1+1+2=1+1+1+1+1+1+1=1+1+1+2+2=1+1+2+3=1+2+