设为首页 | 加入收藏夹

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

2012/6/2 18:34:30 作者:计算机基础知识试题 录入:应序康 访问:11644 次 被顶:7 次 字号:【
摘要:第一题: 给奶牛挤奶 (1 ) 解题思路本题要求出有人挤奶和空闲的最长时间段的长度。由于时间均为整数,且时间的最大值为32 000,所以我们用一个大小为32 000 的byte 型数组来记录每个时间是否有人挤奶。然后再找出最长的有人挤奶和空...
第一题: 给奶牛挤奶
    (1 ) 解题思路
本题要求出有人挤奶和空闲的最长时间段的长度。由于时间均为整数,且时间的最
大值为32 000,所以我们用一个大小为32 000 的byte 型数组来记录每个时间是否有人挤
奶。然后再找出最长的有人挤奶和空闲的时间段。注意题目中要求时间是从第一次挤奶
时间开始至最后一次挤奶结束,而不是从 0 开始至 32 000。
(2 ) 参考程序
Var Time : Array[0 . . 32000] Of Byte ;                   {记录每个时间是否有人挤奶 }
    Milk : Ar ray[ 0 . . 1] Of Word;                             {有人挤奶和空闲的最长时间 }
    n   : Word ;                                                   {农夫人数                 }
Procedure Init ;                                                   {读入数据并统计每个时间是否有人}
{挤奶               }
Var f   : Text ;
    s, e: Word;                                                   {挤奶的起始时间和结束时间 }
    i   : Word;
Begin
Fillchar ( Time , Sizeof ( Time) , 0 ) ;
Assign( f , ’ input .c1’ ) ;
· 0 3 1 ·Reset ( f ) ;
Readln( f , n) ;
For i ∶ = 1 To n Do
  Begin
  Readln( f , s, e) ;
  Fillchar ( Time[ s] , e - s, 1) ;                         {从 e 到 s 时间内有人挤奶   }
  End;
Close ( f ) ;
Fillchar (Milk, Sizeof ( Milk) , 0 ) ;
End ;
Procedure Calc;                                                   {计算有人挤奶和空闲的最长时间 }
Var First , Last : Word;                                     {工作的起始时间和结束时间 }
    i , j , State : Word;                                     {state存放此时间内是空闲 }
{还是有人挤奶             }
Begin
Last∶ = 32000 ;
First∶ = 0 ;
While Time [Last ] = 0 Do
  Dec( Last ) ;
Inc( Last ) ;
While Time [First ] = 0 Do
  Inc(First ) ;
{计算工作的起始和结束时间 }
State∶ = 1 ;
j ∶ = 0 ;
For i ∶ = First To Last Do
  If Time [ i] = State Then Inc ( j)
    Else Begin
          I f j > Milk[State]
              Then Milk[State]∶ = j;                   {j 中存放此时间段的长度   }
          State ∶ = 1 - State;
          j∶ = 1 ;
          End;
End ;
Procedure Print ;                                                   {打印结果                 }
Begin
Writeln(’ Longest continuous time = ’ , Milk[1] ) ;
Writeln(’ Longest idle time = ’ , Milk[ 0] ) ;
End ;
· 1 3 1 ·Begin
Init ;                                                                   {读入数据并初始化         }
Calc ;                                                                   {计算两个最长时间段的长度 }
Print ;                                                                 {打印结果                 }
End .
第二题: 谷仓迷宫
    (1 ) 解题思路
此题的关键是找出每个厩到其它厩的总距离。由于厩的总数不大于 2500,所以我们
可以用宽度搜索来计算总距离:
我们用数组 Stack 来记录宽度搜索的节点,用 Open 指向待扩展的节点,用 Top 记录
数组中节点的数目。下面是宽度搜索的框架:
总距离←0 ;
Open←1 ;
Top←2 ;
将起始厩加入数组中;
While Open < Top Do
  Begin
  找出从 Open 指向的厩能走到的厩;
  I f   此厩没有走过   Then
      Begin
        将此厩加入数组;
        总距离 + 此厩到起始厩的距离;
      End ;
    Open + 1 ;
  End;
(2 ) 参考程序
Type Code = Record
            Id, Step : Word;                         {厩的编号和到起始厩的距离 }
            End;
Var p   : Word;                                                   {质数 p     }
    b, c : Array[1 . . 4 ] Of Longint ; {对应的参数 }
    Min   : Real ; {最短平均距离 }
    Which: Word; {中心厩的编号 }
    Stack : Ar ray[1 . . 2500 ] Of Code ; {宽度搜索用的数组 }
    Open , Top : Word; {宽度搜索用的下标指针 }
    Now   : Longint ; {一个厩到其它厩的距离总和 }
· 2 3 1 ·Procedure Init ; {读入质数 p 和参数 b, c }
Var f : Text ;
    i : Word;
Begin
Assign( f , ’ input .c2’ ) ;
Reset ( f ) ;
Read( f , p) ;
For i ∶ = 1 To 4 Do
  Read( f , b[ i] , c[ i ] ) ;
Close ( f ) ;
Min ∶ = 10000;
End ;
Procedure Judge;                                                   {判断是否出现重复         }
Var i : Word;
Begin
For i ∶ = 1 To Top - 1 Do
  If Stack[ Top] . Id = Stack [ i] . Id Then Exit ;
Stack[ Top] .Step ∶ = Stack[Open] .Step + 1 ;
Inc( Now, Stack[ Top] . Step) ;                                 {如果不重复则总距离加    }
Inc( Top) ;                                                         {Step,并加入数组         }
End ;
Procedure Find;                                                   {找出中心厩   }
Var i , j:Word;
Begin
For i ∶ = 0 To p - 1 Do                                               {计算每个厩到其它厩的距离总和 }
  Begin
  Now ∶ = 0 ;
  Stack[1 ] .Id  ∶ = i;
  Stack[1 ] .Step ∶ = 0 ;
  Open ∶ = 1 ;
  Top ∶ = 2;
  While Open < Top Do                                       {循环直至走遍所有厩   }
    Begin
    For j ∶ = 1 To 4 Do
· 3 3 1 ·      Begin
      Stack[ Top] . Id ∶ = ( b[ j] * Stack[Open] . Id + c[ j ] ) Mod p;
      Judge ;                                                     {判断新节点是否与原先节点重复 }
      End;
    Inc(Open) ;
    End;
  I f Now/ (p - 1 ) < Min Then                                   {如果平均距离小于当前最小值 }
      Begin                                                       {则记录 }
      Min ∶ = Now/ ( p - 1) ;
Which ∶ = i ;
End;
End;
End ;
Procedure Print ;                                                   {打印结果     }
Var f : Text ;
Begin
Assign( f , ’ out .c2’ ) ;
Rewrite( f ) ;
Writeln( f , Which, ’’ , Min: 0 ∶ 4 ) ;
Close ( f ) ;
End ;
Begin
Init ;                                                                   {读入数据                       }
Find; {找出中心厩                     }
Print ;                                                                 {打印结果                       }
End .
第三题: 网络通讯
    (1 ) 解题思路
本题要求出最少损坏多少个计算机,才能使计算机 a 和 b 之间不能通讯。它的数学
模型就是在一个图中最少去掉多少个点,才能使指定的两个点不能连通。它实际上等于
这两点之间互不相交的路的最多数目。对于此类问题,在图论中称作求最小割集问题,它
可以用求最大流的方法来解决。
在求最大流之前,先将原图作一些变换:将图中除了 a、 b 两点外的点 i 都拆成两个点
i和点 n + i( n 为图中点的数目) ,这两点之间连一条容量为 1 的有向边 i→n + i ;对于原图
中的任意一条无向边( i , j ) ,在新图中变为有向边 n + i→j 和 n + j→i ,这些边的容量为∞
(下面的程序中为 100) ;将点 a 的边全改为流出的边,点 b 的边全改为流入的边。例如图
· 4 3 1 ·3 .9 .1 中,点 a 和点 b分别为点 1 和点 5。
对变换后的图求最大流,其流量即为所求的最少数目,其对应的已经标号的点即为所
去掉的点(求最大流的算法及证明参见《运筹学》)。
图   3 . 9 . 1
(2 ) 参考程序
Const Max = 100;                                                   {边的最大流量 }
Type Node = Record                                                 {每点标号时的类型         }
            What : Word;
            Back : Word;
            End;
Var n,m, a , b : Word;
    Which   : Word ;                                               {记录是哪个网络                 }
    g - in , g - out : Text ;                                     {输入输出文件       }
    f , c : Ar ray[1 . . 80,1 . .80] Of Byte ;                 {每条边的流量和容量       }
    Num   : Word;                                                   {最少损坏计算机数目             }
    Stack : Ar ray[1 . . 80] Of Node ;                             {标号时所用的数组 }
    Open , Top : Word; {待扩展点的下标和点的数目 }
    s     : Set Of Byte ; {已标号的点 }
Procedure Init ; {打开文件 }
Begin
Assign(g - in,’ input . c3’ ) ;
Reset ( g - in ) ;
Assign(g - out ,’ out .c3’ ) ;
Rewrite( g - out ) ;
Which∶ = 0 ;
End ;
· 5 3 1 ·Procedure Readdata ; {读入数据并初始化网络 }
Var i   : Word;
    x, y: Word;
Begin
Fillchar ( c , Sizeof ( c) ,0 ) ;
Fillchar ( f , Sizeof ( f ) ,0) ;
Readln( g - in, n,m, a , b) ;
If n = 0 Then Exit ;
For i ∶ = 1 To m Do
  Begin
Readln( g - in, x, y) ;
  I f x = a Then c[ x ,y]∶ = Max
      Else
      If x = b Then c [y + n, x]∶ = Max
        Else
        I f y = a Then c [y ,x]∶ = Max
            Else
            If y = b Then c[ x + n ,y]∶ = Max
              Else Begin
                c[ x + n ,y]∶ = Max;
                c[ y + n, x]∶ = Max;
              End;
  End;
For i ∶ = 1 To n Do
  If Not ( i In [ a ,b] ) Then c [ i , i + n]∶ = 1 ;
End ;
Function Find : Boolean;                                           {找一条增流路径                 }
Var i : Word;
Procedure Increase;                                               {对增流路径进行增流             }
Var j : Word;
Begin
j ∶ = Top;
· 6 3 1 ·While Stack[ j] .Back > 0 Do
  With Stack[ j ] Do
  Begin
    If f [Stack[Back] .What ,What ] < c[Stack[Back] .What , What ]
      Then Inc ( f [Stack[Back] .What , What ] )
      Else Dec( f [What , Stack[Back] .What ] ) ;
    j∶ = Stack[ j ] .Back;
  End;
End ;
Begin
Find ∶ = True ;
Open ∶ = 1 ;
Top ∶ = 1;
Stack[ 1] .What∶ = a ;
Stack[ 1] .Back∶ = 0;
s∶ = [ a ] ;
While Open < = Top Do
  With Stack[Open] Do
  Begin
    For i∶ = 1 To 2 * n Do
    I f Not ( i In s ) And ( ( c[What , i] > f [What , i ] ) Or ( f [ i ,What ] > 0) )
        Then Begin
        Inc( Top) ;
        Stack[ Top] .What∶ = i ;
        Stack[ Top] .Back∶ = Open;
        Include( s, i) ;
        I f i = b Then Begin                                 {如果找到则增流并退出    }
            Increase ;
            Exit ;
          End;
        End;
    Inc (Open) ;
  End;
Find ∶ = False ;                                                     {未找到增流路径                 }
End ;
Procedure Print ;                                                   {打印结果     }
· 7 3 1 ·Var i : Word;
Begin
Inc(Which) ;
Writeln( g - out , ’ Network #’ , Which) ;
Writeln( g - out , Num) ;
For i ∶ = 1 To n Do
  If i In s - [ a, b] Then Write( g - out , i, ’’ ) ;
Writeln( g - out ) ;
End ;
Procedure Main;                                                   {主过程   }
Begin
Repeat
  Readdata ;                                                       {读入数据并初始化         }
  If n > 0 Then
    Begin
      Num∶ = 0 ;
      While Find Do                                               {反复寻找增流路径         }
      Inc( Num) ;
      Print ;                                                             {打印结果                       }
    End;
Until n = 0 ;
Close (g - in) ;
Close (g - out ) ;
End ;
Begin
Init ;                                                                   {打开文件                       }
Main ;                                                                   {主过程 }
End .

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