algorithm - 欲張りアルゴリズムとコインアルゴリズム

Question

まず、はい、それは私のハードウェアであり、私はそれが難しいと感じているので、いくつかのガイダンスに本当に感謝します。

コイン問題の欲張りアルゴリズムが常に機能する場合の額面については、証明する必要があります。1,x,x2...xnx>=1

• 常に金額よりも小さい最大のコインを選ぶとき、私たちは常に最小のコイン数で必要な金額を取得します。

ありがとうございました。

Answer 1

これはあなたの宿題なので、私は完全な答えを提供しませんが、むしろあなたを案内しようとします：

まず、そのタイプの問題で通常発生するので、最初のいくつかの自然数についてステートメントが真であることを自分で証明してみてください。それらの証拠を作成するために使用するものを要約してみてください。これは通常、正しいアプローチのガイダンスを提供します。

これには誘導を使用します。

あなたを助けるかもしれないもう一つのオプション-基数で数値システムのすべての数を表しますx。これにより、ステートメントが真である理由が明確になります。

これがお役に立てば幸いです。