最优面额找零算法求助：基于$2、$5、$10纸币的实现修正

问题规则与测试要求 #

核心规则 #

收银机仅提供$2、$5和$10面额纸币，算法需以最少纸币数量为任意金额找零。

测试要求 #

解决方案需覆盖示例场景及$10、$11、$21、$23、$31这些特定金额，预期最优结果如下：

$10: 1张$10纸币
$11: 1张$5纸币 + 3张$2纸币
$21: 1张$10纸币 + 1张$5纸币 + 3张$2纸币
$23: 1张$10纸币 + 1张$5纸币 + 4张$2纸币
$31: 2张$10纸币 + 1张$5纸币 + 3张$2纸币

现有代码缺陷 #

提供的PHP代码存在以下问题：

• 会生成非正数量的纸币记录
• 无法优雅处理不可找零的金额（如$1、$3）
• 针对$23、$31等金额返回错误结果

原代码如下：

function rendreMonnaie(int $montant)
{
    //Déclaration des variables
    $listeBillets = [10, 5, 2];  //Liste des coupure dispo
    $nbEntree = 0; //Combien de fois un chiffre entre dans le montant
    $message = [];
    $reste = 0;
    $result = 0;


    for ($ibillet = 0; $ibillet < sizeof($listeBillets); $ibillet++) {
        // Calcul du reste de la division du montant par le billet
        $reste = $montant % $listeBillets[$ibillet];
        if ($reste == 0) {
            // Si le reste est 0, le montant est un multiple du billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            break;
        } else if ($reste >= $listeBillets[2]) {
            // Si le reste est supérieur ou égal au plus petit billet
            // Calcul du nombre de billets nécessaires
            $nbEntree = intdiv($montant, $listeBillets[$ibillet]);
            // Ajout du nombre de billets et du type de billet au message
            array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            // Mise à jour du montant avec le reste
            $montant = $reste;
        } else {
            if ($listeBillets[$ibillet] == 2) { 
               $nbEntree = intdiv($result, $listeBillets[$ibillet]);
               array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            } else {
                $result = $montant - $listeBillets[$ibillet];
                $reste = $reste % $listeBillets[$ibillet];
                // Calcul du nombre de billets nécessaires
                $nbEntree = intdiv($result, $listeBillets[$ibillet]);
                array_push($message, "$nbEntree x $listeBillets[$ibillet]");
            }
        }
    }
    // Affichage du tableau message pour le débogag
    for ($i = 0; $i < sizeof($message); $i++) {
        // Suppression des éléments du message qui commencent par un nombre inférieur à 1
        if ($message[$i][0] < 1) {
            unset($message[$i]);
        }
    }
    // Conversion du tableau message en une chaîne de caractères
    $message = implode(" + ", $message);
    echo ($message);
}

修复后的代码与逻辑 #

要实现最少纸币数量，核心思路是优先使用大面额，同时处理奇数金额的特殊情况：只有$5是奇数，因此奇数金额必须包含至少1张$5，转换为偶数后再用大面额策略处理。

修复后的代码：

function rendreMonnaie(int $montant): string
{
    // 拦截无法找零的情况：金额小于2，或为1、3这类无法用现有面额组合的奇数
    if ($montant < 2 || ($montant % 2 != 0 && $montant < 5)) {
        return "无法找零";
    }

    $billets = [10 => 0, 5 => 0, 2 => 0];
    $remaining = $montant;

    // 处理奇数金额：必须用1张5元，将剩余金额转为偶数
    if ($remaining % 2 != 0) {
        $billets[5]++;
        $remaining -= 5;
    }

    // 优先使用10元纸币
    $billets[10] = intdiv($remaining, 10);
    $remaining %= 10;

    // 剩余金额用2元纸币填充
    $billets[2] = intdiv($remaining, 2);

    // 构建结果字符串
    $result = [];
    foreach ($billets as $denom => $count) {
        if ($count > 0) {
            $result[] = "$count 张\$$denom 纸币";
        }
    }

    return implode(" + ", $result);
}

// 测试用例验证
$testCases = [
    10 => "1 张$10 纸币",
    11 => "1 张$5 纸币 + 3 张$2 纸币",
    21 => "1 张$10 纸币 + 1 张$5 纸币 + 3 张$2 纸币",
    23 => "1 张$10 纸币 + 1 张$5 纸币 + 4 张$2 纸币",
    31 => "2 张$10 纸币 + 1 张$5 纸币 + 3 张$2 纸币",
    3 => "无法找零",
    7 => "1 张$5 纸币 + 1 张$2 纸币",
];

foreach ($testCases as $amount => $expected) {
    $output = rendreMonnaie($amount);
    echo "金额$$amount: 输出='$output'，预期='$expected' → " . ($output === $expected ? "通过" : "失败") . "\n";
}

代码说明 #

1. 边界判断：直接拦截无法找零的金额，避免无效计算。
2. 奇数处理：通过添加1张$5将奇数金额转为偶数，确保后续可用$10和$2凑齐。
3. 大面额优先：先尽可能用$10，再用$2，保证纸币数量最少。
4. 测试覆盖：包含要求的特定金额及边界场景，验证结果正确性。

内容的提问来源于stack exchange，提问作者Jérôme Delodder