今天讲解的题目选自poj，1003 Hangover，悬挂纸牌。

一、问题描述

题目是这样的，在桌子上有一叠纸牌，将这些纸牌悬放在桌子边缘。纸牌在放置时，包括两个部分，一部分暴露在桌面或其他纸牌外面，一部分在里面。

假如放置n张纸牌，每张纸牌的长度为1，那么第一张有1/2暴露在外面，第二张放在第一张下方，1/3在外面，第三张在第二张下方，1/4在外面，等等，到第n张，在第n-1张的下方，有1/(n+1)在外面，第n张的下方就是桌面了。

例如n等于3时，三张纸牌分别暴露了1/2、1/3、1/4的长度在桌子外，总长度是1/2 + 1/3 + 1/4 约为1.083。那么，假如我们已知这叠纸牌暴露在外面的总长度L，求至少需要几张纸牌能达到这个长度呢?

例如， L = 1.1，在桌上放第1张时，长度为1/2，不足1.1。再放第2张，长度增加了1/3，总长度为1/2 + 1/3 = 5/6，依然不够。继续放第3张，总长度增加1/4，约等于1.08。再加一张，总长度增加1/5，约为1.28，这时暴露在外面的总长度就大于1.1了。因此至少需要4张纸牌，使得暴露在外面的总长度达到1.1。

那么请同学们编写程序，程序输入若干行浮点数，代表暴露在外面的长度L，最后一行为0.00，代表输入结束。

对于每个长度L，都输出一行结果，为纸牌数量，并在这个数量后添加空格card(s)。

例如输入5行浮点数，将会输出4行结果，分别代表，L = 1.00时，至少需要3张纸牌，L = 3.71时，需要61张等等，最后的0.00，代表输入的结束。

二、题目分析

我们来分析一下，最上面一张纸牌会提供1/2的长度，第二张提供1/3，第三张1/4，等等，到了第n张，会提供1/(n+1)的长度。

为了使程序的结构更好，开发函数compute_cards_number，函数传入长度L，在函数中计算最少需要的卡片数量n，并将n返回。

在函数中，设置两个变量，当前放置的纸牌数量n与已经叠加的长度sum。n为整型，初始化为1，代表至少放1张牌，sum为浮点型，初始化为0.5，代表放一张牌时，暴露在桌子外面的长度。

然后使用循环模拟叠放纸牌的过程，while循环的条件是sum < L，只要叠加的长度sum不够L，就继续叠放纸牌。

在循环中，通过代码n++，累加纸牌的数量，通过代码sum += 1.0 / (n+1)，累加暴露在外面的总长度。这里特别要注意，为了计算结果为浮点数，需要使用1.0除以n+1。

三、跑通样例

来看算法的运行过程，函数传入L = 1.00。首先叠放1张纸牌，sum = 0.5。

然后放第2张，n = 2，sum = 1/2 +1/3 = 0.833。

再放第3张，n = 3，sum = 1/2 + 1/3 + 1/4 = 1.083，超过了L。说明至少需要放3张牌，暴露在外面的总长度达到1。

四、输入与输出测试

最后来看poj1003的输入、输出和调用算法的实现。首先设置变量L，用于读取总长度。通过scanf %lf，读取标准输入的浮点数，存储至L。

进入while循环， 当L不是0时，读取、计算、输出的循环不断执行。

将L传入函数compute_cards_number，计算n的最小值，并通过printf将结果输出至标准输出。

循环的最后，继续读入长度L。

完成代码后，打开poj 1003，选择C语言，提交，题目通过测试。

至此poj1003悬挂纸牌就讲完了，我们下节课再见。

喜欢动画讲编程的小伙伴，一定要三连加关注哦！你们的支持是动画讲编程课程研发团队最大的动力！

长按二维码

添加小漫老师微信!
那添加老师微信，免费领取精品算法学习资料，和老师交个朋友