C++教学PPT：基础算法之递推算法

第一题：世纪末的星期

题目描述

曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。还有人称今后的某个世纪末的12月31日，如果是星期一则会…

有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!!

于是，“谣言制造商”又修改为星期日…1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？

请回答该年份（只写这个4位整数，不要写12月31等多余信息）

第二题：振兴中华

题目描述

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。地上画着一些格子，每个格子里写一个字。

从我做起振

我做起振兴

做起振兴中

起振兴中华

比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

要求跳过的路线刚好构成“从我做起振兴中华”这句话。

请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

答案是一个整数，请通过浏览器直接提交该数字。

注意：不要提交解答过程，或其它辅助说明类的内容。

第三题：梅森素数

题目描述

如果一个数字的所有真因子之和等于自身，则称它为“完全数”或“完美数”例如：

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

早在公元前300多年，欧几里得就给出了判定完全数的定理：

若 2^n - 1 是素数，则 2^(n-1) * (2^n - 1) 是完全数。其中 ^ 表示“乘方”运算，乘方的优先级比四则运算高，例如：2^3 = 8， 2 * 2^3 = 16, 2^3-1 = 7但人们很快发现，当n很大时，判定一个大数是否为素数到今天也依然是个难题。因为法国数学家梅森的猜想，我们习惯上把形如：2^n - 1 的素数称为：梅森素数。截止2013年2月，一共只找到了48个梅森素数。新近找到的梅森素数太大，以至于难于用一般的编程思路窥其全貌，所以我们把任务的难度降低一点：1963年，美国伊利诺伊大学为了纪念他们找到的第23个梅森素数 n=11213，在每个寄出的信封上都印上了“2^11213-1 是素数”的字样。2^11213 - 1 这个数字已经很大(有3000多位)，请你编程求出这个素数的十进制表示的最后100位。

第四题：颠倒的价牌

题目描述

小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。其标价都是4位数字（即千元不等）。小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了（参见p1.jpg）。这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，比如：1958 倒着挂就是：8561，差了几千元啊!! 当然，多数情况不能倒读，比如，1110 就不能倒过来，因为0不能作为开始数字。有一天，悲剧终于发生了。某个店员不小心把店里的某两个价格牌给挂倒了。并且这两个价格牌的电视机都卖出去了!庆幸的是价格出入不大，其中一个价牌赔了2百多，另一个价牌却赚了8百多，综合起来，反而多赚了558元。

请根据这些信息计算：赔钱的那个价牌正确的价格应该是多少？