就编成一个可执行的程序，而是分步进行。
    ．第一步编出的程序最为抽象；
    ．第二步编出的程序是把第一步所编的程序（如过程、函数等）细化，较为抽象；
    ．……
    ．第i步编出的程序比第i-1步抽象级要低；
    ．……
    ．直到最后，第n步编出的程序即为可执行的程序。
    所谓“抽象程序”是指程序所描述的解决问题的处理规则，是由那些“做什么”操作组成，而不涉及这些操作“怎样做”以及解决问题的对象具有什么结构，不涉及构造的每个局部细节。
    这一方法原理就是：对一个问题（或任务），程序人员应立足于全局，考虑如何解决这一问题的总体关系，而不涉及每局部细节。在确保全局的正确性之后，再分别对每一局部进行考虑，每个局部又将是一个问题或任务，因而这一方法是自顶而下的，同时也是逐步求精的。采用逐步求精的优点是：
    （１）便于构造程序。由这种方法产生的程序，其结构清晰、易读、易写、易理解、易调试、易维护；
    （２）适用于大任务、多人员设计，也便于软件管理。
    逐步求精方法有多种具体做法，例如流程图方法、基于过程或函数的方法。
    [例]求两自然数,其和是667,最小公倍数与最大公约数之比是120:1(例如(115,552) 、（232,435）)。
    [解]两个自然数分别为m和667-m(2≤m≤ 333)。
   处理对象：m(自然数)、l(两数的最小公倍数)、g（两数的最大公约数）。
   处理步骤：对m从２到333检查l与g的商为120,且余数为0时,打印m与667-m 。
   第一层抽象程序：
    Program TwoNum;
    Var   m,l,g:integer;
    Begin  for  m:=2  to  333  do
      begin  l:=lcm(m,667-m);    ｛求最小公倍数｝
      g:=gcd(m,667-m)；    ｛求最大公约数｝
      if  (l=g*120)and(l mod g=0)  then
          writeln(m:5,667-m:5);
      end;
    End.
    第二层考虑函数lcm（最小公倍数）、gcd（最大公约数）的细化。
    最大公约数问题是对参数a、b，找到一个数i能整除a与b，i就是gcd的函数值。
      Function  gcd(a,b:integer):integer;
      var  i:integer;    
      begin  for  i:=a  downto  1  do  
        if  not((a  mod  i=0)or(b  mod  i=0))  then  gcd:=i;
      end;
    而最小公倍数的计算是：若干个b之和，若能被a整除，则该和便是a、b的最小公倍数。
      Function  lcm(a,b:integer):integer;
      var  i:integer;
      begin  i:=b;
        while  i  mod  a=0  do  i:=i+b;
        lcm:=i;
      end;

就编成一个可执行的程序，而是分步进行。
    ．第一步编出的程序最为抽象；
    ．第二步编出的程序是把第一步所编的程序（如过程、函数等）细化，较为抽象；
    ．……
    ．第i步编出的程序比第i-1步抽象级要低；
    ．……
    ．直到最后，第n步编出的程序即为可执行的程序。
    所谓“抽象程序”是指程序所描述的解决问题的处理规则，是由那些“做什么”操作组成，而不涉及这些操作“怎样做”以及解决问题的对象具有什么结构，不涉及构造的每个局部细节。
    这一方法原理就是：对一个问题（或任务），程序人员应立足于全局，考虑如何解决这一问题的总体关系，而不涉及每局部细节。在确保全局的正确性之后，再分别对每一局部进行考虑，每个局部又将是一个问题或任务，因而这一方法是自顶而下的，同时也是逐步求精的。采用逐步求精的优点是：
    （１）便于构造程序。由这种方法产生的程序，其结构清晰、易读、易写、易理解、易调试、易维护；
    （２）适用于大任务、多人员设计，也便于软件管理。
    逐步求精方法有多种具体做法，例如流程图方法、基于过程或函数的方法。
    [例]求两自然数,其和是667,最小公倍数与最大公约数之比是120:1(例如(115,552) 、（232,435）)。
    [解]两个自然数分别为m和667-m(2≤m≤ 333)。
   处理对象：m(自然数)、l(两数的最小公倍数)、g（两数的最大公约数）。
   处理步骤：对m从２到333检查l与g的商为120,且余数为0时,打印m与667-m 。
   第一层抽象程序：
    Program TwoNum;
    Var   m,l,g:integer;
    Begin  for  m:=2  to  333  do
      begin  l:=lcm(m,667-m);    ｛求最小公倍数｝
      g:=gcd(m,667-m)；    ｛求最大公约数｝
      if  (l=g*120)and(l mod g=0)  then
          writeln(m:5,667-m:5);
      end;
    End.
    第二层考虑函数lcm（最小公倍数）、gcd（最大公约数）的细化。
    最大公约数问题是对参数a、b，找到一个数i能整除a与b，i就是gcd的函数值。
      Function  gcd(a,b:integer):integer;
      var  i:integer;    
      begin  for  i:=a  downto  1  do  
        if  not((a  mod  i=0)or(b  mod  i=0))  then  gcd:=i;
      end;
    而最小公倍数的计算是：若干个b之和，若能被a整除，则该和便是a、b的最小公倍数。
      Function  lcm(a,b:integer):integer;
      var  i:integer;
      begin  i:=b;
        while  i  mod  a=0  do  i:=i+b;
        lcm:=i;
      end;

编程入门题(二)

1、求素数：求2至N（2≤N≤500）之间的素数。例如：
输入：N=100
输出：  2   3    5   7  11  13
       17  19   23  29  31  37
       41  43   47  53  59  61
       71  73   79  83  89  97
       total=24   {表示2至100之间的素数有24个}
[解法一]素数是指除1及本身以外不能被其他数整除的自然数。下面介绍用穷举法求素数。
１．    2是素数；t=0；
２．    I=2～n，则：
（1）如果i是素数，则其必须是奇数且不能被2～√i  中的任一个数整除。
     （2）如果I是素数，则输出该素数且计数器t=t+1；
   3．输出2～N之间素数的总数：total=t;
4．程序结束

[程序]
program exa;
uses crt;
var  i,k,n,w,t:integer;
     yes:boolean;
Begin t:=0;clrscr;write(‘N=’);readln(n);
  if (n<2)and(n>500) then
    begin writeln(‘input error!’);halt;end;
  write(2:5);t:=1;
  for i:=2 to n do
    if odd(i) then
      begin yes:=true;
        w:=trunc(sqrt(I));k:=2;
        while (k<=w)and yes do
          begin if i mod k=0 then yes:=false; k:=k+1;end;
        if yes then begin write(i:5);t:=t+1; end;
      end;
  writeln(‘total=’,t);
end.

[解法二]筛法求素数：
    1．建立一个包括2，3，…，N的数据“集合”R；
    2．顺序取R中的数（从素数2开始），同时将其及能整除它的数从R中划去。“筛法求素数”的过程如下图示：
素数R[1]                   数据集合R
   2    { 2， 3， 4， 5， 6， 7， 8，  9，10，11，12，……}
   3    {     3，     5，      7，    9，     11，   ……}
   5    {             5，      7，            11，   ……}
……                     ………
    这样便可得到所求的素数：2，3，5，……。
[程序]
program Sushu;
var  i,j,k,n,w,t:integer;
  R,P:array [1..500] of integer;
Begin
  write('N=');readln(n);
  if (n<2) or (n>500) thenbegin writeln('Input N error!');halt end;
  for i:=2 to n do R[i-1]:=i; writeln('Result:');t:=0;k:=n-1;
  while k>0 do
    begin P:=R;  {数组P保存在P中}
      write(R[1]:5);  {输出素数} t:=t+1;w:=R[1];j:=0;
      for i:=1 to k do
        if P[i] mod w<>0 then  {划去w及 W的倍数}
          begin j:=j+1; R[j]:=P[i];end;  {重新构造集合R}
      k:=j; {新建后R的元素个数}
    end;  writeln;writeln('Total=',t);
end.

2、矩阵相乘：已知N×M1矩阵A和M1×M矩阵B（1≤M、M1、N≤10），求矩阵C（=A×B）。例如：
输入：N，M1，M=4  3  4
      A= 1   2    3             
3    4    5             提示：所谓矩阵相乘（如A×B=C），是指
4    5    6                Cij= ∑(Aik×Bkj)(i=1～N,j=1～M1,k=1～M)
5    –1  –2                   
           B= 1   6    4    2        例如：
              2   3    4    1             C11=A11×B11+A12×B21+A13×B31
            –1   5    7   –3              =1×1+2×2+3×（– 1）
输出：C= 2   27   33   –5             =2
              6   55   63   –5            C42= A41×B12+A42×B22+A43×B32
              8   69   78   –5              =5×6+（–1）×3+（–2）×5
         5   17   2    15               =17
[解]该题主要考查矩阵的表示及其运算。矩阵Ａ（N×M1）与矩阵Ｂ(M1×M）相乘得矩阵Ｃ（Ｎ×Ｍ），其解法如下：
       i=1～Ｎ，重复做
         j=1～M,重复做
     (1)cij=0； (2)k=1～M1，重复做Cij=Cij+Aik*Bkj； (3)输出Ｃij
[程序]
program JiZheng;
var i,j,k,N,M1,M:integer;
A,B,C:array [1..10,1..10] of integer;
Begin
  write('N,M1,M=');readln(N,M1,M);
  if (N>=1)and(N<=10)and(M1>=1)and(M1<=10)and(M>=1)and(M<=10) then
begin {输入N×M1矩阵A}write('A=');
for i:=1 to N do for j:=1 to M1 do read(A[i,j]);readln;
    {输入M1×M矩阵B} write('B=');
for i:=1 to M1 do for j:=1 to M do read(B[i,j]);readln;
    write('C=');
      for i:=1 to N do
        begin for j:=1 to M do{计算Cij= ∑(Aik×Bkj)}
          begin C[i,j]:=0; for k:=1 to M1 do C[i,j]:=C[i,j]+A[i,k]*B[k,j];
            write(C[i,j]:5); ｛输出矩阵Cij｝
          end;
          writeln;write(' ':2);
        end;
      writeln;
    end
  else writeln('Input N,M1,M error!');
end.

3、找数字对：输入N（2≤N≤100）个数字（在0与9之间），然后统计出这组数中相邻两数字组成的链环数字对出现的次数。例如：
输入：N=20  {表示要输入数的数目}
      0  1  5  9  8  7  2  2  2  3  2  7  8  7  8  7  9  6  5  9   
输出：（7，8）=2 （8，7）=3 {指（7，8）、（8，7）数字对出现次数分别为2次、3次）
     （7，2）=1 （2，7）=1
     （2，2）=2
     （2，3）=1 （3，2）=1
[解]该题主要是数组的存储表示及运用。数组A存放所输入的N个数，用数组B表示A[i]与A[i+1]相邻数字对出现的次数。计算过程见下表：
数组A次数i    0  1  5   9  8   7   2   2   2   3  2   7   8   7   8   7   9    6  5   9 1  2   3  4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
求链环数字的过程    I= 1： B[0,1]=1      I=2：B[1,5]=1      I=3： B[5,9]=1     I=4： B[9,8]=1 I= 5： B[8,7]=1      I=6：B[7,2]=1      I=7： B[2,2]=1     I=8： B[2,2]=2 I=9： B[3,2]=1      I=10：B[2,3]=1     I=11：B[2,7]=1      I=12：B[7,8]=1     I=13：B[8,7]=2      I=14：B[7,8]=2     I=15：B[8,7]=3      I=16：B[7,9]=1     I=17：B[9,6]=1      I=18：B[6,5]=1     I=19：B[5,9]=1
[程序]
Program Getdouble;
var i,N:integer; fd:boolean;
  A:array[1..100] of integer;
  B:array[0..9,0..9] of integer;
Begin fillchar(B,sizeof(B),0);{数组B初值置为0} write('N=');readln(N);
  if (N>1)and(N<=100) then
    begin write('Enter ',N,' numbers:');
      for i:=1 to N do
        begin read(A[i]);  {输入A[i]}
          if (A[i]<0)or(A[i]>9) then   {A[i]的值在0与9之间}
            begin writeln('Input error!');halt;end;
        end;
      for i:=1 to N-1 do
        B[A[i],A[i+1]]:=B[A[i],A[i+1]]+1;{相邻数字对BA[i],A[i+1]值加1}
      fd:=true;writeln('Result:');
      for i:=1 to N-1 do
        if (B[A[i],A[i+1]]>0)and(B[A[i+1],A[i]]>0) then
          begin write('(',A[i],',',A[i+1],')=',B[A[i],A[i+1]],'  ');
            if A[i+1]=A[i] then writeln {相邻数字相同，如（2，2）}
              else writeln('(',A[i+1],',',A[i],')=',B[A[i+1],A[i]]);
            B[A[i+1],A[i]]:=0;
            fd:=false;
          end;
      if fd then writeln('Not found!');
    end
  else writeln('Input N error!');
end.
4、蛇形矩阵：生成一个按蛇形方式排列自然数1，2，3，4，5，……，N2的 (1<N≤10)阶方阵。例如：
输入：N=4                         N=7
输出：1   3    4   10               1    3    4   10   11   21   22
           2   5    9   11               2    5    9   12   20   23   34
           6   8   12   15               6    8   13   19   24   33   35
           7   13  14   16               7   14   18   25   32   36   43
                                        15   17   26   31   37   42   44
                                        16   27   30   38   41   45   48
                                        28   29   39   40   46   47   49
[解]本题考查重点是矩阵的表示及
    上下标运算，旨在培养观察和
    分析思维能力。
        例如，当N=7 时，把1，
    2，3，……，49逐一填入数组
    A中，搜索填数的方向如右图示：

    从图中，我们可以看出：对每个数字m（1，2，……，～N*N）来说，可能按以下四种搜索方向之一填数：
                              d=2（右上）
    
                      m        d=3（向右）
           d=4        
         （左下）        d=1（向下）
    按照图10-1的搜索方向填数时，先要把当前数字m填入数组A[i,j]中，接下来就是要确定下一次的填数的坐标及其搜索方向（即d=?）。现分析如下：
    第一种情形（d=1，如m=2,7,15；35，44）：
              （i，j）
            d=1        d=2(当j=1)
              （i+1，j）
               
                d=4(当j=N)
    第二种情形（d=2，如m=2,10,21；或34,43,48；或7,8,9,16,17,18,19等）：
                    d=2(当i<>1且j<>N)
                 
             （i-1，j）     d=3(当i=1)
               
          d=2       d=1(当j=N)
          (i，j)
    第三种情形（d=3，如m=29,40,47;或4,11,22）：
                    d=3          d=2(当i=N)
             （i，j）     (i，j+1)
               
                     d=4(当j=N)
    第四种情形（d=4，如m=28,39,46;或6,15；或5,12,13,14等）：
                     (i，j)
                      d=4
              （i+1，j）     d=3(当i=1)
               
                d=4(当i=N且j<>1)

[程序]
Program she;
const max=10;
var d,i,j,m,N:integer;
  A:array [1..10,1..10] of integer;

begin
  write('N=');readln(N);
  if (N>=1) and (N<=max) then
    begin i:=1;j:=1;m:=1;d:=1;
      repeat A[i,j]:=m;   {填数}
        case d of
          1: {第一种情形}begin i:=i+1; if j=1 then d:=2 else d:=4; end;
          2: {第二种情形}begin i:=i-1;j:=j+1;
if j=N then d:=1 else if i=1 then d:=3;end;
          3: {第三种情形}begin j:=j+1; if i=N then d:=2 else d:=4;end;
          4: {第三种情形}begin i:=i+1;j:=j-1;
if i=N then d:=3 else if j=1 then d:=1;end;
        end;
        m:=m+1;
      until m>N*N;
      writeln('OUTPUT:');
      for i:=1 to N do begin for j:=1 to N do write(A[i,j]:4); {输出填数} writeln;end;
    end
  else writeln('Input N error!');
end.

5、编码问题(95年全国分区联赛题)：设有一个数组A：array [0..N-1] of integer； 存放的元素为0～N-1(1<N<=10)之间的整数，且A[i]≠A[j]（i≠j）。例如当N=6时，有：A=（4，3，0，5，1，2）。此时，数组A的编码定义如下：
A[0]编码为0；
A[i]编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数
          （i=1，2，…，N-1）
∴上面数组A的编码为：B=（0，0，0，3，1，2）
    要求编程解决以下问题：
(1)给出数组A后，求出其编码；
(2)给出数组A的编码后，求出A中的原数据
程序样例：
例一：
输入：Stat=1   {表示要解决的第（1）问题}
       N=8      {输入８个数}
       A=1 0 3 2 5 6 7 4
输出：B=0 0 2 2 4 5 6 4
例二：
输入：Stat=2   {表示要解决的第（2）问题}
       N=7
       B=0 1 0 0 4 5 6  
输出：A=2 3 1 0 4 5 6


[解]第1个问题的解法：用穷举搜索法。
      B[0]为0
      B[i]表示在A[1]，A[2]，……，A[i-1]中比A[i](i=1,2,……,N)小的个数。
    第2个问题的解法：先构建数组P，初始值为0，1，2，３，……，N-1。然后从B[N-1]，B[N-2]，……，B[1]，B[0]逆向从数组P中取数求数组A。以题中例二为例，求解过程如下图：
下标值i    B0 B1 B2  B3 B4  B5 B6     p0 p1 p2  p3 p4  p5  p6    数组A
   6    0 1  0  0  4  5  6                ↑    0  1  2  3  4  5  6    A[6]=p[B6]=p6=6,划去p6
   5    0 1  0  0  4  5  6             ↑        0  1  2  3  4  5    A[5]=p[B5]=p5=5,划去p5
   4    0 1  0  0  4  5  6          ↑          0  1  2  3  4     A[4]=p[B4]=p4=4,划去p4
   3    0 1  0  0  4  5  6       ↑             0  1  2  3       A[3]=p[B3]=p0=0,划去p0
   2    0 1  0  0  4  5  6    ↑                1  2  3      A[2]=p[B2]=p0=1,划去p0
   1    0 1  0  0  4  5  6 ↑                   2  3      A[1]=p[B1]=p1=3,划去p2
   0    0 1  0  0  4  5  6↑                     2       A[0]=p[B0]=p0=2
    从上述求解过程中，我们得到：A=（2，3，1，0，4，5，6）。
[程序]
program code;
var  i,j,k,m,n,stat:integer;
  A,B,P:array [0..10] of integer;
begin
  write('Stat(1,or 2)=');readln(stat);
  case stat of
    1:begin write('N='); readln(n); write('A=');
        for i:=0 to n-1 do read(A[i]); readln; {读入数组A}
        for i:=0 to n-2 do  
          for j:=i+1 to n-1 do
            if (A[i]=A[j])or(A[i]>n-1) then {数组A中有否相等}
              begin writeln('Input error!');halt; end;
        for i:=0 to n-1 do B[i]:=0; {编码数组B初始值为0}
        for i:=1 to n-1 do
          for j:=0 to i-1 do
            if A[i]>A[j] then B[i]:=B[i]+1; {求数组编码}
        for i:=0 to n-1 do write(B[i]:5);writeln;
      end;
    2:begin write('N='); readln(n); write('B=');
        for i:=0 to n-1 do read(B[i]); readln; {读编码数组B}
        for i:=0 to n-1 do P[i]:=i; {建立取数数列P}
        for i:=n-1 downto 0 do  {由编码数组B逆向求原数组A}
          begin A[i]:=P[B[i]];  {A[i]为数组P中第B[i]号元素}
            for j:=B[i] to i-1 do P[j]:=P[j+1];{从P数组中删去P[B[i]]}
          end;
        write('A=');
        for i:=0 to n-1 do write(A[i]:5);writeln; {输出数组A}
      end;
  end;
end.
第二章  算法应用

一、穷举搜索法

    穷举搜索法是穷举所有可能情形，并从中找出符合要求的解。
    穷举所有可能情形，最直观的是联系循环的算法。
    [例]找出n个自然数(1,2,3,…,n)中r个数的组合。例如，当n=５,r=3时，所有组合为：
          ５      ４      ３
          ５      ４      ２
          ５      ４      １
          ５      ３      ２
          ５      ３      １
          ５      ２      １
          ４      ３      ２
          ４      ３      １
          ４      ２      １
          ３      ２      １
           total=10     {组合的总数}

    [解]n个数中r的组合，其中每r 个数中，数不能相同。另外，任何两组组合的数，所包含的数也不应相同。例如，５、４、３与３、４、５。为此，约定前一个数应大于后一个数。
    将上述两条不允许为条件，当r=3时，可用三重循环进行搜索。
    ［程序］
      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.
    或者
      Program  zuhe12;
      const n=5;r=3;
      var  i,j,k,t:integer;
      begin  t:=0;
        for  i:=n  downto  r  do
          for  j:=i-1  downto  r-1  do
            for  k:=j-1  downto  1  do
                begin t:=t+1;writeln(i:3,j:3,k:3);end;
        writeln('total=',t);
      end.
    这两个程序，前者穷举了所有可能情形，从中选出符合条件的解，而后者比较简洁。但是这两个程序都有一个问题，当r变化时，循环重数改变，这就影响了这一问题的解，即没有一般性。
    但是，很多情况下穷举搜索法还是常用的。
二、递归法

    递归法也是常用的方法。
   ［例］仍以前节例题为例，找n个数的r个数的组合。要求：
    输入：n,r=5  3
    输出：５      ４      ３
          ５      ４      ２
          ５      ４      １
          ５      ３      ２
          ５      ３      １
          ５      ２      １
          ４      ３      ２
          ４      ３      １
          ４      ２      １
          ３      ２      １
           total=10     {组合的总数}
    ［解］分析所提示的10组数。首先固定第一位数（如５），其后是在另４个数中再“组合”２个数。这就将“５个数中３个数的组合”推到了“４个数中２个数的组合”上去了。第一位数可以是n    r(如５    3)，n个数中r个数组合递推到n-1个数中r-1个数有组合，这是一个递归的算法。即：
    Procedure   comb(n,r:integer);
    var  i:integer;
    begin  for  i:=n  downto  r  do
      begin  {固定i的输出位置}
        comb(i-1,r-1);  {原过程递推到i-1个数的r-1个数组合}
      end;
    end;
    再考虑打印输出格式。
    ［程序］
    Program  zuhe2;
    var  k,n,r:integer;
    Produrce   comb(n,r:integer);
    var  i,temp:integer;
    begin  for  i:=n  downto  r  do
      if  (i<>n)and(k<>r)  then    {k为过程外定义的}
        begin for temp:=1 to  (k-r)*3  do  write('  '); {确定i的输出位置}
        end;
      write(i:3);
      if i>1 then comb(i-1,r-1);  {递推到下一情形}
      else writeln;
    end;
    Begin {main}
     write('n,r=');readln(n,r);
     if  r>n  then
       begin  writeln('Input n,r error!');halt; end;
     comb(n,r);  {调用递归过程}
   End;

三、回溯法

     回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
    ［例］再以前例说明，找n个数中r个数的组合。
    ［解］将自然数排列在数组A中：
      A[1]    A[2]    A[3]
       5       4       3
       5       4       2
          …
       3       2       １
    排数时从A[1]    A[2]     A[3]，后一个至少比前一个数小１，并且应满足ri+A[ri]>r。若ri+A[ri]≤r就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为１，也应作一次回溯（若不回，便由上述回溯条件处理）。

    ［程序］
     program  zuhe3;
     type  tp=array[1..100] of integer;
     var  n,r:integer;

     procedure  comb2(n,r:integer;a:tp);
     var  i,ri:integer;
     begin  ri:=1;a[1]:=n;
       repeat  
        if  ri<>r  then   {没有搜索到底}
          if  ri+a[ri]>r  then    ｛是否回溯｝
            begin  a[ri+1]:=a[ri]-1;
              ri:=ri+1;
            end
          else
            begin  ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
        else
          begin  for j:=1 to r do write(a[j]:3);writeln; {输出组合数}
            if  a[r]=1  then  {是否回溯}
              begin  ri:=ri-1; a[ri]:=a[ri]-1;end; {回溯}
            else  a[ri]:=a[ri]-1;  {递推到下一个数｝
          end;
       until  a[1]<>r-1;
     end;

     begin {MAIN}
       write('n,r=');readln(n,r);
       if  r>n  then
         begin  writeln('Input n,r error!');halt; end
       comb2(n,r);
     end.

第三章  综合题解

综合测试题（一）

1、寻找数：求所有这样的三位数，这些三位数等于它各位数字的立方和。
   例如，153＝13 ＋53 ＋33 。
    [解]穷尽三位数，用一个循环语句。其数码可用“模取”运算MOD完成。
   [程序]
    PROGRAM lifang;
    uses crt;
    var i,a,b,c:integer;
    begin
      clrscr;
      for i:=100 to 999 do
        begin c:=i mod 10; ｛取个位数｝
          b:=(i div 10) mod 10; ｛取十位数｝
          a:=i div 100;  ｛取百位数｝
          if i=a*a*a+b*b*b+c*c*c then writeln(i:6);
        end;
    end.    

２、最小自然数：求具有下列两个性质的最小自然数n：
    (１)n的个位数是６；
    (２)若将n的个位数移到其余各位数字之前，所得的新数是n的４倍。
    [解]仍用穷举法寻找，当找到一个符合条件者便停止。“找到便停止”的重复，宜采用repeat－until循环。
    由于不知道n是几位数，个位数移到前面去应借助一个指定位数的数。设为e。
    [程序]
     program minnum;
     var  n,e:integer;
     begin e:=1;n:=1;
       repeat  e:=10*e;
         repeat n:=n+1;
         until not((n=e)or((10*n+6)*4=(6*e+n)));
       until ((10*n+6)*4<>6*e+n);
       writeln(10*n+6);
     end.

３、找素数：寻找160以内的素数，它的倒序数（如123的倒序数为321）、数码和、数码积不是素数便是１。
    [解]倒序数、数码和、数码积都需对原数分解，分解后再查它们是否符合条件。
    [程序]
    program sushu;
    uses crt;
  var i,j,n,s,p,f:integer;
    function cond(k:integer):boolean;
      var j:integer;b:boolean;
    begin  b:=true; {为1时表示k为素数}
      if k<>1 then for j:=2 to k-1 do if k mod j=0 then b:=false;
      if k=0 then cond:=false else cond:=b;
    end;
    begin {MIAN}  clrscr;
      for i:=2 to 160 do
      if cond(i) then
        begin  j:=i;n:=0;s:=0;p:=1;
          while j<>0 do
            begin f:=j mod 10;
              j:=j div 10;
              n:=n*10+f;｛计算倒序数｝
              s:=s+f;   ｛计算数码和｝
              p:=p*f;   计算数码积
            end;
          if (cond(n))and(cond(s))and(cond(p)) then write(i:5);
        end;
      writeln; readln
    end.

４、完全平方数：寻找具有完全平方数，且不超过７位数码的回文数。所谓回文数是指这样的数，它的各位数码是左右对称的。例如121、676、94249等。
    [解]判断一个数是否回文数，可以将其转化成字符判断。也可以分解数，所谓分解就是将数的后半段倒置后再与前半段比较。这里采用分解的方法，其函数为symm。
    [程序]
     program wcpfs;
     uses crt;
     var i:longint; s:longint;
     function symm(n:longint):boolean;
     var i,j,k:longint; m:longint;
     begin i:=n;j:=1; {计算n的位数}
       repeat  j:=j+1;i:=i div 10;until (i<=9)and(i>=0);
       k:=j div 2;m:=0;
       for i:=1 to k do  {分解前后两位数}
         begin m:=m*10+(n mod 10);n:=n div 10; end;
      if j mod 2=1 then ｛n是奇数位,中间位不要｝n:=n div 10;
      symm:=(m=n);
    end;
    begin {MAIN}  clrscr;
      for i:=11 to round(sqrt(999999999)) do begin if symm(i*i) then writeln(i*i); end;
    end.

５、成等差的素数：寻找６个成等差级数且小于160的素数。
    [解]设级数为：n，n-d，n-2d，n-3d，n-4d，n-5d。若这６个数全为素数，则为要求的解。这里d、n均是要寻找的。仍用穷尽法，d最大可为33。判断素数函数为isprime。
    [程序]
     PROGRAM dcss(input,output);
   var n,d:integer;
     FUNCTION isprime(m:integer):integer;  ｛判断素数函数｝
     var b,i:integer;
       begin b:=1;
         if m<=0 then b:=0
         else for i:=2 to trunc(sqrt(m)) do if m mod i=0 then b:=0;
         isprime:=b;
       end;
       begin   {main}
         for d:=1 to 31 do  for n:=160 downto 7 do
            if (isprime(n)=1)and(isprime(n-d)=1) then
              if (isprime(n-2*d)=1)and(isprime(n-3*d)=1) then
                  if (isprime(n-4*d)=1)and(isprime(n-5*d)=1) then
                     writeln(n:6,n-d:6,n-2*d:6,n-3*d:6,n-4*d:6,n-5*d:6);
      end.

６、取数列：取｛2m ，3n ｜m>=1，n>=1｝中由小到大排列的前70项数。
    [解]这个数的集合事实上存在两个数列：一个是2m ，另一个是3n 。若依次从两数列中取出小的进入新的数列，该新数列便为所求（这里不用数组，而直接打印输出）。
    [程序]
    program mn23;
    const n=70;
    var m2,n3:real;   k:integer;  f:text;
    begin
      assign(f,'exmn.txt');rewrite(f); {输出结果在文件exmn.txt中}
      m2:=2;n3:=3;k:=0;
      while k<n do
        begin  if m2<n3 then begin writeln(f,m2:40:0);m2:=m2*2; end
          else  begin writeln(f,n3:40:0);n3:=n3*3; end;
          k:=k+1;
        end;
      close(f);
    end.

７、发奖章：运动会连续开了n天，一共发了m枚奖章，第一天发１枚并剩下(m-1)枚的1/7，第二天发２枚并剩下的1/7，以后每天按此规律发奖章，在最后一天即第n天发了剩下的n枚奖章。问运动会开了多少天？一共发了几枚奖章？
    [解]由于题目涉及m-1的1/7，于是m-1应是7的倍数，即m=7x+1。递推x，寻找m、n。
    [程序]
     PROGRAM sport;
     var m,n,x,b:integer;
     begin x:=0;
       repeat x:=x+1;m:=7*x+1;n:=1;b:=1;
         while (m>n) and (b=1) do
         begin m:=m-n;
           if (m mod 7=0) then m:=(m div 7)*6 else b:=0;n:=n+1;
         end;
       until b=0;
       writeln('n=',n,'    m=',7*x+1);
     end.

８、猜名次：五个学生A、B、C、D、E参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如１与２，或者２与３等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？答案为：E、D、A、C、B。乙猜对C、B为最后两名，两对相邻为（D、A）、（C、B））。
    [解]设五名选手A、B、C、D、E的编号分别为1、2、3、4、5。用五个变量c1、c2、c3、c4、c5标记第一名至第五名。算法仍用穷尽法。其中处理相邻问题用一个两位数表示，即DA、AE、EC、CB分别用41、15、53、32表示，并按两位数比较判断相邻问题。
    [程序]
     program mingci;
     var c1,c2,c3,c4,c5,s1,s2,t:integer;
     begin for c1:=2 to 5 do
         for c2:=1 to 5 do
           if (c2<>2)or((c2-c1)<>1) then
             for c3:=1 to 5 do
               if (c3<>3)or((c3-c2)<>1) then
                 for c4:=1 to 5 do
                   if (c4<>4)or((c4-c3)<>1) then
                     for c5:=1 to 4 do
                       if (c5-c4)<>1 then
                          begin s2:=0;
                            if c1=4 then s2:=s2+1;
                            if c2=1 then s2:=s2+1;
                            if c3=5 then s2:=s2+1;
                            if c4=3 then s2:=s2+1;
                            if c5=2 then s2:=s2+1;
                            s1:=0;
                            t:=10*c1+c2;
                            if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
                            t:=10*c2+c3;
                            if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
                            t:=10*c3+c4;
                            if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
                            t:=10*c4+c5;
                            if (t=41)or(t=15)or(t=53)or(t=32) then s1:=s1+1;
                            if (s1=2)and(s2=2) then
                            writeLn(c1:3,c2:3,c3:3,c4:3,c5:3);
                          end;
     end.
９、填自然数：设有如图所示的3n＋2个球互连，将自然数1－3n＋2分别为这些球编号，使如图相连的球编号之差的绝对正好是数列1，2，……，3n+2中各数。
          ②─⑥                  ②─⑨─⑤            ②─⑿─⑤─⑨
          │  │                  │  │  │            │  │  │  │
      ①─⑧─④─⑤          ①─⑾─④─⑧─⑦    ①─⒁─④─⑾─⑦─⑧
          │  │                  │  │  │            │  │  │  │
          ③─⑦  (n=2)           ③─⑩─⑥  (n=3)      ③─⒀─⑥─⑩  (n=4)
    [解]填自然数的一种算法是：
    (1)先自左向右，第１列中间１个填数，然后第２列上、下２个填数，每次２列；但若n是奇数，最后１次只排第１列中间１个数。
    (2)自右向左，先右第１列中间填数；若n是奇数，再右第２列中间填数。然后依次右第１列上、下２个填数，再右第２列中间１个填数，直到左第２列为止。
    [程序]
     program ziyangshu;
     uses crt;
     const size=25;
     var a:array[0..2,0..size] of integer; i,k,m,n:integer;
     begin  clrscr;write('Input then n:');readln(n);k:=1;
       for i:=0 to n div 2 do
         begin a[1,2*i]:=k;k:=k+1;
           if ((i=n div 2)and(n mod 2=1)or(i<n div 2)) then
             begin a[0,2*i+1]:=k;k:=k+1; a[2,2*i+1]:=k;k:=k+1; end;
         end;
       if n mod 2=1 then begin a[1,n+1]:=k;k:=k+1;m:=n end
       else m:=n+1;
       writeln(m);
       for i:=0 to n div 2 do
         begin a[1,m-2*i]:=k;k:=k+1; writeln(1,' ',m-2*i,' ',k);
           a[0,m-2*i-1]:=k;k:=k+1;  a[2,m-2*i-1]:=k;k:=k+1;
         end;
       write(' ':3);
       for i:=1 to n do write(a[0,i]:3);writeln;
       for i:=0 to n+1 do write(a[1,i]:3);writeln;write(' ':3);
       for i:=1 to n do write(a[2,i]:3);writeln;
     end.

[em6]好，支持到底！！

这位高手讲得真好,我花了好长时间看了一下,学了好多东西,谢谢你了啊

非常遗憾——网上早就有了！！