设为首页 | 加入收藏夹

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

2012-6-2 18:30:59 作者:计算机基础知识试题 录入:应序康 访问:6690 次 被顶:2 次 字号:【
摘要:第一题: 低价买入,更低价买入 (1 ) 解题思路我们从题目中的例子来分析此题:如果第一次购买股票是在第一天,那么如何选择第二次购买股票的时间呢 ? 显然第二次购买股票的价格应比第一次的低,而且我们应该选择从这一天开始能购买股票的天数最多的...
第一题: 低价买入,更低价买入
    (1 ) 解题思路
我们从题目中的例子来分析此题:如果第一次购买股票是在第一天,那么如何选择第
二次购买股票的时间呢 ? 显然第二次购买股票的价格应比第一次的低,而且我们应该选
择从这一天开始能购买股票的天数最多的那一天。这样如果我们用数组 List 来记录由
这一天开始能购买股票的最多天数,那么我们能得到如下的关系:
List [m] = Max{List [ i] + 1}   ( i是第 m + 1~n天中所有价格低于第 m 天的那些天)
· 4 9 ·由上面的关系,我们很容易用动态规划方法从后至前地算出 List 中每个元素的值。
初始条件是 List [ i] = 1, i∈(1, n)。
这样所求的最多天数就是 Max{List [ i] , i∈( 1, n) }。
现在余下的问题是怎样找出所有不同的序列。如果不考虑序列是否相同,那么我们
很容易写出下面的递归过程(Before 为上一次购买的时间, Len为需购买的天数) :
Procedure Find(Before , Len) ;
Begin
  If   Len = 1 Then   总数加 1
      Else
      For i←Before + 1 To n
        I f (第 i 天的价格 <第 Before 天的价格) And
            ( List [ i] = Len)   Then   Find( i , Len - 1) ;
End ;
我们来分析产生重复的原因: 我们已经避免了相同天数引起的重复,关键是怎样去
掉由不同天数所引起的相同序列。我们在选择每一次购买时间时,可能出现不同的时间
有相同的价格,而且它们的 List 值都满足要求, 这就是重复出现的原因。对于这些相同
价格的时间,我们选择哪一个呢 ? 我们发现从最早时间开始的序列包含了所有有其它时
间开始的序列,所以我们只选择最早的时间购买即可。所以我们在进行下一次递归之前,
先判断这天在所有价格相同的时间里是否是最早的,如果是在向下搜索。
(2 ) 参考程序
Var n : Word;
    Price : Ar ray[1 . . 5000 ] Of Word;                   {每天股票的价格           }
    List   : Ar ray[ 1 . . 5000 ] Of Word;
    Max, Total : Word;                                       {购买的最多天数和这种    }
{序列的数目                     }
Procedure Init ;                                                   {读入数据并初始化         }
Var f :Text ;
    i :Word ;
Begin
Assign( f ,’ input . txt’ ) ;
Reset ( f ) ;
Readln( f , n) ;
For i ∶ = 1 To n Do
  Readln( f , Price [ i] ) ;
Close ( f ) ;
Max ∶ = 0 ;
Total ∶ = 0;
· 5 9 ·End ;
Procedure Calc;                                                   {找出最多的购买天数             }
Var i , j : Word;
Begin
For i ∶ = 1 To n Do
  List [ i]∶ = 1;                                                     {赋初值为 1 }
For i ∶ = n Downto 1 Do
  For j∶ = i + 1 To n Do
I f (Price[ j ] < Price [ i] ) And ( List [ j] > List [ i] - 1 )
      Then List [ i]∶ = List [ j] + 1; {计算由每天开始最多的 }
{购买天数 }
For i ∶ = 1 To n Do
  If List [ i] > Max Then Max ∶ = List [ i ] ; {找出最多的购买天数 }
Writeln(’ Longest length ’ , Max) ;
End ;
Procedure Find(Before , Len : Word) ;                   {找出所有不同的序列       }
Var i , j:Word;
Begin
If Len = 0 Then Inc( Total )                                 {如果找到则总数加 1 }
Else
For i ∶ = Before + 1 To n Do
  If ( (Before = 0) Or (Price [Before ] > Price [ i] ) ) And (List [ i ] = Len )
      Then Begin
        j ∶ = 0 ;
        For j∶ = Before + 1 To i - 1 Do
        I f (List [ j ] = Len) And (Price[ j ] = Price[ i ] )
            Then Begin
                  j ∶ = i ;
                  Break ;
                End;
        If j < i Then Find( i , Len - 1) ;                 {如果是最早的时间       }
      End;
End ;
Begin
Init ;                                                                   {读入数据并初始化         }
· 6 9 ·Calc ;                                                                   {找出最多的购买天数             }
Find(0 , Max) ;                                                     {找出所有不同的序列             }
Writeln(’ Total with this length ’ , Total ) ;
End .
第二题: 重叠的方框
    (1 ) 解题思路
为了找出方框的叠放顺序,首先要找出每个方框的位置。由于题目中已经说明,每个
方框的 4 个边均有一部分可见,所以我们很容易得出每个方框的位置。然后我们对每个
方框的 4 个边进行搜索,如果发现有另一个字母出现在这个方框的边上,可知那一个字母
代表的方框覆盖了这一个方框。例如一个用字母 ‘A’ 标注的方框边上有字母 ‘B’ ,那么字
母 ‘B’ 标注的方框一定覆盖字母 ‘A’ 标注的方框。这样我们就得到了方框间的覆盖关系,
很容易用一个递归过程来找出所有的叠放顺序:
Procedure   Find( k) ;
Begin
  If   k > 方框总数   Then   打印结果
      Else   Begin
        找一个不被剩余方框覆盖的方框;
        记录此方框;
        去除这个方框与其它方框的覆盖关系;
        Find( k + 1) ;
        恢复这个方框与其它方框的覆盖关系;
      End;
End ;
(2 ) 参考程序
Type St r30 = St ring[ 30 ] ;
    Line   = Ar ray[’ A’. .’ Z’ ] Of Byte;
Var Frame : Ar ray[’ A’. .’ Z’ ,1 . .4] Of Byte;       {记录每个方框的位置           }
    Num   : Word;                                           {方框的数目 }
    a : Ar ray[ 1 . . 30 ] Of St r30 ; {记录整个图形 }
    s : Set Of Byte;
    Cover : Ar ray[’ A’. .’ Z’ ] Of Line ; {方框之间互相覆盖的关系 }
    h, w : Word; {图形的大小 }
    Exist : Array[1 . .26] Of Char ; {每个方框的字母 }
    Result : Ar ray[ 1 . . 26 ] Of Byte ;                     {方框的叠放顺序           }
Procedure Init ;                                                   {读入图形并初始化数据    }
Var f : Text ;
· 7 9 ·    i : Word;
Begin
Assign( f , ’ input . txt’ ) ;
Reset ( f ) ;
Readln( f , h) ;
Readln( f , w) ;
For i ∶ = 1 To h Do
  Readln( f , a[ i] ) ;
Close ( f ) ;
Fillchar (Frame, Sizeof (Frame ) , 0) ;
Fillchar (Cover , Sizeof (Cover ) , 0 ) ;
s∶ = [ ] ;
End ;
Procedure Analyse;                                                 {分析方框间的叠放顺序    }
Var i , j : Word;
    Ch : Char ;
Begin
For i ∶ = 1 To h Do
For j ∶ = 1 To w Do
  If ( a[ i, j ] < > ’.’ ) Then
    Begin
    I f (Frame[ a [ i , j] ,2] = 0 ) Then
      Frame[ a[ i , j] ,2 ]∶ = i ;
    Frame [ a[ i , j ] ,4 ]∶ = i ;
    I f (Frame[ a [ i , j] ,1] = 0 ) Or (Frame[ a [ i , j] ,1] > j) Then
      Frame[ a[ i , j] ,1 ]∶ = j ;
    I f (Frame[ a [ i , j] ,3] < j) Then Frame[ a[ i , j] ,3 ]∶ = j ;
    End;                                                                 {找出每个方框的位置             }
Num ∶ = 0;
For Ch ∶ = ’ A’To ’ Z’Do
  If Frame[Ch ,1] > 0 Then
    Begin Inc( Num) ; Exist [Num]∶ = Ch; End;             {找出每个方框对应的字母 }
{及方框的总数                   }
For Ch ∶ = ’ A’To ’ Z’Do
  If Frame[Ch ,1] > 0 Then
  Begin
· 8 9 ·  For j ∶ = Frame[Ch, 1] To Frame[Ch, 3] Do
    Begin
    I f a[ Frame [Ch ,2] , j] < > Ch Then Cover [ a [Frame[Ch,2 ] , j ] , Ch]∶ = 1;
    I f a[ Frame [Ch ,4] , j] < > Ch Then Cover [ a [Frame[Ch,4 ] , j ] , Ch]∶ = 1;
    End;
  For j ∶ = Frame[Ch, 2] To Frame[Ch, 4] Do
    Begin
    I f a[ j, Frame[Ch,1 ] ] < > Ch Then Cover [ a [ j , Frame [Ch ,1] ] , Ch]∶ = 1;
    I f a[ j, Frame[Ch,3 ] ] < > Ch Then Cover [ a [ j , Frame [Ch ,3] ] , Ch]∶ = 1;
    End;
  End;                                                                   {找出方框间的覆盖关系    }
End ;
Procedure Print ;                                                   {打印一组解   }
Var i : Word;
Begin
For i ∶ = Num Downto 1 Do
  Write (Exist [Result [ i] ] ) ;
Writeln;
End ;
Procedure Find( k : Word) ;                                   {寻找叠放的顺序     }
Var i , j : Word;
    Save : Line ;
Begin
If k > Num Then Print                                       {找到一组解则打印   }
Else For i∶ = 1 To Num Do
      I f Not ( i In s) Then
        Begin
        For j ∶ = 1 To Num Do
          If Cover [Exist [ j] , Exist [ i] ] > 0 Then   {如果有覆盖它的方框           }
            Begin
              j ∶ = Num + 1;
              Break ;
            End;
        I f j = Num Then Begin
· 9 9 ·            Save∶ = Cover [ Exist [ i] ] ;
            Include( s, i ) ;                                 {保留数据           }
            Result [ k]∶ = i ;
            Fillchar (Cover [ Exist [ i ] ] , Sizeof (Cover [Exist [ i] ] ) ,0) ;
            Find( k + 1) ;
            Cover [ Exist [ i ] ]∶ = Save ;
            Exclude( s, i) ;                                 {恢复数据           }
            End;
        End;
End ;
Begin
Init ;                                                                   {读入图形并初始化数据    }
Analyse ;                                                         {分析方框间的覆盖关系    }
Find(1) ;                                                         {寻找叠放的顺序                 }
End .
(3 ) 运行结果
INPUT:
10
10
HHH AAAA F . .
H F H GGGA F G .
HHH CCCA F G J
G F A CDDA F G J
G F A CDCA F G J
. F A AE E E F . J
. . . . ED ED . J
. . I BBB I I I J
. . I B E B E J I J
. . I BBB I I I .
OUPUT :
JGCDFAEIHB
JGCDFAHEIB
JGCDFAEHIB
JGCDFAEIBH

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