all_sort.txt

经典的剪枝

数字全排列问题     -|lxgzx001 发表于 2006-3-4 21:16:00  
 

数字全排列问题：
任意给出从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.

 


program qupl;
var
i,n,t,k:integer;
a:array[1..3] of integer;
x:array[1..3] of integer;
procedure print;
var
j:integer;
begin
for j:=1 to 3 do
write(x[j]:4);
writeln;
inc(t);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to 3 do
    if a[j]=0 then
       begin
       x[i]:=j;
       a[j]:=1;
       if i<3 then try(i+1) else print;
       a[j]:=0;
       end;
end;
begin
writeln('---------------------');
t:=0;
for i:=1 to 3 do a[i]:=0;
try(1);
writeln('total=',t);
end.