设为首页 | 加入收藏夹

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

2012-6-2 18:32:06 作者:计算机基础知识试题 录入:应序康 访问:7008 次 被顶:2 次 字号:【
摘要:第一题: 奶牛排队 (1 ) 解题思路· 0 0 1 ·此题与我们熟知的鼓轮题目很相似,唯一的区别是本题要求排成一列,而鼓轮要求排成一圈。以 n = 4, m = 19 为例(用 0 代表 b,用 1 代表 w ) : 我们发现从子序列 a...

第一题: 奶牛排队
    (1 ) 解题思路
· 0 0 1 ·此题与我们熟知的鼓轮题目很相似,唯一的区别是本题要求排成一列,而鼓轮要求排
成一圈。以 n = 4, m = 19 为例(用 0 代表 b,用 1 代表 w ) : 我们发现从子序列 a1 a2 a3 a4 到
子序列 a2 a3 a4 a5 , 其中有 3 位没有变。所以我们考虑所有的 n - 1 = 3 位二进制数(如图
图  3 . 7 . 1
3 .7 .1) ,每个二进制数为一个点,从点( ai - 1 ai ai + 1 )可以到达
点( ai ai + 1 0 )和点( ai ai + 1 1 ) ,对应的子序列分别为 ai - 1 ai ai + 1 0
和 ai - 1 ai ai + 11。由于此图中每个点的正、 负度均为2 ,所以必
存在一条欧拉道路经过所有的边。其中任意一条都是一个
合理排列,例如 0000101001101111。
为了寻找欧拉道路,我们用数组 p 来记录每个点是否
还有边未走。其中 p[ i ]的第 0 位和第 1 位(二进制)分别代
表点 i 指向 0 和 1 的边。用数组 List 记录这个排列:
设定出发点为(000 ) ;
走过( 000)的自环;
Repeat
  找一个只剩一个出发边的点;
  任找一条包含此点的回路;
  将此回路加入到队列中;
Until   所有边都走完;
(2 ) 参考程序
Type List type = Array[ 1 . . 32782 ] Of Byte ;               {记录奶牛排列的类型       }
Var p : Array[0 . .16383] Of Byte ;                             {记录每点还有哪些边未走   }
    List : List type ;                                               {记录奶牛的排列                 }
    Top : Word;                                                   {加入队列的奶牛数目             }
    m, n : Word;
    Num : Word;                                                   {节点的数目   }
    Shield:Word;                                                   {计算节点对应数字的变量   }
Procedure Init ;                                                   {读入数据并初始化         }
Var i : Word;
Begin
Write(’ Enter N M: ’ ) ;
Readln( n, m) ;
Fillchar ( p, Sizeof ( p) , 3) ;
p[ 0]∶ = 2;
For i ∶ = 1 To n Do
  List [ i]∶ = 0;                                                     {将 n个 0 加入队列          }
· 1 0 1 ·Top ∶ = n ;
Num ∶ = 1;
For i ∶ = 1 To n - 1 Do
  Num∶ = Num * 2;
Shield ∶ = 0 ;
For i ∶ = 1 To n - 1 Do
  Shield ∶ = Shield * 2 + 1 ;                                       {低 n - 1位为 1 ,其余为 0 }
End ;
Function Search( x : Word) :Word;                             {找出队列中出现 x 的位置     }
Var i , j, k : Word;
Begin
For i ∶ = n To Top Do
  Begin
    k ∶ = 0 ;
    For j∶ = i - n + 2 To i Do
    k ∶ = k * 2 + List [ j] ;
    If k = x Then Begin
              Search ∶ = i ;
                  Exit ;                                           {找到则记录退出                 }
                  End;
  End;
End ;
Procedure Find;                                                   {寻找一种排列 }
Var i , Len : Word ;
    Locate : Word;
Begin
Repeat
  For i∶ = 0 To Num - 1 Do
I f ( p[ i] In [1 ,2] ) Then Break ; {找一个还有未走边的点 }
  Locate ∶ = Search( i ) ;                                       {找出这点在队列中的位置   }
  Len ∶ = Top - Locate ;
  Move (List [ Locate + 1 ] , List [m - Len + 1] , Len) ;             {移至队尾                 }
  Top ∶ = Locate;
  While p[ i ] > 0 Do
  I f ( p[ i] And 2 > 0) Then                                 {如果边 1 还未走     }
    Begin
· 2 0 1 ·      Inc ( Top) ; List [ Top]∶ = 1;                               {加入队列           }
      p[ i]∶ = p[ i ] And 1 ;                                           {去掉此边     }
      i ∶ = ( i * 2 + 1) And Shield;                         {取其低 n - 1 位           }
    End Else Begin {如果边 0 还未走 }
Inc( Top) ;
List [ Top]∶ = 0 ;
p[ i ]∶ = p[ i ] And 2 ;
i∶ = (2 * i ) And Shield;
End;
  Move (List [ m - Len + 1] , List [ Top + 1 ] , Len) ;
  Inc( Top, Len) ;
Until Top = m;                                                   {直至队列中奶牛数目为 m   }
End ;
Procedure Print ;                                                   {打印结果     }
Var i : Word;
Begin
For i ∶ = 1 To m Do
  If List [ i] = 0 Then Write( ‘b’ )
              Else Write( ‘w’ ) ;
Writeln;
End ;
Begin
Init ;                                                                   {读入数据并初始化         }
Find;                                                                   {寻找一种排列                   }
Print ;                                                                 {打印结果                       }
End .
(3 ) 运行结果
Enter N M: 5 36
bbbbbwwwwwbwwwbbwwbwbwwbbbwbwbbwbbbb
第二题: 奶牛运输
(1 ) 解题思路
由于农场间的距离已经给定,所以我们很容易求出任两个任务间的距离。比如我们
执行任务 ‘A B’ 后执行任务 ‘F C’ ,则两个任务间的距离为农场B 到农场 F 的距离79。我
们假定第 0 个任务为 ‘A A’ ,每个任务为一个点,两点间的距离即为任务间的距离。这样
问题就化为在 n + 1 个点的图中求一条最短的哈密顿回路(经过每个点仅一次)。
· 3 0 1 ·对一个一般的图,目前还没有很好的算法求出它的最短哈密顿回路。但对一个点比
较少的图,有一个时空复杂度均为 n ·2n
的动态规划算法。由于此题中点的最大数目为
13 ,所以可以用动态规划算法来解决。
我们用数组 List [What , s]来记录从点 0 出发经过 k 个点的 s 集到达点 What 的最短
距离。则我们可以得到下面的递推公式:
List [What , s] = Min{List [ i , s / {i}] + d[ i , What ]}
(上式中,点 i 是 s集中的任一点, d[ i ,What ]为点 i到点 What 的距离)
初始条件是: List [What , {} ] = d[0 ,What ]
则最短回路的长度为 Min{List [What , {1 . . .n}/ {What} ] + List [ what , 0] }
例如 4 个点之间的距离如表 3 .7 .1。
表  3 . 7 . 1
0 1 2 3
0 0 8 5 6
1 6 0 8 5
2 7 9 0 5
3 9 7 8 0
    可知初始条件为:
List [ 1, {} ] = d[0, 1 ] = 8, List [ 2, {} ] = d[0, 2 ] = 5, List [ 3, {} ] = d[0, 3 ] = 6
k = 1 时:
List [ 1, {2} ] = List [2 , {}] + d[2, 1] = 14, List [1 , {3} ] = List [ 3, {}] + d[3 ,1] = 13
List [ 2, {1} ] = 16 , List [ 2, {3} ] = 14 , List [3 , {1}] = 13 , List [3 , {2}] = 10
k = 2 时:
List [ 1, {2 ,3}] = Min{List [ 2, {3} ] + d[ 2,1 ] , List [3, {2} ] + d[ 3, 1]} = 17
List [ 2, {1 ,3}] = 21 , List [3 , {1,2}] = 19
则最短回路的长度为:
Min{List [1, {2, 3} ] + d[1, 0 ] , List [2, {1, 3} ] + d[2, 0 ] ,
List [ 3, {1, 2}] + d[ 3, 0] } = 23
虽然我们用集合来表示这 k 个点很方便,但是集合不能作为数组的下标。所以我们
还需先将集合转为数字(程序中的 Num 函数)。另外本题中的总距离还需加上执行每个
任务所走的距离(程序中的 Base 变量)。
(2 ) 参考程序
Const Map : Ar ray[’ A’. .’ G’ ,’ A’. .’ G’ ] Of Byte =
          ( (0, 56 ,43 ,71 ,35,41, 36) , (56, 0,54, 58 ,36 ,79 ,31 ) ,
          (43 ,54 ,0 ,30 ,20,31, 58) , (71, 58 ,30 ,0 ,38 ,59 ,75 ) ,
          (35 ,36 ,20,38, 0,44, 67) , (41, 79 ,31 ,59 ,44,0 ,72 ) ,
          (36 ,31 ,58,75, 67 ,72 ,0) ) ;                     {农场间的距离     }
· 4 0 1 ·Type St r3 = St ring[ 3] ;
    Data = Set Of 0 . . 12 ;
Var n : Word;                                                     {任务总数   }
    Task : Ar ray[ 0 . . 12 ] Of St r3 ; {记录每个任务 }
    d : Array[0 . .12 ,0 . . 12 ] Of Byte; {任务间的距离 }
    List : Array[0 . . 12, 0 . . 2047] Of Word; {动态规划的数组 }
    What , k : Word;
    Path : Ar ray[0 . . 12] Of Byte; {执行任务的最优次序 }
    Top   : Word;
    Base : Word; {执行任务的距离 }
Procedure Init ; {读入数据并计算 d和 Base }
Var f   : Text ;
    i , j : Word;
Begin
Assign( f ,’ delvr .txt’ ) ;
Reset ( f ) ;
Readln( f , n) ;
For i ∶ = 1 To n Do
  Readln( f , Task[ i] ) ;
Close ( f ) ;
Task[ 0]∶ =’ A A’ ;
For i ∶ = 0 To n Do
For j ∶ = i To n Do
  Begin
    d[ i, j ]∶ = Map[ Task[ i ,3 ] , Task[ j ,1] ] ;
    d[ j, i ]∶ = Map[ Task[ j ,3 ] , Task[ i ,1] ] ;
  End;
Fillchar (List , Sizeof (List ) , $Ff ) ;
Base∶ = 0 ;
For i ∶ = 1 To n Do
  Inc(Base, Map[ Task[ i ,1] , Task[ i,3 ] ] ) ;
End ;
Function Num( s : Data) :Word;                                 {计算集合 s 对应的数 }
· 5 0 1 ·Var x : Word Absolute s;
Begin
Num ∶ = x;
End ;
Procedure Calc(Step, Pre:Word; s:Data) ;               {找出所有 k个点的组合     }
Var i :Word ;
Begin
If Step > k Then
    Begin
    For i ∶ = 1 To n Do
      If ( i In s) And ( List [ i, Num( s - [ i ] ) ] + d[ i ,What ] < List [What , Num( s) ] )
        Then List [What , Num( s) ]∶ = List [ i, Num( s - [ i] ) ] + d[ i, What ] ;
    End                                                               {如果找到更优的解则修改数组中 }
{的值   }
    Else For i ∶ = Pre + 1 To n Do
          If i < > What Then Calc (Step + 1, i , s + [ i ] ) ;
End ;
Procedure Find;                                                   {用动态规划方法计算最短回路的 }
{长度                     }
Var i , j : Word;
Begin
For i ∶ = 0 To n Do
  List [ i,0 ]∶ = d[0 , i] ;
For k ∶ = 1 To n - 1 Do
  For What∶ = 1 To n Do
  Calc (1, 0 , [ ] ) ;                                                 {计算 List [What ,经过 k个点] }
For i ∶ = 1 To n Do
  If List [ i, Num( [1 . .n] - [ i ] ) ] + d[ i ,0] < List [ 0, Num( [ 1 . . n] ) ]
    Then List [ 0, Num( [ 1 . . n] ) ]∶ = List [ i , Num( [1 . .n] - [ i ] ) ] + d[ i ,0] ;
{计算最短回路的长度             }
End ;
Procedure Print ;                                                   {打印执行任务的顺序             }
Var s : Data ;
· 6 0 1 ·    i , Farm : Word;
Begin
Writeln(List [ 0, Num( [ 1 . . n ] ) ] + Base ) ;                   {打印总路程               }
s∶ = [1 . .n] ;
Farm ∶ = 0;
Path[0 ]∶ = 0 ;
Top ∶ = n + 1 ;
Repeat
  For i∶ = 1 To n Do
  I f ( i In s) And (List [ i , Num(s - [ i] ) ] + d[ i, Farm] = List [Farm, Num( s) ] )
      Then Begin
            Farm∶ = i;
            s∶ = s - [ i ] ;
            Dec( Top) ;
            Path[ Top]∶ = i ;                                   {记录执行哪个任务   }
            Break;
          End ;
Until s = [ ] ;
Write(’ A ’ ) ;
For i ∶ = 1 To n Do
  Begin
  I f Task[ Path[ i] ,1] < > Task[Path[ i - 1] , 3] Then
      Write ( Task[ Path[ i] ,1] ,’’ ) ;
  Write( Task[Path[ i ] , 3] ,’’ ) ;
  End;
If Task [Path[ n] , 3] < > ’ A’Then Write(’ A’ ) ;           {打印经过农场的顺序       }
Writeln;
End ;
Begin
Init ;                                                                   {读入数据并初始化         }
Find;                                                                   {找出最短回路的长度             }
Print ;                                                                 {打印结果                       }
End .
第三题: 攻击性奶牛
    (1 ) 解题思路
此题的最终目的是找出一种安排方案,使得攻击的方格数目最少,也就是不被攻击的
方格数目最多。初一看如果用搜索方法,则状态数目将会非常大,运行速度会很慢。可是
· 7 0 1 ·我们可以在其中加一些剪枝处理,则可大大减少搜索量。我们用变量 Max 记录当前找到
的最优方案中不被攻击的方格数。如果在搜索过程中,剩余的不被攻击的方格已经不大
于这个数目,则不应继续搜索下去。我们还发现,整个区域是上下对称的,所以我们不妨
假设上半部分的奶牛大于等于下半部分的奶牛数目,这样搜索量就可以减少一半。
(2 ) 参考程序
Var At tack : Ar ray[ 1 . . 64 ,0 . . 30] Of Byte;               {每个格子能攻击的方格  }
    Num     : Array[1 . . 64] Of Byte ;                     {每个格子能攻击的方格数目 }
    a   : Array[1 . . 8 ,1 . . 8 ,0 . . 30] Of Byte Absolute At tack;
    Max: Word;                                                     {剩余的最多方格数         }
    Cow, Result : Ar ray[0 . . 9 ] Of Byte ;                 {奶牛的位置及最佳方案  }
    Map : Ar ray[1 . . 64] Of Byte;                               {记录每个方格是否被攻击   }
Procedure Init ;                                                   {初始化数据   }
Var i1 , i2 , j1 , j2 : Integer ;
Begin
Fillchar (Num, Sizeof ( Num) , 0 ) ;
Fillchar (Map , Sizeof (Map) , 0 ) ;
Cow[0]∶ = 0 ;
Max ∶ = 0 ;
For i1∶ = 1 To 8 Do
For j1∶ = 1 To 8 Do
  For i2 ∶ = 1 To 8 Do
  For j2 ∶ = 1 To 8 Do
  I f ( i1 = i2) Or ( j1 = j2 ) Or (Abs( i1 - i2 ) = Abs( j1 - j2 ) ) Then
      Begin
      Inc( Num[ ( i1 - 1 ) * 8 + j1] ) ;
      a[ i1, j1, Num[ ( i1 - 1 ) * 8 + j1 ] ]∶ = ( i2 - 1) * 8 + j2 ;
      End;                                                         {找出每个格子攻击的方格   }
End ;
Procedure Find( k, Left : Word) ;                             {搜索所有的安排方案 }
Var i , j : Word;
Begin
  If k > 8 Then
    Begin
    Max ∶ = Left ;
· 8 0 1 ·    Result∶ = Cow;
    End
Else
For i ∶ = Cow[ k - 1 ] + 1 To 64 Do
  If ( k > 4 ) Or ( i < 33) Then                         {如果上半部分的奶牛不少于下半 }
    Begin                                                         {部分的奶牛         }
      For j∶ = 1 To Num[ i ] Do
      Begin
        If Map[Attack[ i, j ] ] = 0 Then Dec( Left ) ;
        Inc (Map[Attack[ i , j] ] ) ;
      End;
      Cow[ k]∶ = i ;
      If ( Left > Max) Then Find( k + 1 , Left ) ;           {如果不能剪枝则继续搜索 }
      For j∶ = 1 To Num[ i ] Do                                 {恢复数据     }
      Begin
        Dec( Map[Attack] [ i , j] ] ) ;
        If Map[Attack[ i, j ] ] = 0 Then Inc( Left ) ;
      End;
      End;
End ;
Procedure Print ;                                         {打印结果     }
Var i , j : Word;
Begin
Result [ 9]∶ = 0;
j ∶ = 1 ;
For i ∶ = 1 To 64 Do
  Begin
  I f i = Result [ j ] Then
      Begin
      Write(’ C ’ ) ;
      Inc( j ) ;
      End
      Else Write(’.’ ) ;
  I f i Mod 8 = 0 Then Writeln ;
  End;
Writeln(’ Minimum = ’ ,64 - 8 - Max) ;
· 9 0 1 ·End ;
Begin
Init ;                                                                   {初始化数据                     }
Find(1 , 64 ) ;                                                     {找出所有的方案                 }
Print ;                                                                 {打印结果                       }
End .
(3 ) 运行结果
CCC . . . . .
.CC C . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
CC . . . . . .
. . . . . . . .
. . . . . . . .
Minimum = 45

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