c++二级试题.doc

7.6.1开灯与关灯(Light, More Light)有一个叫做Mabu的人在大学的走廊里面反复开灯与关灯,每个灯泡都有它们自己的开关用来改变它们的状态。如果灯是关着的，那么可以通过按这个开关来打开它，再按一次则将它关上。最初的时候所有的灯都是关上的。Mabu做了一件很奇特的事情：如果走廊上有n个灯泡，他就在走廊里来回走n次。在他走第i次的时候，只按动可以被i整除的位置（位置编号1到n）上的开关。在他走回初始位置时，他不会按动任何开关。第i次走动被定义为走到走廊尽头（同时作上述奇特的事情），然后走回来。你的任务是确定最后一个灯泡的最终状态。它是开着，还是关着的？输入输入每一行将给出一个走廊里的电灯总数（n=(223)-1)。n=0表示输入结束，你的程序不应该处理这一行。输出如果灯泡开着，输出“yes”：如果灯泡关着，输出“no”。每一行数据在单独的一行输出。7.6.2.Carmichael 数(Carmichael Numbers)密码学中的一些算法用到了很大的素数,但是要检验这些大数是不是素数却并不容易.存在一些速度快、准确性高的随机素数测试，如费马测试。a是一个2到n-1 之间的随机数，其中n就是那个需要测试素数性的整数。如果n满足一下的等式，则n就可能是素数：(an)mod n=a ,如果一个素数可以多次通过费马测试,那么它是素数的可能性很高。不幸的是,这里有一个坏消息:存在一些特定的的合数n,当a取小于n的所有可能值时都能通过测试。这些数被称为Carmichael数。写一个程序来判断一个数是不是Carmichael数。输入输入包含若干行,每一行包含一个正整数n(2n65000)。 n=0为输入结束标志,你的程序不应当处理它。输出对于输入的每个数，按照样例输出一行，说明这个数是否为Carmichael数。7.6.3欧几里德提出：对于任何正整数A和B，一定存在一对整数X和Y使得AX+BY=D,其中D是A和B的最大公约数。给定A和B，你的任务是找到相应的X,Y和D，使得|x|+|y|最小。输入输入包含若干行，每一行有一对整数A和B，用空格隔开（A,B1000000001）输出对于输入的每一行，输出一行，包含X,Y,和D，用单个空格隔开。如果有很多组满足条件的X，Y，应保证X0)如果存在一个整数k使得K*a=b则称a可以整除b.输入输入包含若干行,每行有两个小于231的非负整数n和m.输出对于输入的每一行,按照样例格式输出一行,说明m是否可以整除n!。7.6.5四素数之和Waring素数猜想是说：每一个奇数要么是素数，要么可以写成三个素数之和。Goldbach猜想是说：每一个偶数都能写成两个素数之和。这两个问题200年来尚未解决。在本题中。我们的任务要简单一点：把一个给出的整数写成四个素数之和。输入输入每一行都有一个整数n(n=10000000).输入以文件结束符结尾输出对于输入的每一个数n,输出一行,包含和为n的四个素数.如果n不能写成4个素数之和,则在单独的一行输出”Impossible,”.如果有很多解法,输出任何一种即可.7.6.6数学家Albert Wilansky 在1982年翻阅电话薄时偶然发现他姐夫H.Smith的电话有以下的奇特性质:电话号码的各个数字之和等于该电话号码所有素因子的每个数字之和.懂了吗?Smith的电话号码493-7775.他的素因子分解式为;4937775=3.5.5.65837电话号码的各个数字之和为4+9+3+7+7+7+5=42,而所有素因子的各个数字之和为3+5+5+6+5+8+3+7=42.Wilansky将它们排除在Smith数的定义之外.其它的Smith书还包括6036和9985Wilansky没有找到过比刚才那个电话号码更大的Smith数,你能帮助他吗?输入输入包含若干组数据,其中第一行为测试数据组数.每一行数据位于单独的一行中,包含一个小于109的正整数.输出对于每一个输出值n,计算出大于n的最小Smilth数,并单独的一行输出它.假设这样的数总是存在的.7.6.7弹珠我收藏了一些弹珠(彩色的小玻璃球),并且想买一些盒子来装它们.这些盒子有两种型号:类型1:每个盒子c1美元,可以恰好装n1个弹珠.类型2:每个盒子c2美元,可以恰好装n2个弹珠.我想将每个盒子都装满,并且花费最少的钱来买盒子.请帮我找出最好的方法把这些弹珠装到盒子里.输入输入包含多组数组,每组数据的开头是一个整数n(1=n=2000000000).第二行为c1和n1,第三行c2和n2.这里的c1,c2,n1,n2都是小于2000000000的正整数.n为0标志着输入的结束.输出对于每组数据,输入最小花费的方案(两个非负整数m1和m2,其中mi表示第i种盒子的数量).如果不存在解决方案,则输出”failed”.你可以假设:如果有解,方案唯一.7.6.8重新打包杯子制造协会生产三种不同规格的杯子(规格1,规格2,规格3),并以不同的包装出售.每种包装用三个整数(s1,s2,s3),其中si(1=i=3)表示该包装种规格i的杯子的数量.不幸的是,没有一种包装s1=s2=s3.市场调查发现:这种s1=s2=s3的包装需求量很大,为了抓住这个机会,ACW决定在它庞大库存中拆开一些没有出售的包装,重新组合后得到这种大需求量的包装.例如,假设ACW公司有以下的库存(1,2,3),(1,11,5),(9,4,3)(2,3,2).我们可以将三个(1,2,3),一个(9,4,3),两个(2,3,2)的包装拆开,然后重新组合成16个(1,1,1)的包装.你也可以把它们重新组合成八个(2,2,2),四个(4,4,4)两个(8,8,8)一个(16,16,16)的包装.注意拆开后的所有杯子必须重新组合到新的包装中.ACW请你写一个程序来判断是否能够从库存包装中选取一些,然后重新打包后得到三种规格的杯子数目相等的包装.输入输入包含若干组数据.每一组数据的第一行为一个整数N(3=N=