|
数字全排列问题：
任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：
123，132，213，231，312，321。
注意：数字不能重复，N由键盘输入（N<=9）。
解题思路：
应用回溯法，每个数的取法都有N个方向（1——N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止。
程序代码：
program quanpailie; {数字全排列问题}
var
a:array[1..9] of integer;
k,x,n:integer;
function panduan(j,h:integer):boolean; {判断当前数字是否能赋值给当前数组元素}
var
m:integer;
begin
panduan:=true;
for m:=1 to h-1 do
if a[m]=j then panduan:=false {如果当前数字与前面的数组元素相同则不能赋值}
end;
procedure try(h:integer);
var
i,j,m:integer;
begin
for j:=1 to n do
if panduan(j,h) then
begin
a[h]:=j; {能够赋值，且长度k加一}
k:=k+1;
if k=n then {如果长度达到N则表示一种组合已经完成，输出结果}
begin
for m:=1 to n do
write(a[m]);
write('':4);
x:=x+1; {每输出一种排列方式加一}
if x mod 5=0 then writeln; {每行输出5种排列方案}
end
else
try(h+1); {对下一个数组元素进行赋值}
k:=k-1 {回溯的时候一定要把长度减一}
end
end;
begin
writeln('输入 N:');
readln(n);
k:=0; {k表示长度，长度初始值为0}
x:=0; {x表示总的排列方式}
try(1); {对第一个数组元素赋值}
writeln('共有 ', x ,' 种排列方案')
end.
|
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
