转载请注明出处<http://blog.csdn.net/qianqin_2014/article/details/51277094>
试题：
有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶.
方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？
输入描述：
输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n（1<=n<=100），表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。
输出描述：
对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。
输入例子：
- 3
- 10
- 81
- 0
- 1
- 5
- 40
方法一：循环方法
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void bottle(int arr)
{
int count = 0; //所得汽水的数量
while ((arr + 1) > 3)
{
int tempZ = arr / 3; //用一个中间值来代替瓶子的数量，防止对齐数量发生篡改,保存空瓶直接兑换汽水数量
int tempY = arr % 3; //兑换汽水数量后所剩下的空瓶
arr = tempY + tempZ; //第一次兑换及喝剩下后剩下的空瓶瓶子数量
count += tempZ; //累加所换得的汽水数量
if (arr + 1 == 3) //知识后退出循环
{
count++;
break;
}
}
printf("%d\n", count);
}
int main()
{
int num = 0; //num代表输入的瓶子的数量
while (scanf("%d", &num))
{
if (num == 0)
continue;
else
bottle(num);
}
<span style="white-space:pre"> </span>return 0;
}
方法二：递归算法
永远要记住：循环算法都能用递归实现，二递归算法却不一定能够被循环实现。
在方法一的基础上，继续思考怎么能用递归实现该算法呢？思考一下...
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int algorithm(int n)
{
if (1 == n) //手里只有一个空瓶，肯定不能换掉汽水啦
return 0;
else if (2 == n) //这时候就可以和老板商议一下啦
return 1;
else
return n / 3 + algorithm(n / 3 + n % 3); //递归算法
}
int main()
{
int num = 0;
while (scanf("%d", &num))
{
if (0 == num)
continue;
else
printf("%d\n", algorithm(num));
}
return 0;
}
方法三：用数学思维来思考
这道题的实质是一道数学找规律的问题，然而规律却不容易被发现，怎么办呢，先打印一百个数据试一下吧...
#define _CRT_SECURE_NO_WARNINGS输出结果：
#include<stdio.h>
#define SIZE 100
int algorithm(int n)
{
if (1 == n)
return 0;
else if (2 == n)
return 1;
else
return n / 3 + algorithm(n / 3 + n % 3);
}
int main()
{
int arr[SIZE] = { 0 };
for (int i = 0; i < SIZE; i++)
{
arr[i] = i + 1;
printf("%-3d\t%-3d\n", arr[i], algorithm(arr[i]));
}
<span style="white-space:pre"> </span>return 0
}
1 0
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 4
10 5
11 5
12 6
13 6
14 7
15 7
16 8
17 8
18 9
19 9
20 10
21 10
22 11
23 11
24 12
25 12
26 13
27 13
28 14
29 14
30 15
31 15
32 16
33 16
34 17
35 17
36 18
37 18
38 19
39 19
40 20
41 20
42 21
43 21
44 22
45 22
46 23
47 23
48 24
49 24
50 25
51 25
52 26
53 26
54 27
55 27
56 28
57 28
58 29
59 29
60 30
61 30
62 31
63 31
64 32
65 32
66 33
67 33
68 34
69 34
70 35
71 35
72 36
73 36
74 37
75 37
76 38
77 38
78 39
79 39
80 40
81 40
82 41
83 41
84 42
85 42
86 43
87 43
88 44
89 44
90 45
91 45
92 46
93 46
94 47
95 47
96 48
97 48
98 49
99 49
100 50
看出规律了没，用整数除以2所得的整数就是结果了。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
int num = 0;
while (scanf("%d", &num))
if (num == 0)
continue;
else
printf("%d\n", num / 2);
return 0;
}
本题来源：牛客网
提交的程序：C代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int algorithm(int n)
{
if (1 == n) //手里只有一个空瓶，肯定不能换掉汽水啦
return 0;
else if (2 == n) //这时候就可以和老板商议一下啦
return 1;
else
return n / 3 + algorithm(n / 3 + n % 3); //递归算法
}
int main()
{
int num = 0;
while (~scanf("%d", &num))
{
if (0 == num)
continue;
else
printf("%d\n", algorithm(num));
}
return 0;
}
C++代码：
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
int algorithm(int n)
{
if (1 == n) //手里只有一个空瓶，肯定不能换掉汽水啦
return 0;
else if (2 == n) //这时候就可以和老板商议一下啦
return 1;
else
return n / 3 + algorithm(n / 3 + n % 3); //递归算法
}
int main()
{
int num = 0;
while (cin>>num)
{
if (0 == num)
continue;
else
cout << algorithm(num) << endl;
}
return 0;
}