思路
由题意可知:
- n=0 的时候,有 0 瓶
- n=1 的时候,有 0 瓶
- n=2 的时候,有 1 瓶
- n=3 的时候,有 1 瓶
- n=4 的时候,有 2 瓶
- ......
由此,我们设 f(n) 为小明手上有 n 个空瓶的时候,可以得到的汽水瓶数。根据规则我们可以知道 f(n) = f(n/3+n%3) + n/3; 所以,自底向上即可计算出结果。
代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<int> nums(101);
nums[0] = 0;
nums[1] = 0;
nums[2] = 1;
while( true )
{
cin >> n;
if( 0 == n )
break;
if( n < 3 )
cout << nums[n] << endl;
else
{
for( int i = 3; i <= n; i++ )
{
int tmp = i / 3;
nums[i] = nums[tmp+i%3] + tmp;
}
cout << nums[n] << endl;
}
}
return 0;
}