Может кто-то злоупотребить LINQ и решить эту денежную головоломку?

Question

Ради удовольствия я хотел бы, чтобы кто-то использовал и злоупотреблял LINQ для решения этой проблемы с деньгами. Я действительно понятия не имею, как бы вы это сделали - я полагаю, заполнив некоторый набор, а затем выбрав его.

Если задано общее количество монет и указать общее количество всех монет, сложенных вместе: Показать все возможные комбинации монет. Монеты: четверть (.25), десять центов (.10), никель (.05) и пенни (.01)

Включите эту опцию, чтобы тип монеты мог быть нулевым или должен быть хотя бы один из них.

Пример задачи: если у меня есть 19 монет, и монеты складываются до 1,56 доллара, и должна быть как минимум 1 монета каждого типа.

Ответ будет:

1 квартал, 9 центов, 8 никелей, 1 пенни

2 четверти, 5 центов, 11 никелей, 1 копейка

2 четверти, 9 центов, 2 никеля, 6 копеек

3 квартала, 1 цент, 14 никелей, 1 пенни

3 четверти, 5 центов, 5 никелей, 6 копеек

4 четверти, 1 цент, 8 никелей, 6 копеек

5 кварталов, 1 цент, 2 никеля, 11 пенсов

И если мы допустим ноль для монеты, мы позволим получить дополнительную 0 кварталов, 13 центов, 5 никелей, 1 пенни

Вот пример кода C #, использующего метод грубой силы для решения проблемы. Не беспокойтесь об улучшении примера, давайте просто посмотрим решение с использованием Linq. // Старайтесь не использовать какой-либо обычный циклический код c #, если это возможно.

private void SolveCoinProblem(int totalNumberOfCoins, double totalAmount, int minimumNumberOfEachCoin)
    {
        int foundCount = 0;
        long numberOfTries = 0;
        Console.WriteLine(String.Format("Solving Coin Problem:TotalNumberOfCoins={0}TotalAmount={1}MinimumNumberOfEachCoin{2}", totalNumberOfCoins, totalAmount, minimumNumberOfEachCoin));
        for (int totalQuarters = minimumNumberOfEachCoin; totalQuarters < totalNumberOfCoins; totalQuarters++)
        {
            for (int totalDimes = minimumNumberOfEachCoin; totalDimes < totalNumberOfCoins; totalDimes++)
            {
                for (int totalNickels = minimumNumberOfEachCoin; totalNickels < totalNumberOfCoins; totalNickels++)
                {
                    for (int totalPennies = minimumNumberOfEachCoin; totalPennies < totalNumberOfCoins; totalPennies++)
                    {
                        numberOfTries++;
                        if (totalQuarters + totalDimes + totalNickels + totalPennies == totalNumberOfCoins)
                        {
                            if (Math.Round((totalQuarters * .25) + (totalDimes * .10) + (totalNickels * .05) + (totalPennies * .01),2) == totalAmount)
                            {
                                Console.WriteLine(String.Format("{0} Quarters, {1} Dimes, {2} Nickels, {3} Pennies", totalQuarters, totalDimes, totalNickels, totalPennies));
                                foundCount++;
                            }
                        }
                    }
                }
            }
        }
        Console.WriteLine(String.Format("{0} Combinations Found. We tried {1} combinations.", foundCount, numberOfTries));
    }

Answer 1

Не проверено, но:

        int minQuarters = 1, minDimes = 1,
            minNickels = 1, minPennies = 1,
            maxQuarters = 19, maxDimes = 19,
            maxNickels = 19, maxPennies = 19,
            coinCount = 19, total = 156;
        var qry = from q in Enumerable.Range(minQuarters, maxQuarters)
                  from d in Enumerable.Range(minDimes, maxDimes)
                  from n in Enumerable.Range(minNickels, maxNickels)
                  from p in Enumerable.Range(minPennies, maxPennies)
                  where q + d + n + p == coinCount
                  where q * 25 + d * 10 + n * 5 + p == total
                  select new {q,d,n,p};
        foreach (var row in qry)
        {
            Console.WriteLine("{0} quarter(s), {1} dime(s), {2} nickel(s) and {3} pennies",
                row.q, row.d, row.n, row.p);
        }

---

На самом деле, для розничных целей - может быть, лучше спросить: «Сколько монет я могу выдать»? Заменить на:

...
from p in Enumerable.Range(minPennies, maxPennies)
where q + d + n + p <= coinCount
where q * 25 + d * 10 + n * 5 + p == total
orderby q + d + n + p
...

и используйте First() или Take(...); -p

Вы также можете уменьшить количество проверенных случаев, вычитая (например) q в тесте maxDimes (и так далее ...) - что-то вроде (упрощенно):

        int minCount = 1,
            coinCount = 19, total = 156;
        var qry = from q in Enumerable.Range(minCount, coinCount - (3 * minCount))
                  where q * 25 <= total
                  from d in Enumerable.Range(minCount, coinCount - (q + (2 * minCount)))
                  where q * 25 + d * 10 <= total
                  from n in Enumerable.Range(minCount, coinCount - (q + d + minCount))
                  where q * 25 + d * 10 + n * 5 <= total
                  from p in Enumerable.Range(minCount, coinCount - (q + d + n))
                  where q + d + n + p == coinCount
                  where q * 25 + d * 10 + n * 5 + p == total
                  select new { q, d, n, p };