0

はい、私はこれに似た投稿があったことを知っていますが、それらをすべて調べた後、私はプログラミングに非常に慣れていないのでまだ立ち往生しており、与えられた答えはどれも私の問題に役立つほど具体的ではありませんでした。

質問。アイテムのコスト（1ドル以下）が与えられた場合に、購入者が50セント、20セント、10セント、5セント、および1セントのコインの数を与える効率的なACL（アルゴリズムコンピューター言語）アルゴリズムを記述します。彼らが1ドルを渡した場合に受け取ります。変更するコインの数を最小限に抑える必要があります。

質問は特定のプログラミング言語とは関係がなく、答えはif、if-else、whileループなどの単純なACL言語のみを使用でき、配列やその他の高度なコマンドは使用できません。

これが私がいる場所です：

ここにコードを入力アルゴリズム最小変更量

{
    int cost, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    if (cost <= 50)
    {
        fifty = 1;

完成したコード、あなたの助けに感謝します！あいまいさが見られる場合、またはコードを簡略化するのに役立つ場合は、お知らせください。

Algorithm how much change
{
    int cost, change, fifty, twenty, ten, five, one;

    fifty = 0;
    twenty = 0;
    ten = 0;
    five = 0;
    one = 0;

    read (cost);
    change = 100 - cost;

    if (change >= 50)
    {
        fifty = fifty + 1;
        change = change - 50;
    }
    while (change >= 20)
    {
        twenty = twenty + 1;
        change = change - 20;
    }
    while (change >= 10)
    {
        ten = ten + 1;
        change = change - 10;
    }
    while (change >= 5)
    {
        five = five + 1;
        change = change - 5;
    }
    while (change >= 1)
    {
        one = one + 1;
        change = change - 1;
    }

    print(one, five, ten, twenty, fifty);
}
4

5 に答える 5

2

実際には、コスト> = 50は1回だけチェックする必要がありますが、これはより一般的です（1ドルを超える場合）

while (cost >= 50)
{
fifty++;
cost -= 50;
}
while (cost >= 20)
{
twenty++;
cost -=20;
}
...
于 2011-03-08T07:43:40.760 に答える
2

あなたの特定の変化量については、単純な貪欲な素朴な「私がもうできなくなるまで最大のものを選ぶ」戦略がうまくいくと私は信じています。

元。：

  1. その50の量が変更量よりも大きくなる前に、50をいくつ選ぶことができますか？その50の数を追跡し、合計からその量を引きます
  2. 20代、10代など、繰り返します。

ただし、欲張り法が機能するとは限りません。「一般的な」ソリューションについては、コインの変更-アルゴリズム担当者を参照してください。

于 2011-03-08T07:44:38.960 に答える
1

これは宿題のように聞こえるので、すぐに答えを出すつもりはありませんが、正しい方向へのヒントを与えます。

あなたがあなたのプログラムのあるポイントであるとしましょう。返還する金額が残っています。たとえば、80セントです。必ず返却しなければならないコインを1枚手に入れるにはどうすればよいですか？

于 2011-03-08T07:44:06.137 に答える
1

ヒント：最大のコインから始めて、使用できるコインの最大数を見つけてから、2番目に大きいコインに移動して繰り返します。25lolの代わりに20コインを使うことで彼らはあなたを楽にしてくれたようです。

于 2011-03-08T07:45:42.513 に答える
0

ここに画像の説明を入力してください

more detailed:

ここに画像の説明を入力してください

and even a brute force algorithm which is O(d M^d)

ここに画像の説明を入力してください
This is from マックス・アレクセーエフ, University of South Carolina cse。

于 2011-03-08T07:49:06.733 に答える