di3.txt

信息学 (计算机) 奥林匹克训练题 (中级部分) 天津师范大学 李学武 编

 例如：输入的字符为:ABCBAAADDEF                                                  

     其对应的编码表为：                                                          

         A:   2                B:  10                                            

         C:  11                D:  12                                            

         E:  00                F:  O1                                            

 对应的编码为：210111022212120001       总码长为：18                             

 根据该编码，给出编码:010001121110222   则输出字串:FEFDCBAAAA.                   

                                                                                 

 47. 某些密码由 N 个英文字母组成(N〈26), 每个字母的平均使用率为:W1,W2,...        

 ,Wn, 要求编程完成下列任务：                                                     

    ① 键入英文字母及个数；                                                      

    ② 键入Ｎ个英文字母的使用频率；                                              

    ③ 用二进制数对该Ｎ个英文字母进行编码（最短，无二义性）；                    

    ④ 键入字母短文（单词用空格区分），输出相应编码；                            

    ⑤ 键入二进制编码短文，输出译文。                                            

                                                                                 

 48. 将４个红球，３个白球与３个黄球排成一排，共有多少种排法？                    

                                                                                 

 49. 有面值为 M..N 的邮票各一枚，共能拼出多少不同的面额。                        

                                                                                 

 50. 有一个四阶方阵，随机产生 1..16 这 16 个自然数（不重复），依次填入每         

 个方格中。要求用最少的对调次数，使每一行、每一列以及对角线上的四个数之和        

 均相等。打印每一次对调的过程。                                                  

                                                                                 

 51. 微型蓝球赛. 甲,乙两队进行蓝球比赛,结果甲队以S:T 获胜.(T<S<=10, S,T          

 由键盘输入). 比赛中, 甲队得分始终领先(严格大于乙队). 规定以任何方式进一         

 球都只得一分. 编程序打印该比赛的每一种可能的不同的得分过程, 以及所有不同        

 过程的总数.                                                                     

                                                                                 

 52. 求两整型数组错位相加的最大面积.                                             

    设整型数组 C 具有 N 个分量: C=(C1,C2,...,CN), 两相连分量(C[I],C[I+1])        

 可计算一个面积: 若C[I],C[I+1]同号, 则面积 SI=abs(C[I]+C[I+1])/2, 否则,面        

 积等于 (abs(a*C[I])+abs(b*C[I+1]))/2, 其中, a>0,b>0,a+b=1 (详见下图),数         

 组 C 的面积 A=S[1]+S[2]+...+S[N-1].                                             

     编程要求如下:                                                               

  从键盘输入 N, 再输入两个具有 N 个分量的数组: A1,A2:ARRAY [1..N] OF             

 INTEGER; 将 A1,A2 错位相加(详见后面的例子)得数组A3, 求 A3 的面积.编程给         

 出一个错位相加的方案, 使 A3 的面积最大.                                         

    例: 设 N=3, A1=(3,7,2), A2=(-5,7,-4), 则应考虑 9 种情况:                     

                    (1)                         (2)                              

        A1  3  7  2                       3  7  2                                

        A2              -5  7  -4                  -5  7  -4                     

        A3  3  7  2  0  -5  7  -4         3  7  2  -5  7  -4                     

                    (3)                         (9)                              

        A1  3  7  2                                     3  7  2                  

        A2       -5  7 -4       ......     -5  7  -4                             

        A3  3  7 -3  7 -4                  -5  7  -4  0 3  7  2                  

                                                                                 

 53. (工作安排问题) 现有 N (N≤8) 件工作, 分别由 N 个人完成, 每人都完成一        

 件,且只完成一件, 每人完成不同工作的时间不同. 试设计一种分配工作方案, 使         

 完成 N 件工作所需的总时间最少.                                                  

    原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:                               

    第 1 行:        工作任务数(N)                                                

    第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以上各数         

 均为不超过 1000 的正整数.                                                       

    计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数据的        

 形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.                      

    例: 设 EXAM1.TXT 的数据为:                                                   

         4                                                                       

         2  15  13  4                                                            

         10  4  14  15                                                           

         9  14  16  13                                                           

         7  8  11  9                                                             

     对此, 一个正确的输出可以是                                                  

         1-4, 2-2, 3-1, 4-3                                                      

         TOTAL=28                                                                

                                                                                 

 54. 求Ｎ个字符串的最长公共子串，Ｎ＜＝２０，字符串长度不超过２５５。            

    例如：Ｎ＝３，由键盘依次输入三个字符串为                                     

      What is local bus ?                                                        

      Name some local buses.                                                     

      local bus is a high speed I/O bus close to the processer.                  

 则最长公共子串为"local bus"。                                                   

 ( 参看程序 9 )                                                                                

 

 55. (液晶显示) 下图是用液晶七笔阿拉数字表示的十个数字，我们把横和竖的一         

 个短划都称为一笔，即７有３笔，８有７笔等。请把这十个数字重新排列，要做到        

 两相邻数字都可以由另一个数字加上几笔或减去几笔组成，但不能又加又减。比如        

 ７→３是允许的，７→２不允许。编程打印出所有可能的排列。                        

    如：４１０７３９５６８２。                                                   

                                                                                 

 56. (Ｎ阶梵塔) 有Ｋ根棒，第一根上放Ｎ片大小不等的圆盘，并保持上小下大的         

 顺序。现将Ｎ片圆盘从第１根移至第Ｋ根，移动中均保持上小下大的顺序，问最少        

 移几次方得结果，求出移动方案。                                                  

 ( 参看程序 3 )                                                                                

 

 57. 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单        

 位：天）                                                                        

            任务  │Ｊ1  Ｊ2  Ｊ3  Ｊ4  Ｊ5  Ｊ6                                 

        ─────┼───────────────                               

          印刷车间│ ３  １２  ５   ２   ９  １１                                

          装订车间│ ８  １０  ９   ６   ３  １                                  

 如何安排加工顺序，使加工时间最少。                                              

                                                                                 

 58. 将７万元投资到Ａ，Ｂ，Ｃ三项目上，其利润见下表：                            

        投资额(万元)│ １    ２    ３    ４    ５    ６    ７                    

        ──────┼────────────────────                   

            项  Ａ  │0.11  0.13  0.15  0.24  0.24  0.30  0.35                   

                Ｂ  │0.12  0.16  0.21  0.25  0.25  0.29  0.34                   

            目  Ｃ  │0.08  0.12  0.20  0.26  0.26  0.30  0.35                   

  如何分配投资额，使获得的利润最大。                                             

                                                                                 

 59. 无根树与通常所说的树（有根树）很相似，它包含有节点和枝，但不含有根。        

 无根树节点之间只有相邻关系。如图一所示，是一棵有七个节点的无根树，以图一        

 的Ａ为根节点得到图二所示的有根树，以Ｂ为根节点得到图三所示的有根树，但从        

 无根树的角度看，图一、二、三是结构相同的无根树，同时无根树的结构与节点的        

 名称无关。                                                                      

    有根树可以用字符串的形式表示，其递归表示方法是：                             

        根节点（子树１    子树２    子树３...）                                  

 图一，图二的有根树可表示为 A(B(CF(EGD))) 和 B(ACF(EGD))。由于子树的表示         

 顺序可以不同，所以一棵有根树可以有多种表示方法，如图三又可表示成                

 B(F(EGD)CA) 或 B(ACF(DE(G)) 等。表示无根树时，可以以它任一节点为根节点，        

 将其看作有根树，从而可以利用有根树的字符串表示形式来表示无根树。                

    任务一：由键盘读入一个字符串表示的无根树，无根树的各节点的名称用互不         

 相同的大写英文字母表示。由用户输入一个节点的名称，程序应能够输出一种以该