C语言程序设计大赛题目

程序设计大赛训练题 （1）请写一个程式求出2个数的GCD(最大公因数)

Input and Output

输入包含好几笔资料，每笔资料一行，包含2个整数a,b。(0

对每行输入，输出这2个数的GCD Sample Input 12 36 25 24 0 0

Sample Output GCD(12,36)=12 GCD(25,24)=1）

(2) 联集

读入2个正整数a,b，请输出介于a,b之间（包含a,b）2,3,5倍数的联集大小。

Input（输入可能包含了好几列测试资料，每一列有2个整数a,b。 a=0 b=0 代表输入结束。）

Output（对每一列输入，请输出联集的大小。请参考Sample Output ） Sample Input（1 10 ；10 20；0 0；） Sample Output（8；7）

（3）Q100: The 3n + 1 problem

考虑以下的演算法：

1. 输入 n 2. 印出 n

3. 如果 n = 1 结束

4. 如果 n 是奇数 那么 n=3*n+1 5. 否则 n=n/2 6. GOTO 2

例如输入 22, 得到的数列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 据推测此演算法对任何整数而言会终止 (当列印出 1 的时候)。虽然此演算法很简单，但以上的推测是否真实却无法知道。然而对所有的n ( 0 < n < 1,000,000 )来说，以上的推测已经被验证是正确的。

给一个输入 n ,透过以上的演算法我们可以得到一个数列（1作为结尾）。此数列的长度称为n的cycle-length。上面提到的例子, 22的 cycle length为 16.

问题来了：对任意2个整数i，j我们想要知道介于i，j（包含i，j）之间的数所产生的数列中最大的cycle length是多少。

Input:输入可能包含了好几列测试资料，每一列有一对整数资料 i，j 。 ( 0< i，j < 10000 )

Output：对每一对输入 i , j你应该要输出 i, j和介于i, j之间的数所产生的数列中最大的cycle length。

Sample Input：1 10；10 1；100 200；201 210；900 1000； Sample Output 1 10 20 10 1 20 100 200 125 201 210 89 900 1000 174

（4）Q101: The Blocks Problem

在早期人工智慧的领域中常常会用到机器人，在这个问题中有一支机器手臂接受指令来搬动积木，而你的任务就是输出最后积木的情形。一开始在一平坦的桌面上有n块积木（编号从0到n-1）0号积木放在0号位置上，1号积木放在1号位置上，依此类推，如下图。

机器手臂有以下

几种合法搬积木的方式（a和b是积木的编号）：

move a onto b

在将a搬到b上之前，先将a和b上的积木放回原来的位置（例如：1就放回1的最开始位罝）

move a over b

在将a搬到b所在的那堆积木之上之前，先将a上的积木放回原来的位罝（b所在的那堆积木不动） ? pile a onto b

将a本身和其上的积木一起放到b上，在搬之前b上方的积木放回原位 ? pile a over b

将a本身和其上的积木一起搬到到b所在的那堆积木之上 ? quit

动作结束

?

?

前四个动作中若a=b，或者a, b在同一堆积木中，那么这样的动作算是不合法的。所有不合法的动作应该被忽略，也就是对各积木均无改变。

Input输入含有多组测试资料，每组测试资料的第一列有一个正整数n（0 < n < 25），代表积木的数目（编号从0到n-1）。接下来为机器手臂的动作，每个动作一列。如果此动作为 quit ，代表此组测试资料输入结束。你可以假设所有的动作都符合上述的样式。请参考Sample Input。

Output每组测试资料输出桌面上各位置积木的情形（每个位置一列，也就是共有n列），格式请参考Sample Output。 Sample Input10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit 4

pile 0 over 1 pile 2 over 3 move 1 onto 3 quit

Sample Output 0: 0

1: 1 9 2 4 2: 3: 3 4:

5: 5 8 7 6 6: 7: 8: 9: 0: 0 1: 2: 2 3: 3 1

（5）Q102: Ecological Bin Packing

有3个桶子用来装回收的玻璃瓶，玻璃瓶的颜色有三种：棕色（Brown）、绿色（Green）、透明色（Clear）。在这个问题里我们会告诉你每个桶子里的玻璃瓶的颜色及数量，现在要搬移桶子里的玻璃瓶使得最后每个桶子里都只有单一颜色的玻璃瓶，以方便回收。你的任务就是要算出最小搬移的瓶子数。你可以假设每个桶子的容量无限大，并且总共搬移的瓶子数不会超过231。

Input每笔测试资料一行，每行有9个整数.前3个代表第1个桶子里Brown, Green, Clear颜色的瓶子数。接下来的3个数代表 第2个桶子里Brown, Green, Clear颜色的瓶子数。最后的3个数代表第3个桶子里Brown, Green, Clear颜色的瓶子数。

例如：10 15 20 30 12 8 15 8 31

表示有20个Clear色的玻璃瓶在第1个桶子里，12个Green色的玻璃瓶在第2个桶子里，15个Brown色的玻璃瓶在第3个桶子里。

Output对每一笔测试资料，输出3个桶子内最后存放之玻璃瓶颜色，以及最小搬移的瓶子数。请以大写的'G'、 'B'、 'C' 分别代表绿色（Green）、棕色（Brown）、透明色（Clear）。

例如：BCG 30

代表最后搬移的结果第1个桶子内的玻璃瓶颜色为Brown，第2个桶子内的玻璃瓶颜色为Clear，第3个桶子内的玻璃瓶颜色为Green.并且总共搬移了30个玻璃瓶。

如果最小搬移瓶子数有一组以上的组合，请输出字典顺序最小的那一组答案。 Sample input

1 2 3 4 5 6 7 8 9

5 10 5 20 10 5 10 20 10 Sample Output BCG 30 CBG 50

（6）Q103: Stacking Boxes

在数学或电脑科学里，有些概念在一维或二维时还蛮简单的，但到 N 维就会显得非常复杂。试想一个 n 维的“盒子”：在二维空间里，盒子 ( 2 , 3 ) 可代表一个长为 2 个单位，宽为 3 个单位的盒子；在三维空间里，盒子 ( 4 , 8 ,

9 ) 则是一个 4*8*9（长、宽、高）的盒子。至于在六维空间里，也许我们不清楚 ( 4 , 5 , 6 , 7 , 8 , 9 ) 长得怎样，不过我们还是可以分析这些盒子的特性。

在此问题里，我们要算出一组 n 维盒子里，它们的“最长套入串列”： b1, b2, ......,bk，其中每个盒子 bi 都可以“放入”盒子 bi+1 中（1 <= i < k） 考虑两个盒子 D =（ d1, d2, ......,dn ）， E =（ e1, e2, ......,en ）。如果盒子 D 的 n 个维，能够存在一种重排，使得重排后， D 每一维的量度都比 E 中相对应的维的量度还要小，则我们说盒子 D 能“放入”盒子 E 。（用比较不严谨的讲法，这就好像我们将盒子 D 翻来翻去，看看能不能摆到 E 里面去。不过因为我们考虑的是任一重排，所以实际上盒子不只可转来转去，甚至还可以扭曲。）（还是看看下面的例子说明好了）。

譬如说，盒子 D = ( 2 , 6 ) 能够被放入盒子 E = ( 7 , 3 ) 里，因为 D 可以重排变为 ( 6 , 2 ) ，这样子 D 的每个维的量度都比 E 里对应的维还要小。而盒子 D = ( 9 , 5 , 7 , 3 ) 就没办法放进盒子 E = ( 2 , 10 , 6 , 8 ) ，因为就算再怎摸重排 D 里的维，还是没办法符合“放入”的条件。不过 F = ( 9 , 5 , 7 , 1 ) 就可以放入 E 了，因为 F 可以重排成 ( 1 , 9 , 5 , 7 ) ，这样就符合了放入的条件。

我们今定义“放入”如下：对于任两个盒子 D =（ d1, d2, ......,dn）和 E =（ e1, e2, ......,en ），如果存在一种 1..n 的重排π，使得对于任何的 1 <= i <= n，皆有 dπ(i) < ei，则我们说盒子 D 能“放入”盒子 E 。

Input输入包含多组测试资料。每组测试资料的第一列有两个数字：第一个是盒子的数量 k ，然后是盒子的维数 n ； 接下来有 k 列，每列有n个整数表示一个盒子的 n 个维的量度，量度之间由一个以上的空白做区隔。第一列表示第一个盒子，第二列表示第二个盒子，依此类推； 此问题里，盒子的维数最小是 1 ，最大是 10 ， 并且每组测试资料中盒子的个数最多为 30 个。 Output对于每一组测试资料，你必须输出两列数字：第一列是“最长套入串列”的长度，第二列是按照内外顺序，印出“最长套入串列”里盒子的编号（其中编号是按照在输入档案的每组数列里所出现的顺序，例如第一个盒子就是 1 号 . . . 等等。）最里面的盒子（或是最小的）摆在第一个，再来是次小的，依此类推； 如果对于每一组的盒子，存在两个以上的“最长套入串列”，输出任何一个均可。 Sample Input 5 2 3 7 8 10 5 2 9 11 21 18

所谓一个路径的“重量”（weight）就是此路径经过的 n 个格子里，它们的整数总和。举个例子，下面有两个不同的5*6 方阵。（实际上你可以注意到它们的不同只在最后一列而已）

这两个方阵的“最小重量路径”（ minimal-weight path ）已经在上面分别标出来了。注意一下右边的方阵，其利用了第一列和最后一列是相邻的这个性质达到了最小的重量。

Input输入里包含多组测试资料，每组代表一个方阵。每组测试资料的第一列为2个正整数 m 与 n （1 <= m <=10，1 <= n <= 100），依序表示这方阵有几横列和几直行。而后就是 m*n 个整数，这些整数是按照“列顺序”（ row major order ）来排列，也就是输入里的前 n 个数表示方阵的第一横列，再下来的 n 个数表示第二横列，依此类推。在输入里，同一列的数彼此间将会被一个以上的空白隔开。值得注意的是，这里说的整数并不一定是正的。输入以及计算的过程所出现的数均不会超过长整数（long）的范围。 Sample Input中前2组测试资料所表达的方阵就是上方的2个图，请参考。

Output对于每个方阵，你必须输出两列东西。第一列是“最小重量路径”

（ minimal-weight path ），第二列则是其“重量”。对于第一列，你必须输出 n 个正整数，依序表示在每一行，此路径经过了第几列。如果存在两个以上的路径其“重量”皆为最小，则输出按照字典顺序（ lexicographically ）最小的那一个路径。请参考Sample Output。 Sample Input 5 6

3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5

8 4 1 3 2 6 3 7 2 8 6 4 5 6

3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 2 2

9 10 9 10 Sample Output 1 2 3 4 4 5 16

1 2 1 5 4 5 11 1 1 19

Q127: \

你的任务是模拟一种叫“Accordian”的纸牌游戏，他的游戏规则如下：一副扑克牌有52张牌，首先把纸牌一张一张由左到右排好（不能有重叠，所以共有52堆牌，每堆一张），当某一张牌与他左边那张牌或者左边的第三张牌有“Match”的时候，就把这张牌移到那张牌上面去。在这里两张牌“Match”指的是这两张牌的花色（suit）或者点数（rank）一样。当你做了一个移动之后，要察看是否还可以做其他的移动。在任何时间，只有最上面那张牌可以被移动。如果因为移动一张牌使得产生一个空格（也就是被移动的那堆牌只有一张牌），你必须把右边所有的牌堆往左移一格。如此不断的寻找可移动的牌，直到没有一张牌可以移动游戏就结束了。 在选择可以移动的牌的时候可能有些状况会发生。如果有两张牌都可以移动，你应该要移动最左边的那张牌。当一张牌可以被移动到左边一格，或左边三格的时候，你必须移动到左边三格。

Input输入包含多组测试资料。每组测试资料两列，每列有26张牌的资料。每张牌以2个字元代表。第一个字元代表牌的点数（A=Ace, 2~9, T=10, J=Jack, Q=Queen, K=King），第二个字元代表牌的花色（C=Clubs, D=Diamonds, H=Hearts, S=Spades）若遇到仅含#的一列代表输入结束。请参考Sample Input。 Output对每组测试资料输出游戏结束时剩下几堆牌，以及每堆牌有多少张牌。请注意如果只有1堆牌，pile后没有加s，请参考Sample Output。 Sample input

QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C 6S

8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C 5C

AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD

AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS #

Sample Output

6 piles remaining: 40 8 1 1 1 1 1 pile remaining: 52

Q128: Software CRC

你在一家有很多个人电脑的公司上班。你的老板，连一分都省博士，想要把这些个人电脑连线，但是他又不想要花钱买网路卡。由于你不小心告诉老板每台电脑出厂时就有一个非同步串列埠在上面，老板当然把脑筋动到这不用花钱的解决方案上。于是可怜的你被指派来完成这工作软体的需求，以使这些电脑之间可以连线。

你已经读了许多关于通讯的书并且知道在传送及接收讯息时，确保讯息的正确性是一个重点。典型的作法是在讯息的最后加上额外的错误检查码。这个资讯允许接收程式检查出传送的资讯是否有错误（在大多数的例子）。于是，你跑到图书馆借回了一本关于通讯厚厚的书，利用周末（当然没有加班费）研究错误检查的部分。

最后，你决定CRC（cyclic redundancy check）是最适合的错误检查方式。以下描述这个机制： CRC Generation 待传递的讯息被视为一列长长二元数。讯息的第一个位元组（byte）被当作这二元数最重要的位元组，第二个位元组被当作第二重要的位元组，依此类推。这个二元数被称为\。当传送时会在\之后加上2个位元组的CRC检查码，然后整个二元数称为\。 这个CRC的检查码被产生使得\可以整除某个16位元的值 \。所以当接收端收到一讯息，只要把他除以 \，如果余数为0即代表此讯息正确。 你也注意到，大部分建议采用的g值都是奇数，所以你决定用 34943 当作 g 的值。现在你迫切的任务就是对待传送的讯息，写一个程式算出这个CRC的值。

例如：若要传送的讯息为：AB（二进位的表示式为：01000001 01000010），你必须算出的CRC值应为60 1B（01100000 00011011的十六进位表示式），使得 01000001 01000010 01100000 00011011可以整除34943（10进位）。 Input

每组测试资料一列，含有一个待传送的讯息（不会超过1024个ASCII字元的长度），列结束字元（End of line）不被视为待传送讯息的一部份。若遇到只含 # 的一列，代表输入结束（此列无须输出）。请参考Sample Input。 Output

对每组测试资料输出一列，CRC的值（以十六进位表示）。请注意：CRC的值一定介于0到34942（十进位）之间。输出格式请参考Sample Output。 Sample Input this is a test A AB Nothing gonna change my love for you. # Sample Output 77 FD 00 00 0C 86 60 1B 57 98

本文来源：https://www.bwwdw.com/article/avrd.html