栈练习自然数的拆分
Time Limit:1000MS Memory Limit:65536K Total Submit:105 Accepted:81
Description
任何一个大于1的自然数总可以拆分成若干个自然数之和。 1:4=1+1+1+1 2:4=1+1+2 3:4=1+3 4:4=2+2 5:4=4
Input
输入仅一行，包含一个自然数n。
Output
这个自然数拆分结果。拆分出的因子要求满足s1＋s2＋…＋sk＝n 且s1≤s2≤…≤sk。具体要求见样例
Sample Input
4
Sample Output
1:4=1+1+1+1 2:4=1+1+2 3:4=1+3 4:4=2+2 5:4=4
Source
ELBA
这题用搜索，搜遍每一个角落就行了 var a:array[0..1000]of longint; ans,i,j,k,n,m:longint; procedure shuchu(dep:longint);//输出。 var i,j,k:longint; begin inc(ans); write(ans,':',n,'='); for i:=1 to dep-2 do begin write(a[i],'+'); end; writeln(a[dep-1]); end; procedure aa(s,dep:longint); var i,j,k:longint; begin if s=0 then//拆分结束条件 begin shuchu(dep); exit; end; m:=s; for i:=1 to s do begin if (a[dep-1]<=i) and (i<n) then begin a[dep]:=i; s:=s-i; aa(s,dep+1); s:=s+a[dep]; end; end; end; begin readln(n); aa(n,1); write(ans+1,':',n,'='); writeln(n); end.