试题、程序及解题报告

2007年信息学分区联赛模拟赛试题解析

第一题吉祥数

为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的第一项内容是做游戏：猜数。老师给每位同学发一张卡片，每张卡片上都有一个编号(此编号为非负数，且小于255)，每个编号互不相同。老师制定了以下的游戏规则：第一轮，每位同学将自己卡片上编号的各位数字进行平方后再相加得到一组新数，编号在这组新数中出现的同学淘汰出局，第二轮，余下的同学再将编号的各位数字进行立方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，第三轮，余下的同学再将编号的各位数字进行4次方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，……，以此类推，经过n轮后，仍留下来的同学，将获得圣诞特别礼物，卡片上的数即为2007年吉祥数。(假定班级人数不超过200人)ghillie.in1

241232122014463672ghillie.out26122472123

这是一道基础题，数据量不大，采用模拟法，将每一轮初始的编号数存在数组Ａ中，这个数组中所有数的值在每一轮中不能更改，这组数产生的新数用Ｂ数组来存放，然后将Ｂ数组与Ａ数组进行比较，将Ａ数组中没有的Ｂ数组中的数存入Ｃ数组，下一轮开始时，先初始化Ａ数组，这时Ａ数组就取Ｃ数组，程序中最好能自定义一个函数fj(n,k:integer),作用是将编号数n进行分解后，再将数字k次方，最后求和，函数值取这个和。另外输入数据时，由于第二行不知数据的个数，因此要用函数eoln来控制。第二题最优分解方案

经过第一轮的游戏，不少同学将会获得圣诞特别礼物，但这时细心的数学课代表发现了一个问题：留下来的人太多而使礼物数量可能不够，为此，加试了一道数学题：将一个正整数n分解成若干个互不相等的正整数的和，使得这些数的乘积最大，当主持人报出一个n后，请你立即将这个最大值报出来，现请你帮你的好友编一个程序来解决这个问题。best.in7best.out122*2*3=122+2+3=73*4=123+4=7

初看此题，最容易想到的算法是搜索，但此题的n最大可以达到1000,搜索肯定会超时，这种情况下要另求它法，从最简单的例子中着手，往往能归纳出它的规律。n分解方案max523662487341283515923424

规律是：要想使乘积最大，应尽量使分得的个数多，另外当相同个数的正数的和相同时，数的差越小，数的积也就越大，因此将数从最小的数从２开始分解，下面每次取加１的数，直到不够取停止，这时再将余下的零头从最后的一个数开始，每个数加１，直至将零头处理完。如n=8时，分解的数为2，3，零头为3，将3加到3、2之上，变成3、4，还余1，就再加到4上，变成3、5。将数相乘时还要采用高精度乘法。第三题传话

兴趣小组的同学来自各个学校，为了增加友谊，晚会上又进行了一个传话游戏，如果a认识b，那么a收到某个消息，就会把这个消息传给b，以及所有a认识的人。如果a认识b，b不一定认识a。所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1<=i<=n。message.in46

12

23

41

31

13

23

message.out

T

T

T

F1243广度优先搜索算法第四题圣诞树

圣诞特别礼物挂在一棵圣诞树上，这棵树有n层，每层有一件礼物，每件礼物都有一个价值，有的礼物还有一些连结线，与下层的礼物相连，领取礼物的规则如下：任选一件礼物，它的下面如果有连结线，则可以继续取它连结的礼物，以此类推，直至取到没有连结线的礼物才结束，你如果是第一个去取，怎样取才能获得最大的价值呢？请你编一程序解决这一问题。tree.in3

1223

20

30tree.out

42

122030123数据范围1<=n<=100

动态规划状态:f(i)表示以第i个礼物为首向下寻找所得的最优值边界状态:f(n)=g[n]g[i]表示第i个礼物的价值ans=max{f(i)1<=i<=n}状态转移方程f(i)=g[i]+maxf(i+1)(i+1,i)=10(i+1,i)=0f(i+2)(i+2,i)=10(i+2,i)=0f(n)(n,i)=10(n,i)=0…………ans=max{f(i)1<=i<=n}动态规划状态:f(i)表示以第i个礼物为尾(最后一个礼物)由上寻找所得的最优值.边界状态:f(1)=g[1]g[i]表示第i个礼物的价值ans=max{f(i)1<=i<=n}状态转移方程f(i)=g[i]+maxf(i-1)(i+1,i)=10(i+1,i)=0f(i-2)(i+2,i)=10(i+2,i)=0f(1)(n,i)=10(n,i)=0…………ans=max{f(i)1<=i<=n}

本题有些同学可能会用从第一层开始往下搜索的方法来解，细细一看，层数最大达到100，肯定会超时。本题类似于求最长不下降序列，采用动态