正整数拆分.doc

回专题模式 回学习阶段模式
【题目名称、来源】
正整数拆分（经典问题）
【问题描述】
输入自然数n，然后将n拆分为由若干个数相加的形式，参与加法运算的数可以重复。
输入：n
输出：
所有拆分方案
总的拆分数
例如：
输入：7
输出：
7=1+6
7=1+1+5
7=1+1+1+4
7=1+1+1+1+3
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
7=1+1+1+1+2+2
7=1+1+2+3
7=1+2+4
7=1+2+2+2
7=1+3+3
7=2+5
7=2+2+3
7=3+4
14
【所属专题】
递归、回溯
【适合学习阶段】
第一阶段、第二阶段
【解题思路】
问题分析：很明显这是一道关于数的组合的问题，我们考虑要形成和为n的一些书的组合要满足以下限制：
1、 这一组数的和为n
2、 每一组数的个数不固定
3、 为了避免重复，我们可以让组合中的后一个数必须不小于前一个数。例如n=3时
1+2，2+1其实是同一种方案。
可以将待拆分的数表示成状态，拆去的数值当作规则，拆分的时候最小的数应不小于前一个数，设拆分过程为：
Procedure chaifen(m,start,k);{m为待拆分的数，start为上一步拆掉的数，k为拆到第几步了}
这样拆分的过程可以用下图表示：

存储结构：
Var
a:array [1..100] of integer;{记录递归过程中待拆分数m}
b:array[1..100] of integer;{记录拆去的数}
提高：如果本问题只要求出拆分总数则可以使用动态规划求解
正整数n的拆分方案f(n)的递推式为：
f(n)=f(n,1)+f(n,2)+…+f(n,n-1)+f(n,n)

【测试数据】

【源程序】
program chaifen;
var
a,b:array[1..100] of integer;
{a:待拆分的数；b：被拆掉的数}
n,count:integer;
procedure chai(m,start,k:integer);
{m:待拆分的数，start：上一颗被拆掉的数，k拆到第几个了}
var i,j:integer;
begin
for i:=start to (m div 2) do begin
a[k]:=m-i;b[k]:=i;{记录拆分方案}
{打印}
write(n,'=');
for j:=1 to k do
write(b[j],'+');
writeln(a[k]);
count:=count+1;
chai(a[k],i,k+1);
end;
end;
begin
assign(input,'chaifen.in');
reset(input);
readln(n);
close(input);
assign(output,'chaifen.out');
rewrite(output);
count:=0;
chai(n,1,1);
writeln(count);
close(output);
end.