之前面试被问到的一个题目,想起来了就记录下

题目大概是这样:

商店规定 3 个空瓶可以换一瓶饮料,问买 10 瓶饮料可以喝到多少瓶?

提供两种解法

1. 循环

<?php

// 循环实现
function drink($full, $empty = 0) {
    // 3 个空瓶换一瓶饮料
    $exchange = 3;
    $drink = 0;
    while ($full > 0) {
        // 喝
        $drink += $full;    // 喝过的总数增加
        $empty = $empty + $full;    // 空瓶数增加

        // 换
        $full = intval($empty / $exchange);
        $empty = $empty % $exchange;
    }


    // 考虑特殊情况,剩余空瓶数 + 1 如果可以兑换一瓶的话,就还可以跟老板预支一瓶,喝完再把空瓶给他
    if ($empty + 1 == $exchange) {
        $drink++;
    }

    return $drink;
}

var_dump(drink(10));

2. 递归

<?php

// 递归实现
function drink_recursive($full, $empty = 0, $drink = 0) {
    // 3 个空瓶换一瓶饮料
    $exchange = 3;

    // 终止条件 - 没有满瓶 && 空瓶不够兑换
    if ($full < 1 && $empty < $exchange) {
        // 考虑特殊情况,剩余空瓶数 + 1 如果可以兑换一瓶的话,就还可以跟老板预支一瓶,喝完再把空瓶给他
        if ($empty + 1 == $exchange) {
            $drink++;
        }
        return $drink;
    }

    // 空瓶兑换
    if ($empty > 0) {
        $full += intval($empty / $exchange);
        $empty = $empty % $exchange;
    }

    // 喝
    if ($full > 0) {
        $drink += $full;
        $empty += $full;
        $full = 0;
    }

    return drink_recursive($full, $empty, $drink);
}

var_dump(drink_recursive(10));

标签: 编程

添加新评论