设为首页 | 加入收藏夹

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

2012-6-2 18:26:17 作者:计算机基础知识试题 录入:应序康 访问:6531 次 被顶:1 次 字号:【
摘要:第一题: 闭合篱笆 (1 ) 解题思路任务(1 )中要求判断一个篱笆是否合法,即是判断一个篱笆是否自交。我们对任两条不相邻的边作判断,这就需要求两条直线的交点。但是两条直线的位置并不能反映这两条边(线段)的位置关系,所以我们不仅要求出这两条...
第一题: 闭合篱笆
    (1 ) 解题思路
任务(1 )中要求判断一个篱笆是否合法,即是判断一个篱笆是否自交。我们对任两条
不相邻的边作判断,这就需要求两条直线的交点。但是两条直线的位置并不能反映这两
条边(线段)的位置关系,所以我们不仅要求出这两条边所在直线的交点,而且还要求出交
点相对于两条边的位置。如图 3 .3 .1 中,两条边 1 - 2 和 3 - 4 交点为 5,我们设有向线段
1 - 5 的有向长度为线段 1 - 2 的 d1 倍,有向线段 3 - 5 的有向长度为线段 3 - 4 的 d2 倍。
则通过 d1 和 d2 的不同值,我们可以得到两条边的位置关系。这样,两条边相交则有: 0 <
d1 < 1 且 0 < d2 < 1。
任务(2 )要求找出所有能看见的边。判断一条边是否能被看见,需要判断该边的每个
部分是否都被其它边所挡住。这样判断很麻烦,不容易编程。题目中已经提示我们,对于
每条边只需考虑是否有一条与其它边均不相交的光线照到它上面,即是这条边上有一点
与点( x y)所连的线段与其它边均不相交。但是一条边上有无数个点,我们究竟对哪些点
进行判断呢 ? 对于每条边,我们先找出挡在这条边前面的所有端点(包含这条边的两个端
点)。如图 3 .3 .1 中间的情况,点 1 为人所站的点,边 3 - 4 为所考虑的边。则挡在边 3 -
4 前面的端点需满足: d1 > 1; 0 < d2 < 1。找出了这些端点后,光线只能从这些端点之间照
过去。而且对于两个相邻的端点之间,光线或是都能照过去,或是都被挡住。所以我们只
· 4 6 ·图   3 . 3 . 1
要在每两个相邻的端点之间找一条光线进行判断即可。
我们先来看两个实际的例子,如图 3 .3 .2,判断在点 1 是否能看见边 3 - 4。在左边的
例子中(图 3 .3 .2 ( a ) ) ,点 6 和点 7 是挡在边 3 - 4 前面的点,从图中可以清楚地看到,点 1
发出的光线从点 3 和点 7 之间、 点 7 和点 6 之间、 点 6 和点 4 之间都无法穿过去,所以从
点 1 不能看到边 3 - 4。而在右边的例子中(图 3 .3 .2( b) ) ,点 1 发出的光线可以从点 2 和
点 4 之间穿过去照到边3 - 4 上,所以从点 1 能看到边3-4。通过这两个例子,我们可以找
到一种判断的方法: 考虑光线是否能从挡在边前面的端点之间穿过去。
图   3 . 3 . 2
编程之中还需注意: 对于每条边应先判断其是否与视线平行,而后再判断其是否可
见;判断两个实数是否相等不能直接用等号 ‘ =’ ,应该判断它们的差的绝对值是否小于一
定数值(程序中定为 10 - 5
)。
(2 ) 参考程序
Type Point = Ar ray[ 1 . . 2] Of Real ;                     {存放每个点坐标的类型  }
Var a : Array [ 1 . . 31 ] Of Point ;                             {存放所有点的坐标   }
    Locate : Ar ray [1 . . 30, 1 . . 2] Of Integer ;           {存放所有点的坐标— — —整数 }
    Visible : Ar ray [0 . .31] Of Byte ;                   {存放可见的边             }
    f- in, f - out : Text ;                                     {输入、 输出文件     }
· 5 6 ·    n   : Word;                                                     {点的数目     }
    Top: Word;                                                     {可见边的数目 }
    b   : Point ;                                                   {人的坐标     }
    d1, d2 : Real;                                                 {交点相对于边的位置             }
Procedure Init ;                                                   {打开文件     }
Begin
Assign( f - in, ’ fence . dat’ ) ;
Reset ( f - in) ;
Assign( f - out , ’ fence .sol’ ) ;
Rewrite( f - out ) ;
End ;
Function Same( x, y: Real) : Boolean;                   {判断两个实数是否相等  }
Begin
Same ∶ = Abs( x - y) < 1e - 5 ;
End ;
Function Intersect ( s1 , e1 , s2 , e2 : Point ) : Boolean;
{判断两条边是否相交,如   }
{果相交求出交点的位置    }
Var a1, a2, b1 ,b2 ,c1, c2 : Real ;
Begin
Intersect∶ = False;
a1∶ = e1 [1] - s1 [1] ;
a2∶ = e1 [2] - s1 [2] ;
b1∶ = s2 [1 ] - e2 [1] ;
b2∶ = s2 [2 ] - e2 [2] ;
c1 ∶ = s2 [1] - s1 [1] ;
c2 ∶ = s2 [2] - s1 [2] ;
If Same( a1 * b2, a2 * b1 ) Then Exit                             {如果两条边平行     }
    Else Begin
          d1∶ = ( c1 * b2 - c2 * b1)/ ( a1 * b2 - a2 * b1) ;
          d2∶ = ( c1 * a2 - c2 * a1 )/ (b1 * a2 - b2 * a1 ) ;
        End ;
Intersect∶ = True ;
End ;
· 6 6 ·Function Ok : Boolean;                                       {判断一个篱笆是否合法    }
Var i , j : Word;
Begin
Ok ∶ = False ;
For i ∶ = 1 To n Do
For j ∶ = i + 2 To n Do
  If ( i > 1) Or ( j < n) Then                                 {如果两条边不相邻   }
    Begin
      If Intersect ( a[ i ] , a[ i + 1] , a [ j] , a [ j + 1 ] ) And
        (d1 > = 0) And ( d1 < = 1 ) And ( d2 > = 0) And (d2 < = 1 )
        Then Exit ;                                               {如果出现自交情况则退出   }
    End;
Ok ∶ = True ;
End ;
Procedure Judge(What : Word) ;                         {判断边(What ,What + 1 )是否可见 }
Var i , j : Word;
    Num : Word;                                                   {挡在边前面的点的数目    }
    d     : Ar ray[1 . . 30] Of Real ;                             {挡在边前面的点在边上投影 }
    Mid   : Real ;
    p     : Point ;                                           {光线找到边上的位置 }
Begin
If Not ( Intersect (b , a [What ] , a [What ] , a [What + 1] ) )
    Then Exit ;                                                     {如果与视线平行                 }
Num ∶ = 0;
Fillchar ( d, Sizeof ( d) , 0) ;
For i ∶ = 1 To n Do
  If Intersect (b, a[ i ] , a[What ] , a [What + 1 ] ) And
    (d1 > = 1 ) And ( d2 < = 1) And (d2 > = 0)
    Then
      Begin                                                       {如果此点在边的前面             }
      Inc( Num) ;
      d[Num]∶ = d2;
      End;
For i ∶ = 1 To Num Do                                               {将点进行排序 }
· 7 6 ·For j ∶ = i + 1 To Num Do
  If d[ i] > d[ j] Then
    Begin
      Mid∶ = d[ i] ;
      d[ i]∶ = d[ j ] ;
      d[ j]∶ = Mid;
    End;
If Num > 0 Then
For i ∶ = 1 To Num - 1 Do
  Begin
  Mid∶ = ( d[ i] + d[ i + 1 ] )/ 2 ;
  p[1 ]∶ = ( 1 - Mid) * a [What ,1] + Mid * a [What + 1 ,1 ] ;
  p[2 ]∶ = ( 1 - Mid) * a [What ,2] + Mid * a [What + 1 ,2 ] ;
  For j ∶ = 1 To n Do                                               {判断点间的光线是否被挡住 }
    If ( j < > What ) And Intersect ( b, p, a [ j ] , a[ j + 1] ) And
      (d1 < = 1 ) And ( d1 > = 0) And ( d2 < = 1) And ( d2 > = 0 )
      Then
        Begin
        j∶ = 0 ;
        Break;
        End;
  I f j > 0 Then Begin
      Inc( Top) ;
      Visible [ Top]∶ = What ;
      Exit ;
      End;
  End;
End ;
Procedure Print ;                                                   {打印结果     }
Var i , j : Word;
Begin
Visible[ Top + 1]∶ = 0 ;
Writeln( f- out , Top) ;
If (Visible [1] = 1 ) And ( Visible [ Top] = n) Then
    Begin
    j ∶ = n;
    While Visible[ Top] = j Do
· 8 6 ·      Begin
      Dec ( Top) ;
      Dec ( j) ;
      End;
    For i ∶ = j + 1 To n + 1 Do
      Write ( f - out , Locate [ i ,1] , ’’ , Locate [ i ,2] , ’’ ) ;
    Visible [0 ]∶ = 0 ;
    End
    Else Visible[0 ]∶ = 100 ;
If Top = 0 Then Writeln ( f - out )
Else
For i ∶ = 1 To Top Do
  Begin
  I f Visible[ i - 1] = Visible[ i ] - 1 Then
      Write ( f - out , Locate [Visible[ i] + 1 ,1] , ’’ ,
Locate [Visible[ i] + 1 ,2] , ’’ )
      Else Write( f- out , Locate[ Visible [ i] ,1 ] , ’’ ,
Locate[ Visible [ i] ,2 ] , ’’ ,
Locate[ Visible [ i] + 1,1 ] , ’’ ,
Locate[ Visible [ i] + 1,2 ] , ’’ ) ;
  I f Visible[ i + 1] < > Visible[ i ] + 1
      Then Writeln( f - out ) ;
  End;
End ;
Procedure Find;                                                   {主过程 }
Var i : Word;
Begin
While Not ( Eof ( f - in) ) Do
  Begin
    Readln( f - in, n) ;
    For i∶ = 1 To n Do
    Begin
      Read( f- in, Locate [ i ,1] , Locate[ i ,2] ) ;
      a [ i, 1]∶ = Locate[ i,1 ] ;
      a [ i, 2]∶ = Locate[ i,2 ] ;
    End;
    Readln( f - in, b[1 ] , b[ 2] ) ;
    a [ n + 1]∶ = a [1 ] ;
· 9 6 ·    Top ∶ = 0 ;                                                           {读入数据     }
    If Not (Ok) Then Writeln( f - out , ’ NO FENCE’ )   {如果不合法                   }
      Else Begin
            Top ∶ = 0 ;
            For i∶ = 1 To n Do                               {寻找可见边         }
              Judge( i ) ;
            Print ;
            End;
    Readln( f - in) ;
    Writeln( f - out ) ;
  End;
End ;
Begin
Init ;                                                                   {打开文件                       }
Find;                                                                   {主过程 }
Close ( f - in) ;
Close ( f - out ) ;
End .
第二题: 算术级数
    (1 ) 解题思路
本题可以用简单的两重循环来解决。分别对首项和公差进行循环,但要注意题目要
求将公差相同的级数放在一起(由输出示例可知) ,所以将公差的循环放在外层。而且每
个公差的信息只打印一次,所以用一个变量 before 来记录上一个级数的公差,以免打印重
复。
(2 ) 参考程序
Var Can : Ar ray[0 . . 10000] Of Boolean ;                 {记录一个数是否为双平方数 }
    f- in, f - out : Text ;                                     {输入、 输出文件 }
    m, n : Word;
    Total : Word; {记录级数的总数 }
    Before : Word; {记录上一次级数的公差 }
Procedure Init ; {打开文件并找出所有的双平方数 }
Var i , j : Word;
Begin
Assign( f - in, ’ arith .dat’ ) ;
· 0 7 ·Reset ( f - in) ;
Assign( f - out ,’ arith . sol’ ) ;
Rewrite( f - out ) ;
Fillchar (Can, Sizeof (Can) , 0) ;
For i ∶ = 0 To 100 Do
  For j∶ = 0 To 100 Do                                       {找出所有的双平方数 }
  I f ( i * i + j * j < = 10000) Then Can[ i * i + j * j]∶ = True ;
End ;
Procedure Judge( b, a : Word) ;                         {判断首项为 a 公差为 b的级数是 }
{否满足要求         }
Var i , j : Word;
Begin
For i ∶ = 0 To ( n - 1) Do
  If Not (Can[ a + b * i] ) Then Exit ;                             {如果不满足要求则退出    }
If Before < > b Then                                               {如果上一次的公差不为 b   }
    Begin                                                         {则打印信息至文件         }
    Writeln( f - out ) ;
    Writeln( f - out , ’ Difference of ’ , b , ’ :’ ) ;
    End;
For i ∶ = 0 To ( n - 1) Do
  Write ( f - out , a + b * i, ’’ ) ;
Writeln( f- out ) ;
Before ∶ = b;
Inc( Total) ;                                                             {总数加 1 }
End ;
Procedure Find;                                                   {读入数据并找出所有的级数 }
Var i , j : Word;
Begin
While Not ( Eof ( f - in) ) Do
  Begin
  Readln( f - in , n, m) ;
  Total ∶ = 0 ;
  Before ∶ = 0;
  Writeln( f - out , ’ Arithmetic progressions of length ’ , n) ;
  Writeln( f - out , ’ taken f rom bisquares within the range’ ) ;
  Writeln( f - out , ’ from 0 to ’ , m, ’ :’ ) ;
· 1 7 ·  For i ∶ = 1 To (m Div (n - 1 ) ) Do
    For j∶ = 0 To m - ( n - 1) * i Do
    Judge ( i, j) ;
  Writeln( f - out ) ;
  Writeln( f - out , ’ There are ’ , Total ,’progressions .’ ) ;
  Writeln( f - out ) ;
  End;
End ;
Begin
Init ;                                                                   {打开文件并初始化         }
Find;                                                                   {找出所有的级数                 }
Close ( f - in) ;
Close ( f - out )
End .

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