ACM作业模板.docVIP

扬州大学试题纸 （2013－2014 学年 第 二 学期） ACM竞赛辅导解题报告 学 院： *******学院 班 级： 计科12 学 号： 111404*** 姓 名： * * * 指导老师： * * * HDU 1465 装错信封 Problem Description 大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。 不幸的是，这种小概率事件又发生了，而且就在我们身边：事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！ 现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？ Input 输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1n=20），n表示8006的网友的人数。 Output 对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。 Sample Input 2 3 Sample Output 1 2 问题分析 去掉问题的冗杂项目，就是一个装错信封的问题。在完全装错的情况下，到底有多少项？ 问题的根本实际上为递归，为什么为递归将进行以下分析。 首先，先将问题具体考虑。 设信封有n封，则对应网友就有n个。而可能性有m种。 且当且仅当n〉1时才有可能发生装错了的现象。因为一个人，你怎么也不会弄错，更不要谈没有人。（人按正确的信封编号，即它头上的就是正确的信，且这也是它的编号） 当n=2时，m=1。 （图1.1） 当n=3时，m=2. 由于此处相当于3号有两种选择，一旦3号选择完成，1，2号就已经固定下来，不能选择了。 （图2.1） 当n=4时，m=9. 此时可以看出此时4号有（4-1）种选择 之后的公式会为（4-1）*（*********） 接下来进行括号内的计算 （图3.1） 此时的3号有两种选择 第一种是选择1，2。 第二种是选择4。 （图3.2.1） 当其选择第一种的时候，3有2种选择 与当n=3的时候情况基本一致。如（图2.1） 及n=4-1时。 m=（4-1）*（f(4-1)+***） (图3.2.2) 而当选择第二种的时候，3有1种选择，即选择4的信，而接下来，1，2完全独立，与n=2的时候完全类似。(如图1.1) m=（4-1）*（f(4-1)+f(4-2)） (图3.2.3) 当n=5时，m= 此时可以看出此时5号有（5-1）种选择 之后的公式会为（5-1）*（*********） 接下来进行括号内的计算 (图4.1) 此时的4号有两种选择 第一种是选择1，2，3。 第二种是选择5。 （图4.2.1） 当其选择第一种的时候，4有3种选择 与当n=4的时候情况基本一致。如（图2.1） 及n=4-1时。 m=（5-1）*（f(5-1)+***） （图4.2.2） 而当选择第二种的时候，4有1种选择，即选 择4的信，而接下来，1，2，3完全独立，和 n=3的时候完全类似。(如图1.1) m=（5-1）*（f(5-1)+f(5-2)） 由此可以发现，其实无论多少个人，都可以将它化成之前的步骤。 由于，不同的人数，装错的都是固定的，而且选择很少，就可以按照老师说的字典的方式来进行存储，将n对应的m都计算出来，然后存储起来。 程序代码 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 #includestdio.h int main() { long i; long n; long m[21] = {0, 1, 2}; // 准备字典，将n对应的m存储起来。 for (i = 3; i 20; i ++) { m[i] = i * (m[i-1]