算法中穷举搜索法的一事例

有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。
例1  找出n个自然数（1,2,3,…,n）中r个数的组合。例如，当n=5，r=3时，所有组       合为：
            5      5      3
           5      4      2
           5      4      1
           5      3      2
           5      3      1
           5      2      1
           4      3      2
           4      3      1
           4      2      1
           3      2      1
       total=10     {组合的总数}
［程序］
program  zuhe11;
  const n=5;
    var  i,j,k,t:integer;
     begin  t:=0;
       for  i:=n  downto  1  do
         for  j:=n  downto  1  do
           for  k:=n  downto  1  do
             if  (i<>j) and (i<>k) and (i>j) and (j>k)  then
               begin
                 t:=t+1;writeln(i:3,j:3,k:3);
               end;
       writeln('total=',t);
     end.
这个程序，穷举了所有可能情形，从中选出符合条件的解，很多情况下穷举搜索法还是常用的。
例2  算24点（poi24.pas）。    
【题目描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1～9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，×，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2×2)/4是合法的，2×(2/4)是不合法的）。下面我们给出一个游戏的具体例子：若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3×7=24。
【输入】
只有一行，四个1～9之间的自然数。
【输出】
如果有解的话，只要输出一个解，输出的是3行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。如果没有解，则输出“no answer!”
【样例】
poi24.in    poi24.out
1 2 3 7 2+1=3
7×3=21
21+3=24
【算法分析】
计算24点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。
［程序］
program  poi24; {point24}
type arr=array [1..4] of integer;
var i,result,n,len:integer;
   d:arr;
   r:array [1..3,1..4] of integer;
   infile,outfile:text;
procedure print;
var i,j:integer;
begin
 assign(outfile,'poi24.out');
 rewrite(outfile);
 for i:=1 to 3 do
 begin
     for j:=1 to 3 do
       if j<>2 then write(outfile,r[i,j])
         else case r[i,j] of
                 1:write(outfile,'+');
                 2:write(outfile,'-');
                 3:write(outfile,'*');
                 4:write(outfile,'/')
               end;
      writeln(outfile,'=',r[i,4])
   end;
 close(outfile);
end;
procedure try(k:integer;d:arr);
var a,b,i,j,l,t:integer;
   e:arr;
begin
 if k=1 then if d[1]=24 then begin print;halt end else
    else  begin
         for i:=1 to k-1 do
         for j:=i+1 to k do
          begin
          a:=d[i]; b:=d[j];
          if a<b then begin t:=a;a:=b;b:=t end;
          t:=0;
          for l:=1 to k do if (l<>i) and (l<>j) then begin t:=t+1;e[t]:=d[l] end;
          r[5-k,1]:=a;
          r[5-k,3]:=b;
          r[5-k,4]:=-1;
          for l:=1 to 4 do
           begin
            case l of
              1:r[5-k,4]:=a+b;
              2:r[5-k,4]:=a-b;
              3:r[5-k,4]:=a*b;
              4:if b<>0  then if a mod b=0 then r[5-k,4]:=a div b
            end;
           r[5-k,2]:=l;
           if r[5-k,4]<>-1 then
                begin
                 e[t+1]:=r[5-k,4];
                 try(k-1,e)
                end
          end
       end
    end;
end;
begin
 assign(infile,'poi24.in');
 reset(infile);
 for i:=1 to 4 do read(infile,d[i]);
 close(infile);
 try(4,d);
 assign(outfile,'poi24.out');
 rewrite(outfile);
 writeln(outfile,'no answer!');
 close(outfile);
end.

练习题
彩虹7号（rainbow.pas）
X市是一个重要的军事基地，在这个基地中有一支名为“彩虹7号”的特别部队。每个队员都有一个固定独立的编号X(1≤X≤215)，他们的职责就是完成部队交给他们的任务，每个任务同样都有固定独立的编号N(1≤N≤10)。在执行任务的过程中，为了保证任务的保密性和队员的安全，队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备进行。
每个队员都需要一个身份验证口令进入系统，由于队员所执行的任务都是涉及国家安全或者极高机密的活动，如果队员使用的口令出现错误，他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才，所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。
口令S的内容满足：SN=X。显然，S有可能也很有可能是一个无理数，所以限定S为一个实数，它包含整数部分和小数部分，不包含小数点（即0.1将视作01）。口令的长度      M(10≤M≤50)，将根据任务的难度而有所不同。
编程任务：给定X，N，M。计算口令的内容S。
输入（rainbow .in）：文件输入，文件有且仅有一行包含3个整型数X，N，M，每个数之间以一个空格符隔开。
输出（rainbow.out）：文件输出，文件有且仅有一行，为S的结果。
样例输入：2 2 10
样例输出：1414213652
注意：口令的最后一位请使用去尾法保留，不要使用四舍五入法保留。文件请不要包含多余的空格和换行。