某商店规定:三个空汽水瓶可以换一瓶汽水,允许向老板借空汽水瓶(但是必须要归还)。
小张手上有n个空汽水瓶,她想知道自己最多可以喝到多少瓶汽水。
数据范围:输入的正整数满足
注意:本题存在多组输入。输入的 0 表示输入结束,并不用输出结果。
输入文件最多包含 10 组测试数据,每个数据占一行,仅包含一个正整数 n( 1<=n<=100 ),表示小张手上的空汽水瓶数。n=0 表示输入结束,你的程序不应当处理这一行。
对于每组测试数据,输出一行,表示最多可以喝的汽水瓶数。如果一瓶也喝不到,输出0。
3 10 81 0
1 5 40
样例 1 解释:用三个空瓶换一瓶汽水,剩一个空瓶无法继续交换 样例 2 解释:用九个空瓶换三瓶汽水,剩四个空瓶再用三个空瓶换一瓶汽水,剩两个空瓶,向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); int i=0; while (input.hasNext()) { int nextInt = input.nextInt(); if (i > 10 || nextInt == 0) { break; } i++; System.out.println(nextInt / 2); } } }
#include<iostream> #include<vector> using namespace std; int main(){ //动态规划 //初始条件:memo[0]=0,memo[1]=0,memo[2]=1 //迭代公式: //a = input/3 //b = input%3 //memo[input] = a+memo[a+b] int input; int n = 10; vector<int>memo;//备忘录 vector<int>res;//存储输入的数据对应的输出 memo.push_back(0); memo.push_back(0); memo.push_back(1); while ((cin >> input) && n--){ if (input == 0) break; if (input >= memo.size()) { for (int i = memo.size(); i <= input; i++){ int a = i / 3; int b = i % 3; memo.push_back(a + memo[a + b]); } } res.push_back(memo[input]); } for (int i = 0; i < res.size(); i++){ cout << res[i] << endl; } system("pause"); return 0; }提交观点
#include <iostream>using namespace std;intmain(){intn;while(cin>>n){cout<<n/2<<endl;}}
/*
递归问题
3个瓶子换1瓶水+1个空瓶子,两个瓶子换1瓶水+0个空瓶子,1个瓶子换0瓶水。
f(1) = 0
f(2) = 1
f(3) = 1
f(4) = f(2)+1 //4个瓶子,其中3个可以换1瓶水+1个空瓶,所以是f(2)+1
f(5) = f(3)+1 //3个瓶子换1瓶水+1个空瓶,所以是f(3)+1
...
f(n) = f(n-2)+1 */
#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;
}
// f(n)=n/3 + f(n%3+n/3),貌似递归次数更少。 // n/3是能直接换到的汽水数,n%3+n/3是新换到的汽水瓶子+上次换剩下的 import java.util.*; public class Main { public static int f(int n) { if (n == 1) return 0; if (n == 2) return 1; return n / 3 + f(n % 3 + n / 3); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int num = sc.nextInt(); if (num != 0) { System.out.println(f(num)); } } sc.close(); } }