拆分自然数的几种算法
温柔似野鬼°
797次浏览
2021年01月27日 23:11
最佳经验
本文由作者推荐
雷锋日活动策划-新学期新打算300字
拆分自然数的几种算法
【问题描述】
自然数的拆分：
任何一个大于
1
的自然数
N
，
总可以拆分成若干个自然数之和，
并且有多 种拆分方法。例如自然数
5
，可以有如下一些拆分方法：
【问题描述】自然数的拆分：
任何一个大于
1
的自然数
N
，
总可以拆 分成若干个自然数之和，
并且有多种拆分方法。例如自然数
5
，可以有如下一些拆分方 法：
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4
5=2+3
算法一
用回溯法来实现
针对所给问题，定义问题的解空间；如本题对
5
的拆分来说，
1<=
拆分的数
<=5
。
确定易
于搜索的解空间结构；如本题对
5
的拆分来说，用
x[]
数 组来存储解，每个数组元素的取值
范围都是
1<=
拆分的数
<=5
， 从
1
开始搜索直到
5
。
搜索解空间，并在搜索过程中用剪 枝函
数避免无效搜索。
如本题对
5
的拆分来说，
为了避免重复，x>=x[j](i>j)
，
如
x[]={2,3}
满足条
件而
x[]={3,2}
就不满足条件不是可行解即无效。
#include
#include
void
splitN(
int
n,
int
m);
//
n
是需要拆分的数，
m
是拆分的进度。
int
x[1024]={0},total=0
//
total
用于计数拆分的方法数，
x[]
用于存储解
void
main()
{
int
n
printf(
);
scanf(
,&n);
splitN(n,1);
printf(
,total,n);
}
void
splitN(
int
n,
int
m)
{
//n
是需要拆分的数，
m
是拆分的进度
int
rest,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(
,total);
for
(j=1;j
printf(
,x[j]);
}
printf(
,x[m]);
printf(
);
}
else
{
splitN(rest,m+1);
//
否则将剩下的数进行进度为
m+1
拆分
}
x[m]=0;
//
取消本次结果，进行下一次拆分。环境恢复，即回溯
}
}
}
算法二
用递归来实现
任何一个大于
1
的自然数
n
，总可以拆分成若干个小于
n
的自然数之和，试求
n
的所有拆
分。
用不完全归纳法
n =2
可拆分成
2 =1 +1
n =3
可拆分成
3 =1 +2 =1 +1 +1
n =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