1993年美国计算机程序设计资格赛试题答案.doc

《1993年美国计算机程序设计资格赛试题答案.doc》由会员分享，可在线阅读，更多相关《1993年美国计算机程序设计资格赛试题答案.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一题: 分数变小数 (1 ) 解题思路本题可以模仿手算除法的形式,重复地进行求商和余数的运算,直到余数为 0 或出现循环节为止。(2 ) 参考程序Const Max = 100; 小数点后最大位数 Var Left , Digit : Ar ray 0 . .Max Of Word; 记录每次的余数和商 n, d : Word; q, Top: Word; q为循环节的位置 Procedure Init ; 读入数据 BeginWrite( ENTER N , D: ) ;Readln( n, d) ;End ;Procedure Calc; 计算 Var i : Word;BeginDig

2、it 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 上海金水财税 http:/101.1.28.171/ q = i + 1; Exit ; 如果出现循环节则退出 End; End;

3、End ;Procedure Print ; 打印结果 Var i : Word;BeginWrite( 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 ;BeginInit ; 读入数据 Calc ; 计算 Print ; 打印结果 End .(3 ) 运行结果EN

4、TER N ,D: 11 5911 / 59 = .(1864406779661016949152542372881355932203389830508474576271)第二题: 质数竖式(1 ) 解题思路 9 3 此题比较简单,只需对两个乘数进行循环,然后判断竖式中的数是否满足要求。需注意的一点是:乘积可能超出整型的范围,需用长整型来计算。(2 ) 参考程序Var Num : Set Of Byte; 数字集合 n : Word; 竖式的数目 Procedure Init ; 读入数据并初始化 Var St : St ring; i : Word;BeginWrite( Enter a s

5、et of digits: ) ;Readln(St ) ; 以字符串形式读入 Num = For i = 1 To Length (St ) Do I南京金鑫财税 http:/101.1.28.180/n = 0 ;End ;Function Ok(x :Longint ) :Boolean ; 判断 x的每位数是否都 在集合中 BeginOk = 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; 找出满足

6、条件的竖式 Var i , j : Longint ;BeginFor 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( ) ;Writeln( i: 6) ;Writeln(X , j :4 ) ;Writeln( - - - - - ) ;Writeln( ( j Mod 1

7、0) * i :6 ) ;Writeln( ( j Div 10 ) * i :5) ;Writeln( - - - - - ) ;Writeln( i * j :6) ; End;Writeln( The number of unique solutions = , n) ;End ;BeginInit ; 读入数据并初始化 Calc ; 找出满足条件的竖式 End .(3 ) 运行结果Enter a set of digits : 2357 1 7 7 5 3 32 3 2 52 3 2 52 5 5 7 5The number of unique solutions = 1第三题: 66

8、棋子挑战(1 ) 解题思路本题与八皇后问题本质相同,只需用简单的回溯法即可解决。(2 ) 参考程序Var a : Array1 . .6 Of Byte; 记录每个棋子列的位置 Num: Word; 解的总数 Procedure Find( k:Word) ; 递归寻找 1 4 Var i , j : Integer ;BeginIf k = 7 Then Begin For i = 1 To 6 Do Write( a i :2 ) ; Writeln; Inc( Num) ; EndElseFor 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