【PTA 题目详解】 7-10 猴子吃桃

题目

猴子第一天摘下若干桃子，当即吃了一半，还觉不过瘾，又多吃了一个；第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天天早上都吃了前一天剩下的一半零一个。到第n(n<=20)天早上想再吃时，见只剩一个桃子了。求第一天共摘了多少桃子。

输入格式:

测试数据有多组，处理到文件尾。每组输入天数n。

输出格式:

每组输出第一天摘的桃子数(结果保证在int型范围)。

输入样例:

在这里给出一组输入。例如：

5
10
18

输出样例:

在这里给出相应的输出。例如：

46
1534
393214

分析 1

假设知道第一天多少桃子，手动分析一遍样例数据，看看是如何变化的。

要求出第一天的桃子数量，我们只需要逆推即可。
从最后一天开始，一直循环做桃数 = (桃数 + 1) * 2，但是只需要做 $n-1$ 天即可。

还需注意的是，“测试数据有多组，处理到文件尾”，意味着输入数据有多少组不知道。这怎么处理呢？
这就不得不提一下 scanf() 的返回值了。若输入成功，scanf() 返回成功读入的数据个数；若读入失败，则返回 EOF。EOF 是一个常量，值为 -1。

那到底怎么写呢？
我们只需要循环调用 scanf()，判断返回值是否为 EOF，若为则跳出循环即可。

参考代码 1

#include int howManyPeachesDoIHave(int n)
{int count = 1; //桃子个数for (int i = 1; i < n; i++){count++;count *= 2;}return count;
}int main(void)
{int n = 0;while (scanf("%d", &n) != EOF) //<-- 多组数据输入的关键{printf("%d\n", howManyPeachesDoIHave(n));}return 0;
}

注意不要再在除了 while 语句的里的其他地方调用 scanf("%d", &n)，否则会重复调用，造成上一个输入的 n 还没处理就被下一个 n 覆盖掉了。

int main(void)
{int n = 0;scanf("%d", &n); // ---> 错误用法 <---while (scanf("%d", &n) != EOF){scanf("%d", &n); // ---> 错误用法 <---printf("%d\n", howManyPeachesDoIHave(n));}return 0;
}

分析 2

桃数实际上就是一个数列，直接求出通项公式，变换一下，直接求出 a 1 a_1 a1​ 的求解公式，岂不是更方便？
下面给出过程
（PS：这是用构造法从递推公式求通项公式的步骤，高中数列知识，请自行复习。）

解：
设第 $n$ 天桃数为 a n a_n an​，则第一天桃数为 a 1 a_1 a1​
由题意，有
a n = 1 2 a n − 1 − 1 a_n=\frac{1}{2}a_{n-1}-1 an​=21​an−1​−1
易知
a n + 2 = 1 2 ( a n − 1 + 2 ) a_n + 2 = \frac{1}{2}(a_{n-1} + 2) an​+2=21​(an−1​+2)

即
a n + 2 a n − 1 + 2 = 1 2 \frac{a_n + 2}{a_{n-1} + 2} = \frac{1}{2} an−1​+2an​+2​=21​
可得 a n a_n an​ 的通项公式为
a n = ( a 1 + 2 ) ( 1 2 ) n − 1 − 2 a_n = (a_1 + 2)(\frac{1}{2})^{n-1} - 2 an​=(a1​+2)(21​)n−1−2
设已知天数为 $k$，同时考虑到 a k a_k ak​ 恒为 1，将上式变换得
a 1 = 3 ∗ 2 k − 1 − 2 a_1 = 3 * 2^{k - 1} - 2 a1​=3∗2k−1−2

参考代码 2

#include 
#include int main(void)
{int n = 0;while (scanf("%d", &n) != EOF){printf("%.lf\n", 3 * pow(2, n - 1) - 2);}return 0;
}

速度比较

写一段简单的代码比较一下两者的速度
两种方法都重复计算一万次，分别统计两者所用的时间

#include 
#include int method1(int n)
{int count = 1; //桃子个数for (int i = 1; i < n; i++){count++;count *= 2;}return count;
}int method2(int n)
{return 3 * pow(2, n - 1) - 2;
}int main(void)
{clock_t t;t = clock();for (int i = 1; i <= 10e4; i++){method1(i);}t = clock() - t;printf("method1(): %lf seconds\n", ((double)t) / CLOCKS_PER_SEC);t = clock();for (int i = 1; i <= 10e4; i++){method2(i);}t = clock() - t;printf("method2(): %lf seconds\n", ((double)t) / CLOCKS_PER_SEC);return 0;
}

输出

method1(): 2.575000 seconds
method2(): 0.029000 seconds
请按任意键继续. . .

可以看见用通项公式算比用循环累加快得多

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！