第一章 只考一题

P19 其他说明 

【例】求二个正整数的最大公约数。

main( )

{int a,b,t,i;

 input (a,b);

 t=1；          //变量t是为累乘因数而设置的；

 for (i=2; i<=a and i<=b; i++)  //“枚举”可能的公约数

    while  (a mod i=0 and b mod i=0 )

    //“试”i是否为公约数

     {t=t*i;

      a=a/i;

      b=b/i;}

 print(t ,“is maximal  common divisor”);

}

 

第二章

时间复杂度 （必考）P42

递归算法    效率高 P43

 

fact(int n)

                  { if (n=0 or n=1)

                        return (1);

                    else

                        return (n*fact(n-1));

                   }

 

 

第三章 重点考

P53 完数

main( )

{int  i,k,j,s,a[20];

for(i=1;i<=1000;i++)

  {s=1;                       

  for(j=2;j<i;j++)

   if (i  mod  j)==0)

     {s=s+j;

      a[k]=j;

      k++;}

  if(i==s)

      {print(s, “it’s  factors are :”,1);

       for(j=0;i<k;j++)

          print(“,”,a[k]);

       }

  }

 }

P56 规律图形

【例4】编写算法：打印具有下面规律的图形。

             1             

             5  2          

             8  6  3       

            10  9  7  4  

main( )

{int i,j,a[100][100],n,k;

 input(n);

 k=1;

for(i=1;i<=n;i=i+1)

  for( j=1;j<=n+1-i;j=j+1)

   {a[i-1+j][j]=k;

    k=k+1;}

for(i=1;i<=n;i=i+1)

  {print( “\n”);

   for( j=1;j<=i;j=j+1)

print(a[i][j]);

  }

}

 

P58 汉罗塔 必考

hanoi (int n,char a,char b,char c)

 / a,b,c 初值为”A”,”B”,”C”/

      1) if(n>0)         

      2) hanoi(n-1,a,c,b);

      3) 输出 “ Move dise” ,n.”from pile”,a,” to”b);

      4) haboi(n-1,c,b,a);

      5) endif }

 

P61 从低位到高位逐位输出

f1(n)                     

{while(n>=10)

       { print( n mod 10);

         n=n\10;}

print(n);

}

 

P73 数字翻译称英文

main( )

 {int i,a[10], ind;    long num1,num2;

  char eng[10][6]={“zero”,”one”,”two”,”three ”,” four”,

 ” five”,”six”,”seven”,“eight”,”nine”};

  print(“Input a num”);

  input(num1);    num2=num1;  ind =0;

while (num2<>0)

{a[ind]=num2 mod 10;  ind= ind +1;  num2=num2/10; }

  print(num1, “English_exp:”, eng[a[ind-1]]);

for( i=ind-2;i>=0;i=i-1)

    print(“-”，eng[a[i]]);

}

 

P75 找钱问题

main( )

{int  i,j,x,y,z,a,b[7]={0,50,20,10,5,2,1},s[7];

input(x,y);

z=y-x;

for(i=1;i<=6;i=i+1)

     {a=z\b[i];    s[i]=a;      z=z-a*b[i];}

 print(y,”-”x,”=”,z:);

 for(i=1;i<=6;i=i+1)

   if (s[i]<>0)

        print(b[i], “----”, s[i]);

}

 

P79 大整数存储

P81 趣味矩阵

【例1】            编程打印形如下规律的n*n方阵

例如下图：使左对角线和右对角线上的元素为0,它们上方的元素为1,左方的元素为2,下方元素为3,右方元素为4,下图是一个符合条件的阶矩阵。
                         0   1  1  1  0
                         2   0  1  0  4
                         2   2  0  4  4
                         2   0  3  0  4
                         0   3  3  3  0

main( )

{int i,j,a[100][100],n;

 input(n);

 for(i=1;i<=n;i=i+1)

   for(j=1;j<=n;j=j+1)

      {if (i=j  or i+j=n+1)  a [i][j]=0;

       if (i+j<n+1 and i<j)  a [i][j]=1;

       if (i+j<n+1 and i>j)  a [i][j]=2;

       if (i+j>n+1 and i>j)  a [i][j]=3;

       if (i+j>n+1 and i<j)  a [i][j]=4;}

for(i=1;i<=n;i=i+1)

  {print( “换行符”);

  for( j=1;j<=n;j=j+1)

        print(a[i][j]);

  }

}

 

【例2】            螺旋阵：任意给定n值，按如下螺旋的方式输出方阵：

n=3    输出：   1  8  7

                2    9  6

                3    4  5

n=4    输出：  1  12  11  10

                2    13  16  9

                3    14  15  8

      4   5   6  7

main( )

{int i,j,a[100][100],n,k;

 input(n);     k=1;

for(i=1;i<=n/2;i=i+1)

 {for( j=i;j<=n-i;j=j+1) { a [j][i]=k；  k=k+1;}    /左侧/

  for( j=i;j<=n-i;j=j+1) {a [n+1-i][j]=k;  k=k+1;} /下方/

  for( j= n-i+1;j>=i+1;j=j-1){a[j][n+1-i]=k;k=k+1;} /右侧/

  for( j= n-i+1;j>=i+1;j=j-1) {a[i][j]=k;   k=k+1;} /上方/

  }

if (n mod 2=1)

  {i=(n+1)/2;   a[i][i]=n*n;}

for(i=1;i<=n;i=i+1)

  {print(“换行符”);

   for( j=1;j<=n;j=j+1)

       print(a[i][j]);

  }

}

 

P92 开灯问题

【例2】开灯问题：有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉；2号同学将编号为2的倍数的灯都打开；3号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。问经n个同学操作后，哪些灯是打开的？

main( )

{ int  n,a[1000],i,k;

  print(“input a number”);

 input(“%d”,&n);

  for( i=1;i<=n;i++)

     a[i]=0;

  for( i=2;i<=n;i++)

   { k=1;

     while ( i*k<=n)

     {  a[i*k]=1-a[i*k];

        k=k+1;}

   }

  for( i=1;i<=n;i++)

  print( a[i]);

}

 

P97 最小公倍数

【例4】编写算法，求任意三个数的最小公倍数。

main( )

 { int x1,x2,x3,t=1,i,flag,x0;

   print(“Input 3 number:”);   input(x1,x2,x3);

   x0=max(x1,x2,x3);

   for (i=2;i<=x0;i=i+1)

    {flag=1;

     while(flag=1)

      { flag=0;

        if (x1 mod i=0)  {x1=x1/i; flag=1;}

        if(x2 mod i=0)   {x2=x2/i; flag=1;}

        if(x3 mod i=0)   {x3=x3/i; flag=1;}

        if (flag=1)  t=t*i;  }//while结束符

          x0=max(x1,x2,x3)   }//for结束符

        print(“The  result  is ”,t);

     }

max(int x,int y,int  z )

 { if(x>y&&x>z)         return(x);

   else if(y>x and y>z)  return(y);

   else  return(z);

  }

 

P99 信息数字化  估计编程或填空，后面例子看下。

例1】警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中
    a说：“我不是小偷。”
    b说：“c是小偷。”
    c说：“小偷肯定是d。”
    d说：“c在冤枉人。”
现在已经知道四个人中三人说的是真话，一人说的是假话，
问到底谁是小偷？

main( )

{ int x;

  for(x=1;x<=4;x++)

   if((x<>1)+(x=3)+(x=4)+(x<>4)==3)

   print(chr(64+x),“is a thief .”);

 }

运行结果：

   c  is  a  thief .

【例2】三位老师对某次数学竞赛进行了预测。他们的预测如下：
       甲说：学生A得第一名，学生B得第三名。
       乙说：学生C得第一名，学生D得第四名。
       丙说：学生D得第二名，学生A得第三名。
竞赛结果表明，他们都说对了一半，说错了一半，并且无并列名次，试编程输出A、B、C、D各自的名次。

main( )

{int a,b,c,d;

for( a=1;a<=4;a=a+1)

 for( b=1;b<=4;b=b+1)

  if (a<>b)

    for( c=1;c<=4;c=c+1)

      if (c<>a    and   c<>b)

       {d=10-a-b-c;

       if  (d<>a   and  d<>b   and  d<>c )

       if(((a=1)+(b=3))=1 and ((c=1)+(d=4))=1 and ((d=2)+(a=3))=1) 

           print( “a,b,c,d=”,a,b,c,d);

       }

  }

 

 

第四章 重点考

P124 兔子繁殖

问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。

main( )

{ int i,a=1,b=1;

  print(a,b);

 for(i=1;i＜=10;i++)

  { c=a+b;

    print (c);

    a=b;

    b=c；

   }

 }

 

P126 最大公约数 必考

main（）

{ int a, b;

  input(a,b);

  if(b=0) 

     {print(“data error”);

       return;}

  else

   { c = a mod b;

     while c<>0

       { a=b;

         b=c;

         c=a mod b;}

    } 

  print(b);

}

 

P133 百钱百鸡 估计编程

【例1】百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?

main( )
{ int x,y,z;
 for(x=1;x<=20;x=x+1)
    for(y=1;y<=34;y=y+1)
      for(z=1;z<=100;z=z+1)
          if(100=x+y+z and 100=5*x+3*y+z/3)
             {print(the cock number is",x)；

        print(the hen number is", y)；

print(the chick number is "z);}
}

 

P134 数字迷 估计填空或编程

【例2】解数字迷：        A  B  C  A  B

                    ×                 A   

                       D  D  D  D  D  D

main（ ）

{ long  A,B,C,D,E,E1,F,G1,G2,i;

  for(A=3;  A<=9;  A++)

  for(B=0;  B<=9;  B++)

  for(C=0;  C<=9;  C++)

 { F=A*10000+B*1000+C*100+A*10+B;

    E=F*A； E1=E;  G1=E1 mod 10;

    for(i=1;  i<=5;  i++)

      { G2=G1; E1=E1/10;     G1= E1 mod 10;

         if(G1<>G2 )   break;     }

       if(i=6)    print( F，”*”，A，”=”，E);

      }

  }

 

 

P136 公倍数

【例3】狱吏问题

main1( )

{int *a,i,j,n;

 input(n);

 a=calloc(n+1,sizeof(int));

 for (i=1; i<=n;i++)

    a[i]=1;

 for (i=1; i<=n;i++)

  for (j=i; j<=n;j=j+i)

     a[j]=1-a[j];

 for (i=1; i<=n;i++)

 if (a[i]=0)     print(i,”is  free.”);

}

 

P141/P151 一组数据最大最小、一组数第二小  必考

算法2 递归求取最大和最小元素

float a[n];

maxmin （int  i, int j ,float &fmax, float &fmin）{int mid;  float lmax, lmin, rmax, rmin;

if (i=j)  {fmax= a[i];  fmin=a[i];}

else if (i=j-1)

     if(a[i]<a[j])  { fmax=a[j]；fmin=a[i];}

        else {fmax=a[i]; fmin=a[j];}

else     {mid=(i+j)/2;
                   maxmin （i，mid，lmax，lmin）;
                   maxmin （mid+1，j，rmax，rmin）;
                  if(lmax>rmax)    fmax=lmax;

          else        fmax=rmax;
                   if(lmin>rmin)     fmin=rmin;

           else        fmin=lmin;
}

【例5】选择问题1      求一组数的第二小的数。 

float  a[100];

main( )

{ int n;           float  min2;

  input(n);

 for (i=0;i<=n-1;i=i+1)    input(a[i]);

min2=second(n);

print(min2);  }

second（int n）

 {float  min2,min1;

  two(0,n-1, min2, min1);

   return  min2;}

two（int  i, int j，float  &fmin2, float &fmin1）
{ float  lmin2,lmin1,rmin2,rmin1;      int mid;

  if  （i=j）   fmin2=fmin1=a[i]
  else if (i=j-1)

       if(a[i]<a[j])    { fmin2=a[j]；fmin1=a[i];}

       else        {fmin2=a[i];  fmin1=a[j];}

  else 

         {mid=(i+j)/2;
           two（i，mid，lmin2，lmin1）;
           two（mid+1，j，rmin2，rmin1）;
           if (lmin1<rmin1)

               if (lmin2<rmin1  && (i!=mid))                                        { fmin1=lmin1;fmin2=lmin2;}

               else   {fmin1=lmin1; fmin2=rmin1;}

          else

              if ( rmin2<lmin1 && (mid+1!=j))  { fmin1=rmin1;fmin2=rmin2;}

              else           {fmin1=rmin1; fmin2=lmin1;}

          }}

 

P163 币种统计

【例4】币种统计问题

    某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。

main( )

 { int i,j,n,GZ,A；

   int B[8]={0,100,50,20,10,5,2,1},S[8];

   input(n);

   for(i=1;i<=n;i++)

     { input(GZ);

       for(j=1,j<=7;j++)

          { A=GZ/B[j];

            S[j]=S[j]+A;

            GZ=GZ-A*B[j];}

        }

   for(i=1;i<=7;i++)

        print(B[i], “----”, S[i]);

  }