0

特定のコイン値のセットを持つ通貨でコインを使用して特定の金額を表すすべての可能な方法を返す次のコードを作成しました。

IEnumerable<IEnumerable<int>> getCoins(int price)
{
    int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
    if (coinValues.Contains(price)) yield return new int[] { price }; // If the price can be represented be a single coin

    // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
    foreach (int coin in coinValues.Where(x => x < price))
        foreach (IEnumerable<int> match in getCoins(price - coin))
            yield return match.Concat(new int[] { coin });
}

これは問題なく動作しますが、たとえばとを 2 つの異なる表現としてprice = 3扱います。この問題は、見つかったすべての値を List に保存し、生成されたときに重複を削除することで解決できますが、その方法では、コードのジェネレーターの性質が犠牲になります。を使用してジェネレーターでありながら、重複を含まないようにコードを変更できますか?{1c, 2c}{2c, 1c}yield return

4

5 に答える 5

2

すでに配列にあるコインよりも大きいコインは許可できませんでした。

public IEnumerable<IEnumerable<int>> getCoins(int price)
{
   int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
   if (coinValues.Contains(price))
      yield return new int[] { price }; // If the price can be represented be a single coin

   // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
   foreach (int coin in coinValues.Where(x => x < price))
      foreach (IEnumerable<int> match in getCoins(price - coin))
         if (match.Min() >= coin)
            yield return match.Concat(new int[] { coin });
}

編集：これには、ソートされた配列を生成するという追加の利点があります。ただし、リストは辞書順では生成されません。

3 結果:

  • 2 1
  • 1 1 1

5 件の結果:

  • 5
  • 2 1 1 1
  • 1 1 1 1 1
  • 2 2 1
于 2013-05-01T16:47:20.210 に答える
0

{1c, 2c}問題は、前述のように、実装によって順序が強制され{2c, 1c}、実際には等しくないことです。それらを外側から削除しようとしてIEnumerableもうまくいかないか、うまくいかない可能性があります。代わりに、最初からそれらが追加されないようにする必要があります。降順でのみコインを追加するようにチェックを追加することで、これを行うことができます。もう 1 つの方法は、C# では行っていないセット操作を使用することですが、セットには順序の概念がないため、これら 2 つの値がセットである場合、それらは等しいと見なされます。

于 2013-05-01T16:51:00.967 に答える
0

他の回答が述べたように、コインを降順でのみ追加するようにすることができます。これは機能するはずですが、Min() を使用する代わりに、最後に追加されたコインの追加パラメーターを追加します。

IEnumerable<IEnumerable<int>> getCoins(int price, int prev_coin)
{
    int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
    if (coinValues.Contains(price)) yield return new int[] { price }; // If the price can be represented be a single coin

    // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
    foreach (int coin in coinValues.Where(x => (x < price && x <= prev_coin)))
        foreach (IEnumerable<int> match in getCoins(price - coin, coin))
            yield return match.Concat(new int[] { coin });
}
于 2013-05-01T16:55:56.557 に答える