设为首页 | 加入收藏夹

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

2012-6-2 18:29:59 作者:计算机基础知识试题 录入:应序康 访问:6676 次 被顶:3 次 字号:【
摘要:第四题: Bet sy 的旅行 (1 ) 解题思路此题显然可以用简单的回溯法来解决。但是题目中已经提醒我们,如果不采用更有效的方法,则 n = 6 时运行时间会很长。我们知道一般情况下,双向搜索都要比单向搜索要快,所以我们采用双向的搜索方法...
第四题: Bet sy 的旅行
    (1 ) 解题思路
此题显然可以用简单的回溯法来解决。但是题目中已经提醒我们,如果不采用更有
效的方法,则 n = 6 时运行时间会很长。我们知道一般情况下,双向搜索都要比单向搜索
要快,所以我们采用双向的搜索方法。从起点(农场)和终点(市场)两个方向进行搜索,直
至走完所有的方格并相遇为止。我们用递归过程 Find( k,方格 1,方格 2 )来进行搜索,其
中 k 为走过的步数,方格 1 和方格 2 为两方向走到的格子:
Procedure   Find( k,方格 1 ,方格 2) ;
  Begin
    If   走完所有的格子且相遇   Then   线路总数加 1
        Else
        I f   方格1 和方格 2 重合   Then Exit
            Else Begin
              找出所有方格 1 和方格 2能到达的新方格;
              Find( k + 1 ,新方格 1,新方格 2 ) ;
            End
  End;
注意当走完所有的格子并判断两方向是否相遇时,要分 n 为奇数和偶数两种情况讨
论: n 为奇数时,两个格子应重合; n为偶数时,两个格子应相邻。
· 2 9 ·(2 ) 参考程序
Const d:Array[1 . .4,1 . . 2 ] Of Shor tint = ( (1 ,0) , ( - 1 ,0) , ( 0,1 ) , (0 , - 1) ) ;
{旅行的 4 个方向                 }
Var n   : Integer ;
    Total : Integer ;                                               {旅行路线的数目                 }
    a   : Array [ 0 . . 7 ,0 . . 7] Of Byte ;                 {旅行地图           }
Procedure Init ; {读入 n并初始化数据 }
Var i : Integer ;
Begin
Write(’ Enter value for N: ’ ) ; Readln( n) ;
Total ∶ = 0;
Fillchar ( a , Sizeof ( a ) , 0) ;
For i ∶ = 0 To n + 1 Do
  Begin
  a[ 0, i ]   ∶ = 2;
  a[ i ,0 ]   ∶ = 2;
  a[ n + 1 , i]∶ = 2;
  a[ i , n + 1]∶ = 2;
  End;                                                                   {正方形的外围不可行走    }
End ;
Function Touch(x1, y1, x2 , y2: Integer ) :Boolean ; {判断两个方格是否相邻  }
Begin
Touch ∶ = (x1 = x2) And (Abs( y1 - y2) = 1 ) Or
        (y1 = y2 ) And (Abs( x1 - x2) = 1) ;
End ;
Procedure Find( k, x1 , y1 , x2 , y2 : Integer ) ;             {双向搜索的递归过程       }
Var i , j : Integer ;
Begin
If ( k = ( n * n + 1) Div 2 ) Then
    Begin
    I f ( n Mod 2 = 0) And Touch( x1 ,y1 ,x2 ,y2 )
        Then Inc( Total) ;
    I f ( n Mod 2 = 1) And (x2 = x1) And ( y2 = y1 )
· 3 9 ·        Then Inc( Total) ;                                           {找到一条路线则总数加1   }
    Exit ;
    End;
If ( x2 = x1 ) And ( y2 = y1) Then Exit ;                 {如果没有走完所有的方格就相遇 }
{则退出                   }
a[ y1, x1 ]∶ = 1 ;
a[ y2, x2 ]∶ = 1 ;
For i ∶ = 1 To 4 Do
  If ( a[ y1 + d[ i,2 ] , x1 + d[ i ,1] ] = 0 ) Then
  For j ∶ = 1 To 4 Do
    If ( a[ y2 + d[ j,2 ] , x2 + d[ j, 1] ] = 0 ) Then
    Find( k + 1 , x1 + d[ i ,1 ] , y1 + d[ i ,2] , x2 + d[ j ,1 ] , y2 + d[ j ,2] ) ;
{每个格向 4 个方向搜索     }
a[ y1, x1 ]∶ = 0 ;
a[ y2, x2 ]∶ = 0 ;                                                     {恢复数据     }
End ;
Begin
Init ;                                                                   {读入 n并初始化数据         }
Find(1 , 1 , 1 , 1 , n) ;                                       {递归寻找旅行路线   }
Writeln(’ The number of tours is ’ , Total) ;
End .
(3 ) 运行结果
Enter value for N: 5
The number of tours is 86
Enter value for N: 6
The number of tours is 1770

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