设为首页 | 加入收藏夹

1993年美国计算机程序设计资格赛试题答案(解答)

2012-6-2 18:19:44 作者:计算机基础知识试题 录入:应序康 访问:7011 次 被顶:1 次 字号:【
摘要:第一题: 分数变小数 (1 ) 解题思路本题可以模仿手算除法的形式,重复地进行求商和余数的运算,直到余数为 0 或出现循环节为止。(2 ) 参考程序Const Max = 100; {小数点后最大位数 }Var Left , Digit :...
第一题: 分数变小数
    (1 ) 解题思路
本题可以模仿手算除法的形式,重复地进行求商和余数的运算,直到余数为 0 或出现
循环节为止。
(2 ) 参考程序
Const Max = 100;                                       {小数点后最大位数               }
Var Left , Digit : Ar ray [0 . .Max ] Of Word;       {记录每次的余数和商           }
    n, d   : Word;
    q, Top: Word;                                           {q为循环节的位置   }
Procedure Init ;                                                   {读入数据     }
Begin
Write(’ ENTER N , D:’ ) ;
Readln( n, d) ;
End ;
Procedure Calc;                                                   {计算         }
Var i : Word;
Begin
Digit [ 0]∶ = n Div d;
Left [ 0] ∶ = n Mod d;
Top ∶ = 0;
q ∶ = 0 ;                                                                 {初始化商和余数                 }
· 8 3 ·While Left [ Top] < > 0 Do                                           {余数不为 0 则循环          }
  Begin
    Inc ( Top) ;
    Digit [ Top]∶ = ( Left [ Top -1] * 10) Div d;
    Left [ Top] ∶ = (Left [ Top-1 ] * 10 ) Mod d;
    For i∶ = 0 To Top-1 Do
    I f Left [ Top] = Left [ i ] Then
      Begin
        q ∶ = i + 1;
        Exit ;                                                     {如果出现循环节则退出    }
      End;
  End;
End ;
Procedure Print ;                                                   {打印结果     }
Var i : Word;
Begin
Write( n, ’ / ’ , d, ’ = ’ ) ;
If Digit [0] < > 0 Then Write (Digit [ 0] ) ;
If Top > 0 Then Write (’.’ ) ;
For i ∶ = 1 To Top Do
  Begin
  I f i = q Then Write (’ (’ ) ;
  Write(Digit [ i ] ) ;
  End;
If q > 0 Then Write(’ )’ ) ;
Writeln;
End ;
Begin
Init ;                                                                   {读入数据                       }
Calc ;                                                                   {计算   }
Print ;                                                                 {打印结果                       }
End .
(3 ) 运行结果
ENTER N ,D: 11 59
11 / 59 = .(1864406779661016949152542372881355932203389830508474576271)
第二题: 质数竖式
(1 ) 解题思路
· 9 3 ·此题比较简单,只需对两个乘数进行循环,然后判断竖式中的数是否满足要求。需注
意的一点是:乘积可能超出整型的范围,需用长整型来计算。
(2 ) 参考程序
Var Num : Set Of Byte;                                       {数字集合           }
    n     : Word; {竖式的数目 }
Procedure Init ; {读入数据并初始化 }
Var St : St ring;
    i   : Word;
Begin
Write(’ Enter a set of digits:’ ) ;
Readln(St ) ; {以字符串形式读入 }
Num ∶ = [ ]
For i ∶ = 1 To Length (St ) Do
  Include(Num, Ord(St [ i] )-Ord(’ 0’ ) ) ;
n ∶ = 0 ;
End ;
Function Ok(x :Longint ) :Boolean ; {判断 x的每位数是否都 }
{在集合中 }
Begin
Ok ∶ = False ;
While x > 0 Do
  Begin
  I f Not ( ( x Mod 10 ) In Num) Then Exit ;
  x ∶ = x Div 10;
  End;
Ok ∶ = True ;
End ;
Procedure Calc;                                                   {找出满足条件的竖式             }
Var i , j : Longint ;
Begin
For i ∶ = 111 To 999 Do
  If Ok( i ) Then
  For j ∶ = 11 To 99 Do                                       {对两个乘数进行循环 }
    If Ok( j ) And Ok( ( j Mod 10) * i) And Ok( ( j Div 10) * i )
· 0 4 ·    And Ok( i * j ) Then {如果满足条件则打印 }
      Begin
      Inc( n) ;
Writeln(’<’ , n, ’ > ’ ) ;
Writeln( i: 6) ;
Writeln(’X’ , j :4 ) ;
Writeln(’ -- - -- - --’ ) ;
Writeln( ( j Mod 10) * i :6 ) ;
Writeln( ( j Div 10 ) * i :5) ;
Writeln(’ -- - -- - --’ ) ;
Writeln( i * j :6) ;
      End;
Writeln(’ The number of unique solutions = ’ , n) ;
End ;
Begin
Init ; {读入数据并初始化 }
Calc ; {找出满足条件的竖式 }
End .
(3 ) 运行结果
Enter a set of digits : 2357
〈 1 〉
7 7 5
× 3 3
2 3 2 5
2 3 2 5
2 5 5 7 5
The number of unique solutions = 1
第三题: 6×6棋子挑战
(1 ) 解题思路
本题与八皇后问题本质相同,只需用简单的回溯法即可解决。
(2 ) 参考程序
Var a   : Array[1 . .6] Of Byte;                         {记录每个棋子列的位置  }
  Num: Word;                                                     {解的总数     }
Procedure Find( k:Word) ;                                     {递归寻找           }
· 1 4 ·Var i , j : Integer ;
Begin
If k = 7 Then Begin
              For i ∶ = 1 To 6 Do
                Write( a [ i ] :2 ) ;
              Writeln;
              Inc( Num) ;
            End
Else
For i ∶ = 1 To 6 Do
  Begin
  a[ k]∶ = i;
  For j ∶ = 1 To k-1 Do
    If ( i = a[ j ] ) Or (Abs ( i -a [ j] ) = k-j ) Then
      Begin
        a [ k]∶ = 0 ;
        Break;                                                     {判断是否与其它棋子同行   }
      End;                                                       {同列或同对角线                 }
  I f a[ k ] > 0 Then Find( k + 1 ) ;                               {递归下一层         }
  End;
End ;
Begin
Num ∶ = 0;
Find(1) ;                                                         {递归查找 }
Writeln(’ THERE ARE ’ , Num, ’SOLUTIONS TO THE’ ) ;
Writeln(’ 6 * 6 CHECKER CHALLENGE .’ ) ;
End .
(3 ) 运行结果
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
5 3 1 6 4 2
THERE ARE 4 SOLUTIONS TO THE
6 * 6 CHECKER CHALLENGE .
第四题: 跳棋难题
(1 ) 解题思路
对于此类问题,一般的算法是采用宽度优先搜索,可以求得最少步数。但是当 n 值很
· 2 4 ·大时,这种算法不但在时间上变得很慢,而且由于宽度搜索需要记录所有状态,在空间上
也会溢出。由于此题并没有要求最少步数,所以我们尝试找出一个移动的规律来解此题。
从 n = 3 来考虑,观察下面的移动方法:
WWW B B B
WW W B B B
WW B W B B
WW B W B B
WW B B W B
W B W B W B
W B W B W B
B W W B W B
B W B W W B
B W B W B W ( * )
B W B W B W
B W B B WW
B B W B WW
B B W B WW
B B B W WW
B B B WWW
    我们可以发现开始时,在移动一个棋子之后,总是跳另一种颜色的棋子,直至没有跳
的可能;然后再移动另一种颜色的棋子,再跳这种颜色的棋子直至不能跳为止。这样交替
进行到一种 “中间状态” (上面标 * 的状态) ,在这种状态中,两种颜色的棋子交错排列。以
后的步骤变成移动一个棋子,再跳同一种颜色的棋子;再移另一种颜色的棋子,再跳另一
种颜色的棋子,直至到达最终状态为止。找到了以上的规律,我们的编程就变得很简单,
而且在时间、 空间上均不成问题。
(2 ) 参考程序
Var n : Word;                                                     {跳棋的数目 }
    State ,Goal : String ; {初始及最终状态 }
Procedure Init ; {读入 n并初始化数据 }
Var i : Word;
Begin
Write(’ Enter N:’ ) ;
Readln( n) ;
State∶ = ’’ ;
Goal ∶ = ’’ ;
For i ∶ = 1 To n Do
· 3 4 ·  Begin
State∶ = ’ W’+ State +’ B’ ;
Goal∶ =’ B’+ Goal + ’ W’ ;
  End; {求出初始及最终状态 }
End ;
Procedure Find; {找出移动步骤 }
Const Chess : Ar ray [ - 1 . . 1 ] Of Char = (’ W’ ,’’ ,’ B’ ) ;
Var Flag : Boolean; {记录是否到 “中间状态” }
    What : - 1 . . 1; {记录该移动哪个棋子 }
    p     : Ineger ; {记录空格的位置 }
Begin
Flag ∶ = False ;
What∶ = - 1 ;
p ∶ = n + 1;
Writeln(State) ; {初始化变量 }
While State < > Goal Do {如果未到最终状态 }
  Begin
I f Not ( p + What In [ 1 . . 2 * n + 1] ) Then {如果到 “中间状态” }
Begin
Flag ∶ = True ;
What∶ = - What ;
End;
State [p]∶ = State [p + What ] ; {移动一个棋子 }
p ∶ = p + What ;
State [p]∶ = ’’ ;
Writeln(State) ;
I f Not Flag Then What∶ = - What ;
While ( p + 2 * What < = 2 * n + 1) And ( p + 2 * What > 0)
And (State [p + What ] = Chess[ - What ] )
And (State [p + 2 * What ] = Chess[What ] ) Do
Begin {反复跳棋子}
State[ p]∶ = State[ p + 2 * What ] ;
p ∶ = p + 2 * What ;
State[ p]∶ = ’’ ;
Writeln(State ) ;
End;
· 4 4 ·I f Flag Then What∶ = - What ;
End;
End ;
Begin
Init ; {读入 n并初始化数据 }
Find; {找出移动方法 }
End .
(3 ) 运行结果
Enter N: 4
WWWW B B B B
WWW W B B B B
WWW B W B B B
WWW B W B B B
WWW B B W B B
WW B W B W B B
W W B W B W B B
W B W W B W B B
W B W B W W B B
W B W B W B W B
W B W B W B W B
W B W B W B BW
W B W B B W BW
W B B W B W BW
B W B W B W BW
B W B W B W BW
B B W W B W BW
B B W B W W BW
B B W B W B W W
B B W B W B WW
B B W B B WWW
B B B W B WWW
B B B W B WWW
B B B B W WWW
B B B B WWWW
第五题: 全部拉丁方阵
(1 ) 解题思路
关于 n 阶拉丁方的总数问题,至今还没有数学公式甚至是递推公式,只能用计算机搜
索来求得。但是我们在搜索时可以采取一些优化来提高效率。我们发现,将一个拉丁方
的任意两行或任意两列交换位置,所形成的新的方阵仍然是一个拉丁方。题目中已经要
· 5 4 ·求第一行的数字为 1 2 3 4 5 … N,所以我们不能交换任意两列。但是我们可以交换除第
一行外的任意两行来得到新的拉丁方,即规定第一列的数字也为 1 2 3 4 5 … N。这样我
们再对其余的每个位置的数字进行搜索,边搜索边判断是否同一个数字是否在同行或同
列中出现。所得的数目再乘以( n - 1 ) ! 即为我们所要求的总数。
(2 ) 参考程序
Var n     : Word;                                                   {拉丁方的大小 }
    h, v : Array [ 1 . . 6 ,1 . . 6] Of Byte ;                 {某数在每行每列是否出现 }
    Total : Longint ;                                               {拉丁方的总数 }
Procedure Init ;                                                   {读入 n并初始化 }
Var i : Word;
Begin
Write(’ ENTER A WHOLE NUMBER ( 2 - 6 ) : ’ ) ;
Readln( n) ;
Fillchar ( h, Sizeof( h) , 0) ;
Fillchar (v , Sizeof (v) , 0 ) ;
For i ∶ = 1 To n Do                                                 {初始化第一行和第一列    }
  Begin
  h [1, i ]∶ = 1 ;
  v[1 , i]∶ = 1;
  v[ i , i]∶ = 1;
  h [ i, i ]∶ = 1 ;
  End;
Total ∶ = 0;
End ;
Procedure Find( x, y : Word) ;                                 {寻找所有的可能情况 }
Var i : Word;
Begin
For i ∶ = 1 To n Do
  If ( h[y, i ] = 0) And (v[ x, i] = 0 ) Then
    Begin
      h[ y, i]∶ = 1;
      v[ x, i ]∶ = 1 ;
      If x = n Then I f y = n Then Inc ( Total)           {如果找到一种则总数加1   }
Else Find(2 , y + 1)
Else Find( x + 1 , y) ;
· 6 4 ·      h[ y, i]∶ = 0;
      v[ x, i ]∶ = 0 ;
    End;
End ;
Procedure Print ;                                                   {打印总数     }
Var i : Word;
Begin
For i ∶ = 1 To n - 1 Do                                               {总数乘以( n - 1) !                 }
  Total∶ = Total * i ;
Writeln(’ THE NUMBER OF ’ , n, ’X ’ , n, ’LATIN’ ) ;
Writeln(’ SQUARES IS ’ , Total ) ;
End ;
Begin
Init ;                                                                   {读入数据并初始化         }
Find(2 , 2) ;                                                             {寻找所有可能                   }
Print ;                                                                 {打印结果                       }
End .
(3 ) 运行结果
ENTER A WHOLE NUMBER (2 - 6) : 5
THE NUMBER OF 5 X 5 LATIN
SQUARES IS 1344
ENTER A WHOLE NUMBER (2 - 6) : 6
THE NUMBER OF 6 X 6 LATIN
SQUARES IS 1128960

打印本文   加入收藏   返回顶部   关闭窗口Tags:计算机程序设计资格赛试题解答,计算机程序设计资格赛试题答案  
参与评论
共有评论 0网友评论列表
CopyRight © 2009-2012 计算机基础知识 Inc.All Rights Reserved. 备案:苏ICP备09028880号