设为首页 | 加入收藏夹

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

2012-6-2 18:22:16 作者:计算机基础知识试题 录入:应序康 访问:6447 次 被顶:3 次 字号:【
摘要:第一题: 分数排序 (1 ) 解题思路我们用两个 Byte 型的数组来存放一个分数。先找出所有满足条件的分数,再将它们按大小顺序排序。题目中要求 N≤100,所以分数的数目不会超过 10000,对其进行存放和排序,在空间、 时间上都不成问题...

第一题: 分数排序
    (1 ) 解题思路
我们用两个 Byte 型的数组来存放一个分数。先找出所有满足条件的分数,再将它们
按大小顺序排序。题目中要求 N≤100,所以分数的数目不会超过 10000,对其进行存放
和排序,在空间、 时间上都不成问题。
(2 ) 参考程序
Type Denominator = Array[1 . . 2 ] Of Byte;               {存放分数的类型 }
· 7 4 ·Var a : Array [ 1 . . 10000] Of Denominator ; {a 中存放所有的分数 }
    n, Num: Word ; {n为分母的最大值 }
{Num 为分数的数目 }
Procedure Init ; {读入 n并初始化 Num }
Begin
Repeat
  Write (’ Enter the maximum denominator :’ ) ;
  Readln( n) ;
  If Not ( n In [1 . .100 ] ) Then Writeln(’ Input er ror !’ ) ;
Until n In [1 . . 100 ] ;
Num ∶ = 0 ;
End ;
Procedure Calc; {找出所有的分数并排序 }
Var i , j : Word;
    Mid : Denominator ; {交换分数时的中间变量 }
Procedure Add(x ,y : Word) ; {判断分数 y / x是否为最简 }
{分数,是,则放入 a 中 }
Var k : Word ;
Begin
For k ∶ = 2 To y Do
  If (x Mod k = 0) And (y Mod k = 0 ) Then Exit ;
Inc( Num) ;
a[ Num, 1]∶ = x;
a[ Num, 2]∶ = y;
End ;
Begin
For i ∶ = 2 To n Do
  For j∶ = 1 To i-1 Do                                       {找出所有除 “0 / 1” 和 “1 / 1”  }
  Add( i , j ) ;                                                     {外的分数     }
For i ∶ = 1 To Num Do
For j ∶ = i + 1 To Num Do
  If ( a[ i,1 ] * a [ j, 2] < a[ i ,2 ] * a[ j ,1 ] ) Then
    Begin
    Mid∶ = a [ i] ;
    a[ i ]∶ = a [ j] ;
· 8 4 ·    a[ j ]∶ = Mid;
    End;                                                                 {将分数排序                     }
End ;
Procedure Print ;                                                   {打印排序后的分数         }
Var i : Word;
Begin
Write(’ 0 / 1’ , # 9 ) ;                                                 { # 9 为制表符  }
For i ∶ = 1 To Num Do
  Write ( a [ i, 2] , ’ / ’ , a[ i ,1 ] , # 9) ;
Writeln(’ 1 / 1’ , # 9) ;
Writeln(’ There were ’ , Num + 2, ’fractions .’ ) ;
End ;
Begin
Init ;                                                                   {读入数据并初始化         }
Calc ;                                                                   {找出分数并排序                 }
Print ;                                                                 {打印   }
End .
(3 ) 运行结果
Enter the maximum denominator : 10
0 / 1 1/ 10 1 / 9 1 / 8 1 / 7 1/ 6 1 / 5 2 / 9 1 / 4 2/ 7
3 / 10 1/ 3 3 / 8 2 / 5 3 / 7 4/ 9 1 / 2 5 / 9 4 / 7 3/ 5
5 / 8 2/ 3 7 / 10 5 / 7 3 / 4 7/ 9 4 / 5 5 / 6 6 / 7 7/ 8
8 / 9 9/ 10 1 / 1
There were 33 f ractions .
第二题: 最大的谷仓
(1 ) 解题思路
对于任务二,农场最大为 20 * 20,所以我们可以用一个数组来记录每个网格是否有
障碍物,再对以每个网格为左上角的谷仓进行判断。但是任务三中农场的大小将达到
1000 * 1000 ,我们将无法记录每个网格的状态,这是本题的主要难点。由于任务三的程序
能同时解决任务二,所以我们直接处理任务三。
题目中要求谷仓不与任何障碍物相邻,这样编程很不方便。所以我们首先将每个障
碍物扩大一圈,这样我们只需让谷仓不与障碍物重叠即可,见图 3 .2 .1。
我们无法记录每个网格的状态,但是我们发现由于障碍物的数目并不多 (最多为
20 ) ,所以农场上许多相邻的网格可以合并成一个长方形的大方格,使得这个方格中的每
个网格的状态相同,即是都为空或都有障碍物。那么我们只要记录这个方格的状态,就可
· 9 4 ·图   3 . 2 . 1
以记录很多网格的状态。现在的问题是,我们怎样找出这些方格呢 ? 题目中关键的是障
碍物的位置,所以我们以所有障碍物的四边作为格线,将整个农场进行打格,见图 3 .2 .2。
显然每个方格中的网格具有同样的状态,而且我们对这个变换后的农场求得的最大谷仓,
一定与原有的农场中的相同(证明留给读者)。
图   3 . 2 . 2
由于障碍物的数目最大为 20,所以除了农场的四边以外,横、 竖的格线最多有 40 条,
这样变换后的农场最大为 41 * 41,足可以用数组来存放其每格的状态。注意此时每格的
长宽要由格线的位置来决定。
(2 ) 参考程序
Const Maxnum = 20;                                                 {障碍物的最大数目         }
Type Code = Record                                                 {存放障碍物的类型         }
x1, y1, x2 ,y2 : Integer ;
End;
    Ruler = Array[0 . . 2 * Maxnum + 1] Of Word ;
Var f : Text ;
    a : Ar ray[ 1 . .Maxnum] Of Code ;                     {存放障碍物               }
    m, n : Word;                                                   {农场的长宽   }
    Num: Integer ;                                               {障碍物的数目 }
    Max: Longint ;                                               {最大谷仓的面积                 }
    Total : Word;                                                   {最大谷仓的数目                 }
· 0 5 ·    Map : Ar ray[0 . . 2 * Maxnum + 1 ,0 . . 2 * Maxnum + 1 ] Of Byte;
{变换后的农场 }
    Ry, Rx     : Ruler ;                                     {变换后的农场中每格的坐标 }
    Topx , Topy : Word;                                       {变换后农场的长宽   }
Procedure Init ;                                                   {打开文件     }
Begin
Assign( f , ’ barn . in’ ) ;
Reset ( f ) ;
End ;
Procedure Readdata ;                                               {读入数据并初始化         }
Var i : Word;
    x, y, w, h : Integer ;
Begin
Readln( f , Num) ;
If Num < 0 Then Halt ;
Readln( f , m, n ) ;
For i ∶ = 1 To Num Do
  With a[ i ] Do
  Begin
    Readln( f , y, x, w, h) ;
    x1 ∶ = x-Byte (x > 1 ) ;
    y1∶ = y-Byte ( y > 1) ;
    x2 ∶ = x + w-Byte ( x + w > n) ;
    y2∶ = y + h-Byte( y + h > m) ;
  End;
Max ∶ = 0 ;
Total ∶ = 0;
Fillchar (Map , Sizeof (Map) , 0 ) ;
End ;
Function In - order (Var b :Ruler ) : Word;                 {将数组 b 的数排序并去掉重复的数}
Var i , j:Word;
    Mid:Word;
    Top:Word;
Begin
For i ∶ = 1 To 2 * Num Do
· 1 5 ·  For j∶ = i + 1 To 2 * Num Do
  I f b[ i ] > b[ j ] Then
    Begin
      Mid ∶ = b[ i] ;
      b[ i]∶ = b[ j ] ;
      b[ j]∶ = Mid;
    End;
Top ∶ = 0;
For i ∶ = 1 To 2 * Num Do
If b[ i] > b[ i - 1] Then
    Begin
    Inc( Top) ;
    b[ Top]∶ = b[ i ] ;
    End;
In - order∶ = Top;
End ;
Procedure Calc;                                                   {将农场进行变换                 }
Var i , j, k : Word;
Begin
Ry[0 ]∶ = 0 ; 
Rx[ 0]∶ = 0;
For i ∶ = 1 To Num Do                                               {找出格线的位置                 }
  With a[ i ] Do
  Begin
    Ry[ 2 * i - 1]∶ = y1 - 1 ;
    If y2 < m Then Ry[ 2 * i]∶ = y2;
    Rx[2 * i - 1 ]∶ = x1 - 1 ;
    If x2 < n Then Rx[2 * i ]∶ = x2;
  End;
Topy ∶ = In - order (Ry) ;
Topx ∶ = In - order (Rx) ;
Ry[ Topy + 1]∶ = m;
Rx[ Topx + 1]∶ = n;                                                   {将格线进行排序整理             }
For k ∶ = 1 To Num Do                                               {找出每格是否有障碍物    }
  With a[ k] Do
  For i ∶ = 0 To Topy Do
  For j ∶ = 0 To Topx Do
    If (Ry[ i] + 1 > = y1) And (Ry[ i] < y2 )
· 2 5 ·      And (Rx[ j ] + 1 > = x1 ) And (Rx[ j ] < x2)
          Then Map[ i , j]∶ = 1;
For i ∶ = 0 To Topy + 1 Do                                     {设置边界           }
  Map[ i, Topx + 1]∶ = 1;
For i ∶ = 0 To Topx + 1 Do
  Map[Topy + 1, i ]∶ = 1 ;
End ;
Function Area( x, y, w, h : Word) : Longint ;               {计算一些方格的面积       }
Var s : Longint ;
Begin
s∶ = (Ry[ y + h] - Ry[ y] ) ;
s∶ = s * (Rx[ x + w] - Rx[ x] ) ;
Area∶ = s;
End ;
Procedure Find;                                                   {找出最大的谷仓及数目    }
Var x,y , w, h : Word ;                                               {谷仓的坐标及长宽         }
    i : Word;
    s : Longint ;
Begin
For x ∶ = 0 To Topx Do
For y ∶ = 0 To Topy Do
  Begin
  w ∶ = 1 ;
  While Map[ y, x + w - 1] = 0 Do
    Begin
    h ∶ = 0;
    Repeat
      Inc ( h) ;
      For i∶ = 1 To w Do
      I f Map[ y + h - 1 ,x + i - 1 ] = 1
          Then Begin
            i ∶ = 0 ;
            Break;
          End ;
    Until i = 0;
    Dec ( h) ;
· 3 5 ·    s ∶ = Area (x ,y, w , h) ;                                     {计算面积   }
I f s > Max Then Begin Max ∶ = s; Total ∶ = 1 ; End
Else If s = Max Then Inc (Total) ;
Inc(w) ;
End;
End;
End ;
Procedure Print ; {打印结果 }
Begin
  Writeln(’ Maximum area = ’ ,Max,
’number of solutions = ’ , Total ) ;
End ;
Procedure Main; {主过程 }
Begin
Repeat {逐个处理每组数据 }
Readdata ; {读入数据 }
Calc; {将农场进行变换 }
  Find; {找出最大的谷仓及数目 }
  Print ; {打印结果 }
Until False ;
End ;
Begin
Init ;
Main ;
End .

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