输出和等于n的所有不增的正整数和式

来源：百度知道 编辑：UC知道 时间：2024/05/21 13:14:29
输入n,输出和等于n的所有不增的正整数和式，如n=4将输出：
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1

找到一个参考程序，是用递归做的，但我不明白原理，请赐教！
Pascal程序：
const n=10;
var a:array[-100..100] of integer;
procedure print(k:integer);
var j:integer;
begin
write(n,'=',a[0]);
for j:=1 to k-1 do write('+',a[j]);
writeln;
end;

procedure rd(i,k:integer);
var j:integer;
begin
if i=0 then print(k);
for j:=i downto 1 do
if (k=0) or (j<=a[k-1]) then begin
a[k]:=j;
rd(i-j,k+1);
end;
end;

begin
rd(n,0);
end.

c程序：
#include <stdio.h>
int a[100] ;
outresult(int k)
{
int j;
printf("=%d",a[0]);
for(j=1;j<k;j++) printf("+%d",a[j]);
printf("\r\n");
}

rd(int i ,int k)//递归法
{ if(i==0) outresult(k);
int j ;
for(j=

原理大概是这样的
a这个数组中存放着被分解的这些数
递归的过程就是用k表示已分解几个数，i表示原来的数减去已分解的数，可以看成待分解的部分。
注意这个循环
for(j=i;j>=1 ;j--)
if (k==0||j<=a[k-1])

每次从大到小分解这个数，这样能保证按字典序输出并且没有重复。
这个过程比较类似于深度优先搜索，就是dfs，不过是模拟的算法。
如果你还不明白我建议你看一些搜索算法的资料，这样比较好理解。

递归的分析用一两句话很难说清楚，不如自己用调试的方式去跟踪程序的执行过程和变量值的变化情况，从而理解程序。