0043.汽水瓶换饮料.md

汽水瓶换饮料

题目链接

C++

/**
 * 思路分析：
 * 
 * 有n个空瓶，尝试换取汽水,
 * 如果n < 2,只能换取0瓶汽水,
 * 如果n == 2,能借走一个汽水，凑齐三个空瓶，归还一个汽水,最终能换取1瓶汽水,
 * 如果n大于等于3，就可以换取 (n / 3)(向下取整)个汽水,
 * 剩下的n % 3 个空瓶 + 上述换取的汽水在喝完后的 n / 3个空瓶, 总共有n % 3 + n / 3 个空瓶
 * 空瓶又可以换取汽水,流程与上述一致，因此这是个递归过程
 * 
 * 列出递推方程:f(n) = n / 3 + f(n % 3 + n / 3)  当n >= 3
 *              f(n) == 1,                       当n == 2
 *              f(n) == 0,                       当n < 2
 * 
 * 不难写出递归代码，由于是尾递归，不需要转化成迭代形式来优化
 * “聪明”的编译器会帮我们优化成迭代形式
*/

#include <iostream>
#include <vector>

using namespace std;

int fun(int n){
    if(n < 2){
        return 0;
    }
    if(n == 2){
        return 1;
    }
    return n / 3 + fun(n % 3 + n / 3);
}

int main(){
    int n;
    vector<int> ans;
    
    while(cin >> n && n != 0){
        ans.emplace_back(fun(n));
    }
    
    for(int i = 0;i < ans.size();++i){
        cout << ans[i];
        //控制语句，使输出的最后一行不换行，其余换行
        if(i + 1 != ans.size()){ 
            cout << endl;
        }
    }
    
    return 0;
}

Java

/**
 * 思路：模拟
 * 通过反复兑换的方式进行计算。
 * 
 * 具体做法：
 * 使用一个循环，当空瓶数量大于三时进入循环
 * 在循环内部，计算空瓶可以兑换多少汽水，将这些汽水数量累计到汽水总数上
 * 更新剩余空瓶的数量，包括未能兑换的部分和喝完饮料后剩下的空瓶
 * 当循环结束以后，如果剩余的空瓶数量为 2，这个时候就可以向老板借一个空瓶，
 *     可以再换一瓶汽水，汽水总数加 1，最后将这瓶汽水的瓶子还给老板
 * 返回汽水总数
*/
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            int emptyBottles = scanner.nextInt();
            if (emptyBottles == 0) {
                break;
            }
            System.out.println(maxSodaBottles(emptyBottles));
        }
    }
    public static int maxSodaBottles (int n) {
        int totalSodas = 0;
        while (n >= 3) {
            int newSodas = n / 3;  // 手里的空瓶能够换取多少瓶饮料
            totalSodas += newSodas;  // 喝掉用兑换的所有饮料
            n = n % 3 + newSodas;  // 新的空瓶总数 = 未能兑换的空瓶 + 喝完饮料后剩下的空瓶
        }
        if (n == 2) {  // 还剩两个空瓶的时候找老板借一个空瓶
            totalSodas += 1;
        }
        return totalSodas;
    }
}

Python

# 第二题 汽水瓶兑换
# 这道题算是简单题，做除法就可以
def get_cola(n):
    res = 0
    while n>=3:
        res += n//3
        n = n//3 + n%3
    if n == 2:
        res += 1
    return res

while 1:
    try:
        n = int(input())
        if n == 0:
            break
        print(get_cola(n=n))
    except:
        break

Go

JS

C

#include <stdio.h>

int maxSodaBottles(int n) {
    int totalSodas = 0;
    
    while (n >= 3) {
        int newSodas = n / 3;  // 手里的空瓶能够换取多少瓶饮料
        totalSodas += newSodas;  // 喝掉用兑换的所有饮料
        n = n % 3 + newSodas;  // 新的空瓶总数 = 未能兑换的空瓶 + 喝完饮料后剩下的空瓶
    }
    
    if (n == 2) {  // 还剩两个空瓶的时候找老板借一个空瓶
        totalSodas += 1;
    }
    
    return totalSodas;
}

int main() {
    int emptyBottles;
    
    while (scanf("%d", &emptyBottles) == 1) {
        if (emptyBottles == 0) {
            break;
        }
        
        printf("%d\n", maxSodaBottles(emptyBottles));
    }
    
    return 0;
}