设为首页 | 加入收藏夹

1994年美国计算机程序设计总决赛试题答案(解答)

2012/6/2 18:28:18 作者:计算机基础知识试题 录入:应序康 访问:7414 次 被顶:1 次 字号:【
摘要:第一题: 给数字起名 (1 ) 解题思路题目中要求名字的数目最大为 5000, 每个名字最长为 12 个字母。这样如果用一个字符串来记录名字,则所需空间大小为 5000 * 13 = 65000 个字节。所以我们用指针来把它放在堆中,以节省...

第一题: 给数字起名
    (1 ) 解题思路
题目中要求名字的数目最大为 5000, 每个名字最长为 12 个字母。这样如果用一个
字符串来记录名字,则所需空间大小为 5000 * 13 = 65000 个字节。所以我们用指针来把
它放在堆中,以节省数据段的空间。
任务 A 要求找出一个数字对应的名字。由于名字的最大数目仅为 5000,所以我们可
以用循环来对每一个名字进行判断,运行速度不会很慢。为了提高速度,对每一个名字,
先判断它的长度是否与数字位数相同,再逐个字母判断。
任务B 要求找出能起名字的编号数目。由于编号的位数最大为12 位,如果按每个编
号进行查找,当位数较大时,运行速度会非常慢。我们知道名字的最大数目为 5000 ,所以
应按名字进行查找。找出所有长度为 digi t 的名字所对应的不同数字,即为能起名字的编
号数目。
(2 ) 参考程序
Type St r12 = St ring[ 12 ] ;
    Dictionary = Ar ray[1 . . 5000 ] Of Str12 ;             {存放名字或数字的类型  }
    Str3   = String[ 3] ;
Const Key : Array[’ 2’. .’ 9’ ] Of St r3 =
      (’ ABC’ ,’ DEF’ ,’ GHI’ ,’ JKL’ ,’ MNO’ ,’ PRS’ ,’ TUV’ ,’ WXY’ ) ;
{记录每个数字对应的字母   }
· 2 7 ·Var Name : ^Dictionary;                                     {存放可用的名字     }
    Top   : Word;                                                   {名字的数目   }
    Ch   : Ar ray[’ A’. .’ Z’ ] Of Char ;                   {每个字母对应的数字       }
    Useful : ^Dictionary;                                           {能起名字的编号                 }
    Total : Word;                                           {能起名字的编号数目 }
Procedure Init ; {读入所有可采用的名字 }
{并初始化 }
Var f   : Text ;
    i , j : Char ;
Begin
Assign( f , ’ prob1 . dat’ ) ;
Reset ( f ) ;
New(Name) ;
Top ∶ = 0;
While Not ( Eof ( f ) ) Do
  Begin
  Inc( Top) ;
  Readln( f , Name ^[ Top] ) ;
  End;
Close ( f ) ;
For i ∶ = ’ A’To ’ Z’Do
  For j∶ = ’ 2’To ’ 9’Do
  I f Pos( i , Key[ j] ) > 0 Then Ch[ i]∶ = j ;
New(Useful) ;
End ;
Procedure Task - a ;                                           {任务 A的过程       }
Var Number : Str12;                                               {读入的数字   }
    Found   : Boolean;                                       {是否找到对应的名字 }
    Len     : Byte;                                                 {读入数字的位数                 }
    i , j     : Word;
Begin
Repeat
  Write (’ Enter number to be t ranslated: ’ ) ;
  Readln(Number ) ;
  If Number = ’ 0’Then Exit ;                                 {如果读入的为 0 则退出 }
  Found ∶ = False;
· 3 7 ·  Len ∶ = Length(Number ) ;
  For j∶ = 1 To Len Do
  I f Not ( Number [ j] In [’ 2’. .’ 9’ ] ) Then
      Begin
      j∶ = 0 ;
      Break;
      End;
  If j > 0 Then                                                   {如果数字非法则不进行查找 }
  For i∶ = 1 To Top Do
  I f Length(Name ^[ i] ) = Len Then
    Begin
    For j ∶ = 1 To Len Do
      If ( Pos(Upcase (Name ^[ i, j ] ) , Key[Number [ j] ] ) = 0)
        Then Begin
              j∶ = 0;
              Break;
              End;
    I f j > 0 Then
        Begin
        I f Not Found Then
            Begin                                           {如果是第一个名字则先打印信息 }
            Write (’ Possible names are : ’ ) ;
            Found ∶ = True ;
            End;
        Write (Name ^[ i] , # 9 ) ;                         { # 9 为制表符    }
        End;
  End;
  If Not Found Then Write (’ No matching names found’ ) ;
  Writeln ;
  Writeln ;
Until False ;
Dispose(Name ) ;
End ;
Procedure Task - b;                                           {任务 B的过程       }
Var Digit : Word;                                           {输入的位数         }
    New : St r12 ;
    i , j   : Word;
Procedure Judge;                                                   {判断一个数字是否出现重复 }
· 4 7 ·Var k : Word ;
Begin
For k ∶ = 1 To Total Do
  If Useful ^[ k ] = New Then Exit ;
Inc( Total) ;                                                             {如果不重复则总数加 1     }
Useful ^[ Total]∶ = New;
End ;
Begin
Repeat
  Write (’ Enter # digits : ’ ) ;
  Readln(Digit ) ;
  Total∶ = 0 ;
  If Digit = 0 Then Exit ;
  For i∶ = 1 To Top Do                                       {找出每个长度为 digit 的名字对应 }
  I f Length(Name ^[ i] ) = Digit Then                   {的数字 }
    Begin
New∶ = ’ ’ ;
For j ∶ = 1 To Digit Do
New ∶ = New + Ch[ Upcase( Name ^[ i, j ] ) ] ;
Judge ; {判断是否出现重复 }
    End;
  Write (’ There are ’ , Total , ’usable numbers out of 1’ ) ;
  For i∶ = 1 To Digit Do
    Write (0) ;                                                     {打印结果 }
  Writeln ;
  Writeln ;
Until False ;
Dispose( Useful ) ;
End ;
Begin
Init ; {读入名字并初始化         }
Task - a ;                                                                 {任务 A的过程               }
Task - b;                                                                 {任务 B的过程               }
End .
第二题(A) : 超级素数
    (1 ) 解题思路
本题需注意超级素数的最大位数为 8,如果用简单的循环来做,则运行速度会较慢。
· 5 7 ·由于超级素数的定义,它从左边截取任意位的数都为素数。所以我们从左边第一位开始
查找,边查找边判断,这样可以省去很多不必要的搜索。
(2 ) 参考程序
Var n : Word;                                                     {超级素数的位数                 }
Procedure Find( k, x : Longint ) ;                             {找出所有的超级素数 }
Var i : Word;
Function Ok(y : Longint ) :Boolean;                     {判断数 y 是否为素数       }
Var j : Word;
Begin
Ok ∶ = False ;
For j ∶ = 2 To Trunc(Sqrt ( y) ) Do
  If y Mod j = 0 Then Exit ;
If y > 1 Then Ok∶ = True ;
End ;
Begin
If k = n + 1 Then Write( x, # 9)                   {找到素数则打印; # 9 为制表符   }
Else
For i ∶ = 1 To 9 Do
  If Ok( x * 10 + i ) Then Find( k + 1, x * 10 + i) ;
End ;
Procedure Main;
Begin
Repeat
  Writeln ;
  Write (’ Number of digits: ’ ) ; Readln( n) ;       {读入数据                     }
  If n > 0 Then Find(1 , 0) ;
Until n = 0 ;
End ;
Begin
Main ;
End .
(3 ) 运行结果
· 6 7 ·Number of digits: 6
233993   239933   293999   373379   373393   593933   593993   719333   739391
739393   739397   739399
Number of digits: 8
2339933929399999373379995939333973939133
Number of digits: 0
第二题(B) : 母牛的奶
    (1 ) 解题思路
由于三个桶的容量都不大于 15,所以三个桶装牛奶的状态总数不大于 16
3
种。我们
用数组 Stack 来记录所有可能的状态, 用变量 Open 来表示待扩展状态的下标, 用变量
Top 来记录状态总数:
Stack[1 ]←初始状态;
Open←1 ;
Top←1 ;
While   还有未扩展状态   Do
  Begin
    找出由 Stack [Open]能扩展的状态;
    If   此状态没有出现重复   Then
        将此状态记录到 Stack中;
    Open + 1 ;
  End;
这样我们只要找出所有状态中 A 桶牛奶为 0 的状态,记录下此状态中 C 桶牛奶的体
积即可。
(2 ) 参考程序
Type Code = Ar ray[ 1 . . 3] Of Byte ;
Var Stack : Array[1 . . 1000] Of Code;                   {记录所有可能的状态       }
    v     : Code ;                                           {三个桶的容量       }
    Can   : Set Of Byte ;                                           {C中可能的剩余量           }
Procedure Init ;                                                   {读入三个桶的容量         }
Begin
Write(’ Enter A B C: ’ ) ;
Readln( v[1] , v[2] , v[ 3] ) ;
Can ∶ = [ v[ 3] ] ;
End ;
Procedure Find;                                                   {寻找所有可能的状态             }
· 7 7 ·Var Open, Top : Word;                                       {待扩展状态的下标和状态总数 }
    i , j : Word;
Procedure Judge;                                                   {判断一个新状态是否重复   }
Var k, r , t : Word;
Begin
For k ∶ = 1 To Top - 1 Do
  Begin
  t∶ = 0 ;
  For r∶ = 1 To 3 Do
    If Stack[ k, r ] < > Stack[ Top, r ] Then t∶ = 1;
  I f t = 0 Then Exit ;
  End;
If Stack[ Top ,1] = 0 Then Include (Can, Stack[ Top,3 ] ) ;
Inc( Top) ;
End ;
Begin
Open ∶ = 1 ;
Top ∶ = 2;
Stack[ 1,1 ]∶ = 0 ;
Stack[ 1,2 ]∶ = 0 ;
Stack[ 1,3 ]∶ = v[ 3] ;
While Open < Top Do                                               {如果还有未扩展的状态    }
  Begin
  For i ∶ = 1 To 3 Do
  For j ∶ = 1 To 3 Do                                               {列举所有倒牛奶的可能    }
    If ( j < > i ) And (Stack[Open, i ] < v[ i] ) And (Stack[Open, j ] > 0)
      Then Begin
            Stack[ Top]∶ = Stack[Open] ;
            If ( v[ i] - Stack[Open, i ] > Stack[Open, j ] )
              Then Begin Inc(Stack[ Top, i ] , Stack[Open ,j ] ) ;
                          Stack[ Top, j]∶ = 0 ;
                    End                                     {如果 j 桶可以倒空   }
              Else Begin
                    Stack[ Top , i]∶ = v[ i] ;
                    Dec(Stack[ Top, j] , v[ i] - Stack [Open, i] ) ;
                    End;                                           {j 桶不可以倒空 }
            Judge;
· 8 7 ·          End ;
  Inc(Open) ;                                                     {扩展下一个状态                 }
  End;
End ;
Procedure Print ;                                                   {打印结果     }
Var i : Word;
Begin
Write(’ Answer : ’ ) ;
For i ∶ = 1 To v[3 ] Do
  If i In Can Then Write ( i ∶3) ;
Writeln;
End ;
Begin
Init ;                                                                   {读入数据                       }
Find;                                                                   {找出所有可能的状态             }
Print ;                                                                 {打印结果                       }
End .

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