设为首页 | 加入收藏夹

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

2012-6-2 18:33:15 作者:计算机基础知识试题 录入:应序康 访问:7338 次 被顶:1 次 字号:【
摘要:第一题: 阶乘 (1 ) 解题思路本题要求的是 n ! 最右边非零位的数,而不是它的确切数值。所以我们不必要记录n ! 的每一位数,只需记录其后若干位即可。那么我们最多要记录多少位呢 ? 这与 n ! 后面 0 的个数有关。我们知道, n ...

第一题: 阶乘
    (1 ) 解题思路
本题要求的是 n ! 最右边非零位的数,而不是它的确切数值。所以我们不必要记录
n ! 的每一位数,只需记录其后若干位即可。那么我们最多要记录多少位呢 ? 这与 n ! 后
面 0 的个数有关。我们知道, n ! 后 0 的数目等于 n ! 中因数 5 的幂次。由于 n≤1000,所
以 n ! 后 0 的数目不大于:
1000
5
+
1000
25
+
1000
125
+
1000
625
= 249     ( [ x]为下取整函数)
所以我们只需记录其后 250 位即可。我们用一个整型数组来记录 n ! 后 250 位每一
位的值,注意每乘一个数需作一次进位处理。最后找出数组中第一个非零的数。
(2 ) 参考程序
· 7 1 1 ·Const Max = 250;                                                   {保留乘积的位数                 }
Var a : Array[ 1 . .Max + 1] Of Word;                             {保留乘积的右 Max 位 }
    n : Word ;
Procedure Init ;                                                   {读入数据并初始化         }
Begin
Write(’ Enter N: ’ ) ;
Readln( n) ;
Fillchar ( a , Sizeof ( a ) , 0) ;
a[ 1]∶ = 1;
End ;
Procedure Calc;                                                   {计算乘积的后 Max 位        }
Var i , j : Word;
Begin
For i ∶ = 2 To n Do
  Begin
  For j ∶ = 1 To Max Do
    a [ j]∶ = a[ j] * i ;
  For j ∶ = 1 To Max Do
    Begin
    Inc( a[ j + 1] , a[ j] Div 10 ) ;
    a[ j ]∶ = a [ j] Mod 10 ;                                           {逢十进一     }
    End;
  End
End ;
Procedure Print ;                                                   {打印结果     }
Var i : Word;
Begin
i ∶ = 1 ;
While a [ i ] = 0 Do
  Inc( i) ;                                                         {找出最右边的非零位             }
Writeln( a [ i] ) ;
End ;
· 8 1 1 ·Begin
Init ;                                                                   {读入 n并初始化                   }
Calc ;                                                                   {计算乘积的后 Max 位      }
Print ;                                                                 {打印结果                       }
End .
(3 ) 运行结果
Enter N: 500
4
Enter N: 1000
2
第二题: 图案转换
    (1 ) 解题思路
此题关键是求由一个图案经旋转或对称后的新图案。我们可以经过坐标的转换来求
得原始图案的每一块在新图案中的位置。如图 3 .8 .1。
图   3 . 8 . 1
为了计算工作量,我们规定每旋转 90° 工作量加1,上下翻转则工作量加10,如果无法
转换则工作量为 20,这样就可以找出工作量最小的那种转换。转换的顺序是如果需上下
对称则先上下对称,而后再旋转。
(2 ) 参考程序
Type Block = Ar ray[1 . . 10 ,1 . . 10] Of Byte ;               {存放图案的类型           }
Var Origin, Goal : Block;                                   {原始和新的图案     }
    n     : Word ;                                                   {图案的边长   }
    Work : Word;                                                   {转换的工作量 }
Procedure Init ;                                                   {读入原始和新的图案             }
Var Name : St ring;
    f     : Text ;
    s     : String;
    i , j : Word;
· 9 1 1 ·Begin
Write(’ Enter name: ’ ) ;
Readln( Name ) ;
Assign( f , Name ) ;
Reset ( f ) ;
Readln( f , n) ;
For i ∶ = 1 To n Do
  Begin
  Readln( f , s) ;
  For j ∶ = 1 To n Do
    If s[ j ] = ’ X’Then Origin [ i, j ]∶ = 1
                  Else Origin[ i, j ]∶ = 0 ;
  End;                                                                   {读入原始图案                   }
Readln( f ) ;
For i ∶ = 1 To n Do
  Begin
  Readln( f , s) ;
  For j ∶ = 1 To n Do
    If s[ j ] = ’ X’Then Goal[ i , j]∶ = 1
                  Else Goal[ i, j ]∶ = 0 ;
  End;                                                                   {读入新的图案                   }
Close ( f ) ;
Work ∶ = 0 ;
End ;
Procedure Rotate;                                           {将原始图案向右旋转 }
Var i , j : Word;
    New   : Block;
Begin
For i ∶ = 1 To n Do
For j ∶ = 1 To n Do
  New[ j , n + 1 - i]∶ = Origin[ i, j ] ;
Origin ∶ = New;
End ;
Procedure Reflect ;                                                 {将原始图案上下翻转             }
Var i , j : Word;
    New   : Block;
· 0 2 1 ·Begin
For i ∶ = 1 To n Do
For j ∶ = 1 To n Do
  New[ i , j ]∶ = Origin[n - i + 1, j ] ;
Origin ∶ = New;
End ;
Function Same : Boolean;                                           {判断原始图案与新的图案   }
{是否相同                       }
Var i , j : Word;
Begin
Same ∶ = False ;
For i ∶ = 1 To n Do
For j ∶ = 1 To n Do
  If Origin[ i , j] < > Goal[ i , j ] Then Exit ;
Same ∶ = True;
End ;
Procedure Find;                                                   {寻找变换的步骤                 }
Var i : Word;
Begin
For i ∶ = 1 To 4 Do
  Begin
  I f Same Then Exit ;
  Rotate ;
  Inc(Work) ;
  End;
Reflect ;
Work ∶ = 10 ;                                                       {如果只旋转不行则先上下对称   }
For i ∶ = 1 To 4 Do
  Begin
  I f Same Then Exit ;
  Rotate ;
  Inc(Work) ;
  End;
Work ∶ = 20 ;                                                       {无法进行转换 }
End ;
· 1 2 1 ·Procedure Print ;                                                   {打印转换步骤 }
Begin
Case Work Of
  20 : Writeln (’ IMPROPER TRANSFORMATION .’ ) ;
  0   : Writeln(’ NOT TRANSFORMED .’ ) ;
  10 : Writeln (’ REFLECTED .’ ) ;
  1 ,2 ,3   : Writeln(’ ROTATED ’ ,Work * 90 ,’DEGREES .’ ) ;
  11, 12 ,13 : Writeln(’ REFLECTED AND ROTATED ’ , (Work - 10 ) * 90,’DEGREES .’ ) ;
  End;
End ;
Begin
Init ;                                                                   {读入原始和新的图案             }
Find;                                                                   {寻找变换的步骤                 }
Print ;                                                                 {打印转换步骤                   }
End .
(3 ) 运行结果
INPUT:
4
.X . .
.X . X
. . . .
. .X .
. .X .
X . . .
. .X X
. . . .
OUTPUT:
REFLECTED AND ROTATED 270 DEGREES .
INPUT:
5
X . . . .
.X . . .
.X . . .
. . . X .
. . . .X
.X . . .
· 2 2 1 ·. .X . .
. .X . .
. . . .X
X . . . .
OUTPUT:
IMPROPER TRANSFORMATION .

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