プログラミング演習問題(支払い可能性判定問題編)

社内の勉強会用に準備した問題とその解説を書いていく。
下の方に解答を載せているので自分で解きたい人はスクロールしすぎないように。

問題

ある世界には硬貨(紙幣)が 2 種類しかない。その世界で売買行為が行われる際に、たまに支払いができないことが起こった。なので、お店の人が価格をつける際に、その金額が支払いができるかどうか知りたい。

例

12 円と 66 円の世界である時、6 円の支払いは可能である。それは 12 円玉を 6 枚払って 66 円玉を 1 枚お釣りとしてもらえばいい。
しかしその世界では 7 円の支払いは不可である。その世界では偶数の金額しか払えないからである。

問題設定

• 入力: 自然数 $a, b, n , (1 \leq a, b, n \leq 10000)$
• 出力: $a, b$ 円の 2 種類の硬貨しかない世界で $n$ 円の支払いができるなら true. 支払いができないなら false

解答までの雑談

発展問題として下記の設定を付け加えた。

使用枚数の制限がなかったため、枚数の多い売買は数え間違い多発し社会問題となった。そこで政府は 1 回の売買行為に対して(支払いとお釣り)合計で 20 枚までしか受け渡しできない法律を作った。その場合でも対応できるようにしたい。

そのとき、発展問題の方が簡単では？というツッコミが入った。そのツッコミは予想済みだった。最初の問題は、ある数学知識を使うと簡単に解けるが、知らないと枚数の範囲がないので一気に難しくなる。出題意図はそこにあった。

解答例

function isPayable($a, $b, $n) {
    return $n % gcd($a, $b) === 0;
}

function gcd($a, $b) {
    return $b === 0 ? $a : gcd($b, $a % $b);
}

解説

これは一次不定方程式そのままである。
つまり $ax+by=n$ を満たす整数 $x$ と $y$ が存在するかどうかという数学の問題に置き換えられる。この時 $x$ と $y$ が正なら支払い、負ならお釣りとしてもらうことに対応している。

例で述べた 12 円と 66 円の世界で 6 円の支払いを考えると $12x + 66y = 6$ の一次不定方程式を解けばいい。解の一つは $x=6, y=-1$ である(12 円玉 6 枚支払って 66 円玉 1 枚お釣りとしてもらう)。

ここで、一次不定方程式 $ax+by=n$ が整数解 $x, y$ を持つことの必要十分条件として $n$ は $a, b$ の最大公約数の倍数であるというのが知られている。

それを実装したのが上記の解答例となっている。

発展問題の解答例

function isLimitPayable($a, $b, $n) {
    $filter = function ($x) use ($a, $b, $n) {
        $y = ($n - $a * $x) / $b;
        return ($n - $a * $x) % $b === 0 && abs($x) + abs($y) <= 20;
    };  
    return (bool)count(array_filter(range(-20, 20), $filter));
}

まとめ

数学は偉大！