Programming is a skill that is essential in many fields related to computer science and artificial intelligence. This programming ability plays an important role in both learning and work. Therefore, the beginner has decided to create a new section called “Daily Challenge,” where they will strengthen and exercise their programming skills by solving a programming problem every day (at least they won’t forget programming).
Special note: The programming problems come from “Niuke.com” and “LeetCode” as well as from enthusiastic partners. Since the beginner sometimes wants to practice a certain type of programming method, the provided code may not always be the optimal solution, but the programming code provided in this article has passed testing.
Soda Bottle
Problem Description
There is a riddle: “A store has a rule: three empty soda bottles can be exchanged for one bottle of soda. Xiaozhang has ten empty soda bottles. How many bottles of soda can she exchange at most?” The answer is 5 bottles, as follows: first, use 9 empty bottles to exchange for 3 bottles of soda, drink the 3 full bottles, and after drinking, there are 4 empty bottles left. With 3 of those, exchange for one more bottle, drink that full bottle, and now there are 2 empty bottles remaining. Then, you can borrow one bottle of soda from the boss, drink that full bottle, and after drinking, use 3 empty bottles to exchange for one full bottle and return it to the boss. If Xiaozhang has n empty soda bottles, how many bottles of soda can she exchange at most?
Input Description:
The input file can contain up to 10 sets of test data, each occupying one line and containing only a positive integer n (1<=n<=100), indicating the number of empty soda bottles Xiaozhang has. n=0 indicates the end of input, and your program should not process this line.
Output Description:
For each set of test data, output one line indicating the maximum number of soda bottles that can be drunk. If no bottle can be drunk, output 0.
Example
Input
3
10
81
0
Output
1
5
40
Analysis
We can solve this problem using recursion, where 3 bottles can be exchanged for 1 bottle of water + 1 empty bottle, 2 bottles can be exchanged for 1 bottle of water + 0 empty bottles, and 1 bottle can be exchanged for 0 bottles of water.
f(1) = 0
f(2) = 1
f(3) = 1
f(4) = f(2)+1 // With 4 bottles, 3 can be exchanged for 1 bottle of water + 1 empty bottle, so it’s f(2)+1
f(5) = f(3)+1 // 3 bottles can exchange for 1 bottle of water + 1 empty bottle, so it’s f(3)+1
…
f(n) = f(n-2)+1
Code
#include <iostream>
using namespace std;
int f(int n)
{
if(n==1) return 0;
if(n==2) return 1;
return f(n-2)+1;
}
int main()
{
int n;
while(cin >> n){
if(n==0)
break;
cout << f(n) << endl;
}
return 0;
}
Click below“Read the original text”to see more↓↓↓