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 });
}

这很好用，但例如price = 3它将{1c, 2c}和{2c, 1c}视为两种不同的表示。该问题可以通过将所有找到的值存储在 List 中来解决，然后在生成重复项时删除它们，但这样会牺牲代码的生成器性质。可以修改代码以不包含重复项，同时仍然是使用的生成器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可能不会起作用/很难起作用，相反，您应该首先尝试阻止它们被添加。您可以通过添加支票来做到这一点，以便您只按降序添加硬币。另一种选择是使用我在 C# 中没有做过的集合操作，但是集合没有顺序的概念，所以如果这两个值是集合，它们将被认为是相等的。

于 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 回答
0

如果它们不大于最后添加的硬币，您只需要添加硬币：

    IEnumerable<IEnumerable<int>> getCoins(int price){
        return getCoins(price, Int32.MaxValue);
    }

    IEnumerable<IEnumerable<int>> getCoins(int price, int lastValue)
    {
        int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
        if (coinValues.Contains(price) && price <= lastValue) 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 <= lastValue))
            foreach (IEnumerable<int> match in getCoins(price - coin, coin))
                yield return match.Concat(new int[] { coin });
    }
于 2013-05-01T17:03:35.437 回答
0

在我看来，它比 DavidN 略有改进，因为它是自然排序的。（对不起，我喜欢括号。）

    public IEnumerable<IEnumerable<int>> getCoins(int price, int MaxCoin = 200)
    {
        int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }.Reverse().ToArray(); // Coin values

        foreach (int coin in coinValues.Where(x => x <= price && x <= MaxCoin))
        {
            if (coin == price)
            {
                yield return new int[] { price }; // If the price can be represented be a single coin
            }
            else
            {
                foreach (IEnumerable<int> match in getCoins(price - coin, coin))
                {
                    yield return new int[] { coin }.Concat(match);
                }
            }
        }
    }
于 2013-05-01T18:31:29.177 回答