拆分自然数的几种算法

《拆分自然数的几种算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、拆分自然数的几种算法【问题描述】自然数的拆分：任何一个大于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开始

2、搜索直到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);s

3、plitN(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("%dt",

4、total);for(j=1;j

5、=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+4=1+2+2+2=1+3+3=2+5=2+2+3=3+4用数组a存储完成n的一种拆分。从上面不完全归纳法的分析n=7时，按a［1］分类，有a［1］=1，a［1］=2，…，a［1］=n/2，共n/2大类拆分。在每一类拆分时，a［1］=i，a［2］=n-i，从k=2，继续拆分从a［k］开始，a［k］能否再拆分取决于a［k］/2是否大于等于a［k-1］。递归过程的参数t指向要拆分的数a［k］#includeusingnamespacestd;inta[100

6、]={0};voidSplit(intt){inti;for(i=1;i