回 帖 发 新 帖 刷新版面

主题:福建省信息学培训班试卷

问题描述:设2n张牌分别标记为1,2,…,n,n+l,…,2n,初始时这2n张牌按其标号从小到大排
列。经一次洗牌后,原来的排列顺序变成n+l,l,n+2,2,··,,2n,n。即前n张牌被放到偶数位置2,4,·,·,2n,而后n张牌被放到奇数位置1,3,…,2n-l。可以证明对于任何一个自然数n,经过若干次洗牌后可恢复初始状态。
编程任务:对于给定的n的值(n<=24000),编程计算最少经过多少次洗牌可恢复到初始状态。
数据输入:由键盘输入n的值。
结果输出:程序运行结束时,将计算出的最少洗牌次数在屏幕上输出。
输入示例
n=10
输出示例
6

问题描述,人民币的币值系统如下:
百元面值为100元;
十元面值为10元,20元,50元;
元面值为I元,2元,5元;
角面值为l角,2角,5角;
分面值为1分,2分,5分。
某人有人民币5·27元,假如这笔钱是由一张5元的纸币,一张2角的纸币和一枚5分的硬币及一枚2分的硬币组成,则不可能从中拿出0·17元。然而,不论这笔钱是由什么面值的货币凑成,0·02元是肯定拿得出的,因为如果没有一枚2分或2枚1分的硬币,就凑不齐5·27元这个数。从这笔钱中肯定拿得出的钱数除0·02元外,明显地还有5元,0,2元,0,07元,5·2元,0·27元等等。我们称这些肯定能拿出来的钱数是5·27元这笔钱肯定包含的钱数。
编程任务:对于给定的n(O<=n<=999),编程计算这n分钱中有多少笔肯定包含的钱数,并按
从小到大的顺序列出所有肯定包含的钱数。"
数据输入,由键盘输入n的值。
结果输出:程序运行结束时,将计算结果写入文本文件out.txt。文件的第一行是计算出的肯
定包含的钱数的笔数。从文件的第二行起是按从小到大的顺序列出所有肯定包含的钱数,每
行10个数。
输入示例
3
输出文件示例out·txt
3
123


间题描述:下图(略)是由14个"+"号和14个"-"号组成的符号三角形。2个同号下面都是"+",2个异号下面都是"-"号。
编程任务,设符号三角形的第一行有n个符号,对于给定的n(o<=n<=30),编程计算有多少
个不同的符号三角形,使得"+"和"-"的个数相同。
数据输入:由键盘输入n的数值。
结果输出:程序运行结束时,将所求得的符号三角形数在屏幕上输出。
输入示例
3
输出示例
4





































































































































































































































































回复列表 (共3个回复)

沙发

符号三角的题有空再说
第二题就是对给定金额进行从高额纸币开始的划分
将每一步的结果分别存入数组a(1..5,1..3)中
其中a(1,1)表示百元张数
a(2,1)表示50元张数,以此类推
划分完成后进行8重循环进行穷举可能的钱数

板凳

第一问题感觉上只要跟着洗牌的过程就可以了
只要模拟n张牌就够了,另外n张的变化过程是类似的

3 楼

突然想起在密码学导引里看过的
第一题就是完美快速洗牌嘛!!
完美快速洗牌的命题是对于2n张牌的完美快速洗牌是如下函数:f(x)=(2x)%(2n+1)
而这个命题有推论:使e为2模2n+1的阶,即e是满足2^e=1 mod (2n+1)的最小正整数
那么对一副有2n张的牌经过快速洗牌后,所有的牌都第一次返回他们的初始位置上。
也就是说原来的题转化成求e
这样计算量都在高精度求e上了

我来回复

您尚未登录,请登录后再回复。点此登录或注册