zoj 2830 Champion of the Swordsmanship

Champion of the Swordsmanship

Time Limit: 2 Seconds Memory Limit: 65536 KB

In Zhejiang University, there is a famous BBS named Freecity. Usually we call it 88.

Recently some students at the Humour board on 88 create a new game - Swordsmanship. Different from the common sword fights, this game can be held with three players playing together in a match. Only one player advances from the match while the other two are eliminated. Sometimes they also hold a two-player match if needed, but they always try to hold the tournament with as less matches as possible.

Input

The input contains several test cases. Each case is specified by one positive integer n (0 < n < 1000000000), indicating the number of players. Input is terminated by n=0.

Output

For each test case, output a single line with the least number of matches needed to decide the champion.

Sample Input

3
4
0

Sample Output

1
2

思路：抽象化。假如有n个人，最少需要比赛f(n)次，为了最少，肯定3个3个一组比赛，这需要n/3次，接下来除去淘汰的，还剩下n/3 + n % 3个人，这时需要比赛f(n/3 + n%3)次，那么f(n) = n / 3 + f(n /3 + n%3).如n == 1,则需要进行0次，n == 2需要进行1次。

显然用递归就解决啦。

 1 #include <iostream>
 2 using namespace std;
 3 int func(int n){
 4     if(n == 1)
 5         return 0;
 6     if(n == 2)
 7         return 1;
 8     return n / 3 + func(n / 3 + n % 3);
 9 }
10 
11 int main(){
12     int n;
13     while(cin >> n){
14         if(n == 0)
15             break;
16         cout << func(n) << endl;
17     }
18     return 0;
19 }