回溯问题,请教(100分)

浩思

Unregistered / Unconfirmed
GUEST, unregistred user!
以下程序实现
输入n,输出等于n的所有不增的正整数和式。如n=4,程序将输出:
4=4
4=3+l
4=2+2
4=2+1+1
4=l+1+1+l
注意::::一定要求用回溯实现,下面的程序中,请问高手:R[k]数组何解?
const maxn=100;
var i,k,n:longint;
a,r:array[0..maxn] of longint;
begin
write('Input n:');
readln(n);
a[1]:=n;
r[1]:=0;
k:=1;
repeat
if r[k]=0
then
begin
for i:=1 to kdo
write(a,' ');
writeln;
while (k>0) and (a[k]=1)do
k:=k-1;
a[k]:=a[k]-1;
r[k]:=r[k]+1
end
else
begin
if r[k]<a[k]
then
a[k+1]:=r[k]
else
a[k+1]:=a[k];
r[k+1]:=r[k]-a[k+1];
k:=k+1
end
until k=0
end.
 
这段程序是这个意思:因为你进行整数分解时时按不增序分解的,
那么我首先要保证探测值(r[k])小于或等于当前分解值(a[k]),
当满足这个条件时表示该探测值是可取的,所以取r[k]作为下一个分解值。
k表示的是当前探测的深度,也就是分解后形成的正整数的个数。
r[k]=0就表示当前的这次探测结束,输出结果,同时将深度减1,实现回朔.[:)]
 
接受答案了.
 

Similar threads

顶部