[全民编程]76道高难度C 练习题含NOI竞赛题欢迎挑战.doc

《[全民编程]76道高难度C 练习题含NOI竞赛题欢迎挑战.doc》由会员分享，可在线阅读，更多相关《[全民编程]76道高难度C 练习题含NOI竞赛题欢迎挑战.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全民编程76道高难度C+练习题含NOI竞赛题欢迎挑战.txt结婚就像是给自由穿件棉衣，活动起来不方便，但会很温暖。谈恋爱就像剥洋葱，总有一层让你泪流。C+入门必做题 1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不 D F G 同字母。编程求出这些数字并且打出这个数字的 + D F G 算术计算竖式。 X Y Z D E算法: g = 0 f = 5 X=A+1 2. 、五名学生有可能参加计算机竞赛，根据下列条件判断哪些 人参加了竞赛： （）参加时，也参加； （）和只有一个人参加； （）和或者都参加，或者都不参加； （）和中至少有一个人参加； （）如果参加，那么和

2、也都参加。 3. 打印一个 N*N 的方阵，为每边 打印出下面图形 字符的个数（）, 要求最 TTTTTTTTTTTTTTT 外一层为T, 第二层为J, 从第三层 TJJJJJJJJJJJJJT 起每层依次打印数字 1,2,3,. TJ11111111111JT （右图以为为例） TJ12222222221JT TJ12333333321JT TJ12344444321JT TJ12345554321JT TJ12345654321JT TJ12345554321JT TJ12344444321JT TJ12333333321JT TJ12222222221JT TJ11111111111JT

3、 TJJJJJJJJJJJJJT TTTTTTTTTTTTTTT/*思路:逐行显示.数字部分由行数决定该行的最大数字并由1递增到最大的数再递减到1分两部分打印:N/2行之前及其之后特别的当N为奇数时,第N/2行(首行为第0行)的最大数之后用cout-num;输出,即该行最大的数只有一个*/#include#define N 20void main()int k= 0,count=0,t=0,time; for(int i=0;iN;i+) for(int j=0;jN;j+)if(i=0 | i=N-1 | j=0 | j= N-1) coutT;else if(i=1 | i=N-2 | j

4、=1 | j= N-2) coutJ;else if( k=i-2 & iN/2) | (k=N/2) ) cout0) coutcount;time-;elseif(i=N/2 & N%2!=0) cout-count;else coutcount-; coutendl; k= 0; count=0; 4. 在行列的数阵中, 数（）在每行和每列中出现且仅 出现一次，这样的数阵叫阶拉丁方阵。例如下图就是一个五阶拉丁方阵。 编一程序，从键盘输入值后，打印出所有不同的阶拉丁方阵，并统计个数。 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 5.

5、输入一个十进数，将其转换成 N 进制数（0N=16)。 6. 矩阵中填数. 当给出 N*N 的矩阵，要求用程序填入下列形式的数： 倒填，例如N=5 蛇形填数 回转填数 2524232221 1 3 41011 116151413 2019181716 2 5 91219 217242312 1514131211 6 8131820 318252211 10 9 8 7 6 714172124 419202110 5 4 3 2 1 1516222325 5 6 7 8 9 7. 读入一行文本，包含若干个单词（以空格间隔，结尾）。将其中以 A 开头的 单词与以 N 结尾的单词，用头尾交换的办法予

6、以置换。 8. 输入两个正整数，将，化为二进制数，然后将这两个二进制数作二进 制加法运算，再将结果化为十进制数输出。 9. 四人玩火柴棍游戏，每一次都是三个人赢，一个人输。输的人要按赢者手中的火柴 数进行赔偿，即赢者手中有多少根火柴棍，输者就赔偿多少根。现知道玩过四次后， 每人恰好输过一次， 而且每人手中都正好有根火柴。问此四人做游戏前手中各有 多少根火柴? 编程解决此问题。x,y,z,kk=5 10 20 40 16z=9 18 36 8 16y=17 34 4 8 16x=33 2 4 8 16 10. 如图所示，编写程序计算 大大小小正方形共有多少？当最小 正方行边长为时，它们的总面积

7、共为多少？ 11. 巧排数字。将、这个数排成一排，使得相邻的两个数之 和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。 12. 下图是一个集装箱仓库，阴影部分表示有集装箱存放不能通过，无阴影处为临时通 道。当有人要从入口处到达出口处时，必须寻找可通过路线，请你找出可完成这个过程 的最方便（即用最短路线）到达出口处的路径。 入口 出口 13. 有N个硬币（N为偶数）正面朝上排成一排，每次将 N-1 个硬币翻过来放在原位 置， 不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把 翻币的最简过程及翻币次数打印出来（用代表正面，O 代表反面）。 14. 有黑白棋子各

8、有个（分别用和代替），按下图方式排列 个黑棋 个白棋 允许将相邻两个棋子互换位置，最后使队形成黑白交替排列，试编程实现该操作。 15. 已知个城市，用i,j表示从城市到城市是否有单向的直达汽车 （= 0)， 每件物品价值为 V1，.VN (Vi0)。用这N件物品的某个子集 填空背包，使得所取物品的总重量=TOTAL，并设法使得背包中物品的价值尽可 能高。 20. (皇后) 在国际象棋的棋盘上放置个皇后，使其不能互相攻击，即任意 两个皇后不能处在棋盘的同一行，同一列，同一斜线上，试问共有多少种摆法？ 21. 请设计一个程序，由计算机把.的八个自然数填入图中，使得横、 竖、对角任何两个相邻的小方格

9、中的两个数是不连续的。(下图右侧的 4 个图 为禁止的情形). 22. 在一个的小方格（如图所示）中放置个号，使得每行每列放且 仅放两个号。 求出所有的基本解。 23. (覆盖问题) 有边长为（为偶数）的正方形，请你用个长为, 宽为的长方形，将它全部覆盖。编程打印出所有覆盖方法。如： 24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班， 向东要走块，向北要走块，（见图）。请设计一个程序，由计算机寻找并 打印出所有的上班的路径。 单位 家 25. (量水) 用存水为，升的两个罐子，量出升水。 26. (八数码问题) 个编有数码的滑牌，能在的井字格中滑动。 井字格中有一格是空

10、格，用表示，因而空格周围的数码滑牌都可能滑到空格中去. 下图是数码滑牌在井字格中的两种状态： 2 8 3 1 2 3 1 6 4 8 0 4 7 0 5 7 6 5 初始状态 目标状态 以左图为初始状态，右图为目标状态，请找出从初始状态到目标状态的滑牌移步 序列，具体要求： （）输入初始状态和目标状态的数据； 、分别用两行输入上述两项数据： 例：Enter the initial state:2 8 3 1 6 4 7 0 5 Enter the final state:1 2 3 8 0 4 7 6 5 、对输入数据应有查错和示错功能； （）实现从初始状态到目标状态的转换（如不能实现，程序应

11、输出不能实现 的提示信息）； （）输出结果，每移动一步都必须在屏幕上显示: 、移动每一步时的序号，最后一步的序号即为移动总步数； 、每一步移动后以表格形式显示状态。 （）要求能使移动步数尽可能少； 27. 给出一个有个格子的表格，除个格子外，每个格子中可放入一个数字，这 些数字取自自然数 1 到 5，放入格子中的数字不得相同，剩余的个格子是空格 （用表示）。图是一个放数字与空格的特例。现要求编程实现从初始表格状态 变化到目标表格状态。初始状态和目标状态都是可变的（图，图所示的状态仅 是一个特例），由键盘输入格子中的数字（）。 移动规则： (1) 每一个数字只可以通过虚线移入相邻空格。如图中，允

12、许“”左移入空 格，而不能上移进入上面空格。 (2) 只允许水平移动或垂直移动，不允许斜移。 (3) 移动后，该数字原先所在的格子变成空格。 实现目标： (1) 输入初始表格状态和目标表格状态的数据。 分别在一行内输入上述两项数据； 对输入的数据应有查错和报错功能； (2) 实现从初始状态到目标状态的转换（如不能实现也应给出必要的说明）。 (3) 显示结果：每移动一步都应在屏幕上有如下信息： 显示每一步移动的序号。所以最后一步的序号就是移动的总步数。 显示每一步移动前后的表格状态。 (4) 以最少的移动步数达到目标。 图 图 初始状态 目标状态 28. 枚银币 C1,C2,.,Cn, 其中有一

13、块不合格,不合格的银币比正常的要重。现用 一天平找出不合格的一块，要求在最坏的情况下，用的天平次数最少。 29. 把一段文章按要求排版。文章的输入方式为：由键盘输入一段以回车符结束的文章 （最大长度 2000 个字符）。排版时以单词为基本单位。单词由不含空格的任意字符组 成，是长度小于个字符的串。空格符是分隔单词的唯一字符，在输入时连续的空格 符在处理时应先化简为单个空格符。在排版前应先输入，排版后每行的字符数为，排 版后将整理好的文章按行输出。输出时不能将一个完整的单词截断，并要求输出的总行 数最小。将每个不足个字符的行用空格补足，填充空格符的方式有以下三种。 ）将填充的空格符置于每行的末尾

14、，并要求每行的起始为单词。 ）将填充的空格符置于每行的开始，并要求每行的末尾为单词。 ）将填充的空格符平均分配在每行中，并保证行的起始和末尾均为单词。 30. 某机要部门安装了电子锁。个工作人员每人发一张磁卡，卡上有开锁的密码特征。 为了确保安全，规定至少要有个人同时使用各自的磁卡才能将锁打开。问电子锁上至 少要有多少种特征? 每个人的磁卡上至少要有多少特征? 如果特征的编号以小写英文字 母表示，将每个人的磁卡的特征编号打印出来，要求输出的电子锁的总特征数最少。 设 3=M=7, 1=N=4, 与由键盘输入，工作人员编号用 1#,2#,.表示. 31. 甲乙两人从枚棋子中轮流取子，甲先取，规定

15、每次所取的枚数不能多于上 一个人所取的枚数，也不可不取。 （）甲第一次取多少枚才能保证甲取得最后一枚，当然，他也不能第一次就把 所有棋子都取走。 （）讨论棋子总数（一定是偶数）从到的各种情况。讨论内容包括： 对各个，是否存在一个小于的枚数，甲第一次取枚后就能保证甲如果策略 正确,一定能取到最后一枚棋子。 32. ( 走棋 ) 一个的方阵如图。有一个小卒从上往下走。走至格子后就 不能走动，走至后，若下方为，则向左或向右走，下方为，则向下走。求所 有走法。 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 33. ( 野人与传教士 ) 设有三个传教士和三个野人来到河边，打算乘一只船从

16、右 岸渡到左岸去。该船最大负载能力为两人，在任何时候，如果野人人数超过传教士 人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过 河去呢？ 34. ( 取棋子 ) 设有颗棋子，由人和计算机轮流从中取走若干颗。每方每次最 多取颗，最少取颗 (值不能超过总数的一半，也不能小于)。试编写一程 序使计算机有较多的获胜机会。 屏幕输入提示: (1) 输入竞赛规则：A. 取最后一颗棋子的那一方为败. B. 取最后一颗棋子的那一方为胜. (2) 总共有多少颗棋子？ (3) 一次最多取几颗？ (4) 谁先取？ (5) 每个回合都应显示: A. 你取几颗？ B. 我取走.颗，还剩.颗. (

17、6) 竞赛过程中发生违例时，打印出: 竞赛无法进行下去！ (7) 竞赛结束后打印： I win!（我胜！）或 You win!（你胜！）。 35. ( Grundy博弈 ) 在两位选手面前放着一堆铜币。第一位选手把原堆分成不相 等的两堆。然后每个选手轮流地这样做，即当轮到某一方分时, 他把已被分开的任 一堆再分成不相等的两堆。博弈这样一直进行下去，直到每一堆都只剩下一个或两 个铜币为止，这时博弈结束。规定首先遇到这种情况的选手为输。 36. 猴子选大王： N 只猴子站成一行，每隔 M 只从头到尾报数，反复进行,报过数的退出，打 印每次退出的猴子的编号,直到剩下一只为止。 N 只猴子站成一行，每

18、 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。

19、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. (算术表达式求值) 输入一个由数字、+，-，*，/ 及括号组成的算术

20、表达式， 求其值。 43. 对于次数很高，但项目很少的多项式，可用链表来表示。 例如：X100076*X763*X37可表示为 1 1000 -76 78 3 3 -70 NIL 在此方式下，编程完成两个多项式的加法与乘法。 44. (一元多项式加法) 实现两个整系数一元多项式的加法。例如, 对于多项式 5*X64*X37*X41 与多项式 50*X24*X, 运算结果为： 5*X67*X44*X350*X24*X1。 程序要求：键盘输入多项式的各项系数及指数，每项系数及指数为一组数据（系 数及指数之一可为零），以0,0结束一个多项式的输入，结果按降幂排列，同类 项要合并（指数最大不超过）。

21、上例第一式的输入为： 5,6 4,3 -7,4 1,0 0,0 输出结果应为：5*x6-7*x4+4*x3+50*x2+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.

22、 若给出 N 个数的数列，求出此数列的最小代价。 46. 设有一个字符串，长度小于 100，且全部以英文字母组成。对字串中的每个字 母可用 0,1,2 三个数字进行编码，且数字可以重复使用。 程序要求：(1) 输入字符串，并能判断输入是否有错； (2) 输出对应的编码表及码长，要求字串的编码总长度为最短； (3) 根据上述编码表，给出一些编码，然后求出其原字符串。 例如：输入的字符为:ABCBAAADDEF 其对应的编码表为： A: 2 B: 10 C: 11 D: 12 E: 00 F: O1 对应的编码为：210111022212120001 总码长为：18 根据该编码，给出编码:0100

23、01121110222 则输出字串:FEFDCBAAAA. 47. 某些密码由 N 个英文字母组成(N26), 每个字母的平均使用率为:W1,W2,. ,Wn, 要求编程完成下列任务： 键入英文字母及个数； 键入个英文字母的使用频率； 用二进制数对该个英文字母进行编码（最短，无二义性）； 键入字母短文（单词用空格区分），输出相应编码； 键入二进制编码短文，输出译文。 48. 将个红球，个白球与个黄球排成一排，共有多少种排法？ 49. 有面值为 M.N 的邮票各一枚，共能拼出多少不同的面额。 50. 有一个四阶方阵，随机产生 1.16 这 16 个自然数（不重复），依次填入每 个方格中。要求用最少的对调次数，使每一行、每一列以及对角线上的四个数之和 均相等。打印每一次对调的过程。 51. 微型蓝球赛. 甲,乙两队进行蓝球比赛,结果甲队以S:T 获胜.(TS0,b0,a+b=1 (详见下图),数 组 C 的面积 A=S1+S2+.+SN-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