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

题目

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

输入格式:

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

输出格式:

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

输入样例:

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

5
10
18
1
2
3

输出样例:

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

46
1534
393214
1
2
3

分析 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意不要再在除了 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;
}
1
2
3
4
5
6
7
8
9
10
11

分析 2

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

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

即
$$\frac{a_n+2}{a_{n-1}+2}=\frac{1}{2}$$
可得 $a_n$ 的通项公式为
$$a_n=(a_1+2)(\frac{1}{2}{)}^{n-1}-2$$
设已知天数为 $k$，同时考虑到 $a_k$ 恒为 1，将上式变换得
$$a_1=3\ast 2^{k-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;
}
1
2
3
4
5
6
7
8
9
10
11
12

速度比较

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

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

输出

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

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