C语言程序设计大赛题目.doc

程序设计大赛训练题 （1）请写一个程式求出2个数的GCD(最大公因数) ? Input and Output 输入包含好几笔资料，每笔资料一行，包含2个整数a,b。(0a, 0 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.???? ??? 输入 n2.???????? 印出 n3.??? ???? 如果 n = 1 结束4.???????? 如果 n 是奇数 那么 n=3*n+15.???????? 否则 n=n/26.???????? 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 Input1 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: