C++で支払いに必要な紙幣の枚数を計算する方法

問題概要

支払うべき金額 pay_Rupees(ルピー)と、額面がそれぞれ Rupees_amount_1 および Rupees_amount_2 の2種類の紙幣が無限枚あるものとします。このとき、ちょうど distribution_total 枚の紙幣を使って pay_Rupees を支払うという条件のもとで、Rupees_amount_1 の紙幣が何枚必要になるかを求めます。条件を満たす支払い方が存在しない場合は -1 を返します。

入力例1

Rupees_amount_1 = 1, Rupees_amount_2 = 5, pay_Rupees = 11, distribution_total = 7

出力例1

必要な紙幣の枚数: 6

説明

6×1 + 5×1 = 11 となり、紙幣の総枚数は 6 + 1 = 7 枚

入力例2

Rupees_amount_1 = 2, Rupees_amount_2 = 3, pay_Rupees = 10, distribution_total = 4

出力例2

必要な紙幣の枚数: 2

説明

2×2 + 3×2 = 10 となり、紙幣の総枚数は 2 + 2 = 4 枚

解法のアプローチ

a1 を額面 Rupees_amount_1 の紙幣の枚数、N を紙幣の総枚数(distribution_total)とします。金額 P(pay_Rupees)を支払うとき、次の等式が成り立ちます。

a1 × Rupees_amount_1 + (N − a1) × Rupees_amount_2 = P

この式を a1 について変形していきます。

P = a1 × Rupees_amount_1 + N × Rupees_amount_2 − a1 × Rupees_amount_2
P − N × Rupees_amount_2 = a1 × (Rupees_amount_1 − Rupees_amount_2)
a1 = (P − N × Rupees_amount_2) / (Rupees_amount_1 − Rupees_amount_2)

したがって、a1 が整数になるときのみ解が存在し、割り切れない場合は -1 を返します。

アルゴリズムの手順

• すべての値を入力として受け取ります。
• 関数 notes_needed(int Rupees_amount_1, int Rupees_amount_2, int pay_Rupees, int distribution_total) が、必要な紙幣の枚数を計算して返します。
• カウント用変数 count を 0 で初期化します。
• total = pay_Rupees − (Rupees_amount_2 * distribution_total) を計算します。
• total_given = Rupees_amount_1 − Rupees_amount_2 を設定します。
• total % total_given == 0 であれば、total / total_given を答えとして返します。
• 割り切れない場合は -1 を返します。

C++実装例

#include<bits/stdc++.h>
using namespace std;
int notes_needed(int Rupees_amount_1, int Rupees_amount_2, int pay_Rupees, int distribution_total){
    int count = 0;
    int total = pay_Rupees - (Rupees_amount_2 * distribution_total);
    int total_given = Rupees_amount_1 - Rupees_amount_2;
    if (total % total_given == 0){
        count = total / total_given;
        return count;
    } else {
        return -1;
    }
}
int main(){
    int Rupees_amount_1 = 1;
    int Rupees_amount_2 = 5;
    int pay_Rupees = 11;
    int distribution_total = 7;
    cout<<"Count of number of currency notes needed are: "<<notes_needed(Rupees_amount_1, Rupees_amount_2, pay_Rupees, distribution_total);
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of number of currency notes needed are: 6

注意点

この実装では、Rupees_amount_1 と Rupees_amount_2 が同じ値の場合にゼロ除算が発生するため注意が必要です。また、計算結果の count が負になるケース(支払金額が「総枚数 × 小さい方の額面」より小さい場合など)も、実際には解が存在しないため、実務では事前チェックを追加することが推奨されます。