回 帖 发 新 帖 刷新版面

主题:[讨论]一道题目!

2.自然数的拆分work2.???(pas,c,cpp)
任何一个大于1的自然数总可以拆分成若干个自然数之和。
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4
分析:设拆分出的数s1≤s2≤…≤sk。定义数组s为一个栈,用来存放因子。从1开始搜索因子,求和,若sum ≤n就将因子压栈;若sum =n,则输出解,出栈;若sum >n,则修改栈顶元素的值,即回溯。
【输入】
   输入仅一行,包含一个自然数n。
【输出】   
   这个自然数拆分结果。拆分出的因子要求满足s1+s2+…+sk=n 且s1≤s2≤…≤sk。具体要求见样例。
【样例】
输入(work2.in)
4

输出(work2.out)
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4


我编的程序输出顺序不对,请哪位帮我编一个正确的程序(最好用栈)
或者用递归也行

回复列表 (共4个回复)

沙发

var
  s:array[0..100]of longint;
  i,j,k,l,m,n,sum,now,top:longint;
begin
  readln(n);s[0]:=n-1;
  top:=1;s[1]:=1;sum:=1;now:=1;
  while true do
    begin
      inc(top); s[top]:=now; sum:=sum+now;
      if sum>n then begin
                      sum:=sum-s[top];s[top]:=0;dec(top);inc(now);
                      while sum+1>n do
                        begin
                          sum:=sum-s[top];
                          s[top]:=0;
                          dec(top);
                        end;
                      inc(s[top]);sum:=sum+1;
                      now:=s[top];
                    end;
      if sum=n then
      begin
        for j:=1 to top do write(s[j],' '); writeln;
        if top=1 then exit;
      end;
    end;
end.

板凳

能讲一下算法吗?

3 楼

大哥..顺便到小弟的帖子上出几道题..不要太难..偶才6年级..准备去比赛了

4 楼


我也一样

我来回复

您尚未登录,请登录后再回复。点此登录或注册