Kann jemand LINQ missbrauchen und dieses Geldrätsel lösen?

Question

Aus Spaß, würde ich gerne sehen, wie jemand LINQ benutzt und missbraucht, um dieses Geldproblem zu lösen. Ich habe wirklich keine Ahnung, wie Sie es tun würden - ich nehme an, einige Sätze zu füllen und dann davon zu wählen.

Wenn Sie eine Gesamtanzahl von Münzen erhalten und die Gesamtmenge aller Münzen addieren: Zeigen Sie jede mögliche Münzkombination an. Münzen sind Quarters (.25), Dimes (.10) Nickels (.05) und Pennies (.01)

Enthalten Sie die Option, so dass es eine Null von einer Art von Münze geben kann oder es mindestens 1 sein muss jeder.

Beispiel Problem: Wenn ich 19 Münzen habe und die Münzen summieren sich zu $ ​​1.56 und es muss mindestens 1 von jeder Art von Münze sein.

Die Antwort wäre:

1 Quarters, 9 Dimes, 8 Nickels, 1 Pennies

2 Quarters, 5 Dimes, 11 Nickels, 1 Pennies

2 Quarters, 9 Dimes , 2 Nickels, 6 Pennies

3 Quarters, 1 Dimes, 14 Nickels, 1 Pennies

3 Quarters, 5 Dimes, 5 Nickels, 6 Pennies

4 Quarters, 1 Dimes, 8 Nickels, 6 Pennies

5 Quarters, 1 Dimes, 2 Nickels, 11 Pennies

Und wenn wir Null für eine coint erlaubt wir erlaubt erhalten eine zusätzliche 0 Viertel, 13 Dimes, 5 Nickels, 1 Pennies

Hier ist ein Beispiel C# -Code mit einer Brute-Force-Methode, um das Problem zu lösen. Mach dir keine Mühe, die Probe zu verbessern, lass uns nur eine Lösung mit Linq sehen. // Versuchen Sie, möglichst keinen regulären C# Looping-Code zu verwenden.

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

Ungeprüfte, aber:

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

---

Eigentlich für den Einzelhandel - vielleicht eine bessere Frage ist: "Was ist die wenigsten Münzen ich geben kann"? Ersetzen durch:

... 
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 
... 

und verwenden entweder First() oder Take(...) ;-p

Sie könnten wahrscheinlich auch die Anzahl der geprüften Fälle reduzieren durch Subtrahieren (zum Beispiel) q im maxDimes Test (und so weiter .. .) - etwas wie (vereinfacht):

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