di3.txt

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

 30. 某机要部门安装了电子锁。Ｍ个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有Ｎ个人同时使用各自的磁卡才能将锁打开。问电子锁上至少要有多少种特征? 每个人的磁卡上至少要有多少特征? 如果特征的编号以小写英文字母表示，将每个人的磁卡的特征编号打印出来，要求输出的电子锁        

 的总特征数最少。                                                                

    设 3<=M<=7, 1<=N<=4, Ｍ与Ｎ由键盘输入，工作人员编号用 1#,2#,...表示.         

                                                                                 

 31. 甲乙两人从２４枚棋子中轮流取子，甲先取，规定每次所取的枚数不能多于上        

 一个人所取的枚数，也不可不取。                                                  

  （１）甲第一次取多少枚才能保证甲取得最后一枚，当然，他也不能第一次就把         

 所有棋子都取走。                                                                

  （２）讨论棋子总数Ｎ（一定是偶数）从６到３０的各种情况。讨论内容包括：         

 对各个Ｎ，是否存在一个小于Ｎ的枚数Ｍ，甲第一次取Ｍ枚后就能保证甲如果策略        

 正确,一定能取到最后一枚棋子。                                                   

                                                                                 

 32. ( 走棋 ) 一个４＊４的方阵如图。有一个小卒从上往下走。走至格子１后就         

 不能走动，走至０后，若下方为１，则向左或向右走，下方为０，则向下走。求所        

 有走法。                                                                        

              ┌─┬─┬─┬─┐                                                 

              │1 │0 │0 │0 │                                                 

              ├─┼─┼─┼─┤                                             

              │0 │0 │1 │0 │                                                 

              ├─┼─┼─┼─┤                                                 

              │0 │1 │0 │0 │                                             

              ├─┼─┼─┼─┤                                                 

              │1 │0 │0 │0 │                                                 

              └─┴─┴─┴─┘                                                 

                                                                                 

 33. ( 野人与传教士 ) 设有三个传教士和三个野人来到河边，打算乘一只船从右         

 岸渡到左岸去。该船最大负载能力为两人，在任何时候，如果野人人数超过传教士        

 人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过        

 河去呢？                                                                        

                                                                                 

 34. ( 取棋子 ) 设有Ｎ颗棋子，由人和计算机轮流从中取走若干颗。每方每次最         

 多取Ｋ颗，最少取１颗 (Ｋ值不能超过总数的一半，也不能小于１)。试编写一程         

 序使计算机有较多的获胜机会。                                                    

    屏幕输入提示:

    (1) 输入竞赛规则：A. 取最后一颗棋子的那一方为败.                                  

                      B. 取最后一颗棋子的那一方为胜.

    (2) 总共有多少颗棋子？                            

    (3) 一次最多取几颗？                                              

    (4) 谁先取？                                               

    (5) 每个回合都应显示: A. 你取几颗？                                        

                          B. 我取走......颗，还剩......颗.                                             

    (6) 竞赛过程中发生违例时，打印出:  竞赛无法进行下去！                             

    (7) 竞赛结束后打印：                                                             

    I win!（我胜！）或  You win!（你胜！）。                                     

 

 35. ( Grundy博弈 ) 在两位选手面前放着一堆铜币。第一位选手把原堆分成不相        

 等的两堆。然后每个选手轮流地这样做，即当轮到某一方分时, 他把已被分开的任        

 一堆再分成不相等的两堆。博弈这样一直进行下去，直到每一堆都只剩下一个或两        

 个铜币为止，这时博弈结束。规定首先遇到这种情况的选手为输。                      

                                                                                 

 36. 猴子选大王：                                                                

   ① N 只猴子站成一行，每隔 M 只从头到尾报数，反复进行,报过数的退出，打         

 印每次退出的猴子的编号,直到剩下一只为止。                                       

   ② N 只猴子站成一行，每 M 只报数。先从头到尾，报到尾后，再返回从尾到头        

 报数，打印每次方向及过程，直到剩下二只时，以排到后面的(指报数方向)为大王。      

   ③ N 只猴子围成一圈，从第 P 个开始，每隔 M 只报数，打印每次过程，只剩下       

 一个时为大王。                                                                  

                                                                                 

 37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得                  

 K1*K2*....*Kn 为最大。                                                          

   例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大                     

                                                                                 

 38. 有一集合中有 N 个元素，每个元素均为自然数。给定一个 total （假设每个        

 元素值均小于total)，求满足条件的所有子集，子集中各元素之和应等于total。         

                                                                                 

 39. 一个集合满足如下条件：                                                      

   (1)１是集合的元素；                                                           

   (2) 若 P 是集合的元素，则 2*P+1，4*P+5 也是集合的元素。                       

 求：此集合中最小的 K 个元素。                                                   

 　③ 对ＡＢＣ作全排列而得的六个三位数之和为 2886。                              

                                                                                 

 40. 一个整型变量只能用来存贮较小的 N！的值，当 N 较大时，可将阶乘值中的         

 每一个数字放在一个一维数组的一个元素中。使用这方法，打印：                      

    ① Ｎ！的值；                                                                

    ② Ｎ！－Ｍ！（Ｍ＞Ｎ）；                                                    

    ③ Ｎ！＋Ｍ！                                                                

 

 41. (合并链表) 已知两个链表 AN={a1,a2,...an}, BN={b1,b2,...bm}, 将其合并        

 为一个链表 CN={a1,b1,a2,b2,...}                                                 

                                                                                 

 42. (算术表达式求值) 输入一个由数字、+，-，*，/ 及括号组成的算术表达式，        

 求其值。                                                                        

                                                                                 

 43. 对于次数很高，但项目很少的多项式，可用链表来表示。                          

  例如：X^1000－76*X^76＋3*X^3－7可表示为                                        

  ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐          

  │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│          

  └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘          

 在此方式下，编程完成两个多项式的加法与乘法。                                    

                                                                                 

 44. (一元多项式加法) 实现两个整系数一元多项式的加法。例如, 对于多项式           

 5*X^6＋4*X^3－7*X^4＋1 与多项式 50*X^2＋4*X, 运算结果为：                       

 5*X^6－7*X^4＋4*X^3＋50*X^2＋4*X＋1。                                           

   程序要求：键盘输入多项式的各项系数及指数，每项系数及指数为一组数据（系        

 数及指数之一可为零），以'0,0'结束一个多项式的输入，结果按降幂排列，同类         

 项要合并（指数最大不超过３０）。                                                

   上例第一式的输入为：    5,6                                                   

                           4,3                                                   

                          -7,4                                                   

                           1,0                                                   

                           0,0                                                   

  输出结果应为：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.                                  

                                                                                 

 45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把        

 它们相加， 并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=           

 ((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中        

 间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:        

 (4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.         

 若给出 N 个数的数列，求出此数列的最小代价。                                     

                                                                                 

 46. 设有一个字符串，长度小于 100，且全部以英文字母组成。对字串中的每个字        

 母可用 0,1,2 三个数字进行编码，且数字可以重复使用。                             

 程序要求：(1) 输入字符串，并能判断输入是否有错；                                

           (2) 输出对应的编码表及码长，要求字串的编码总长度为最短；              

           (3) 根据上述编码表，给出一些编码，然后求出其原字符串。