Einführung

Über Probem31 von Project Euler. Ich habe versucht, es durch einen Anfänger der rekursiven Funktion zu erklären, indem ich mich auf die Antworten anderer Leute in der rekursiven Funktion bezog. Illustration wird ebenfalls unten gezeigt. Schauen Sie also auch dort nach.

Problem

Aufgabe 31 "Summe der Münzen" In Großbritannien gibt es Pfund £ und Pence p, und es gibt acht Arten von Münzen im allgemeinen Umlauf. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). Es ist möglich, £ 2 mit der folgenden Methode zu verdienen. 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p Wie viele Möglichkeiten kann ich mit diesen Münzen 2 € verdienen?

Japanische Version Englische Version offiziell

Politik

Wiederholen Sie den Vorgang des Herausnehmens einer beliebigen aus "Münzen = [1,2,5,10,20,50,100,200]", bis sie 200 erreicht. Es wäre nicht großartig, wenn es von Menschenhand gemacht würde, aber es ist unzählig, also in solchen Fällen "rekursive Funktion"!

Was ist eine rekursive Funktion?

Eine Funktion, die sich innerhalb der durch def ~ end definierten Funktion aufruft. Wenn es berühmt ist, wird die Fibonacci-Funktion oft als Einführung in rekursive Funktionen behandelt. Wenn Sie es zum ersten Mal gehört haben, suchen Sie bitte.

Ein weiterer Kommentar: [Illustration] Hierarchische rekursive Funktion [Ruby]

Antworten

def coin_count(coins, goal, last = 0)
  if goal == 0
    return 1
  end

  total = 0
  coins.each do |c|
    if c < last
      next
    end
    if goal >= c
      total += coin_count(coins, goal - c, c)
    end
  end

  total
end

coins = [1,2,5,10,20,50,100,200]
puts coin_count(coins,200)

Ich schämte mich zu sagen, dass ich es nicht alleine lösen konnte, also habe ich es basierend auf [hier] erstellt (http://joezack.com/2010/09/26/project-euler-problem-31-in-ruby/). Ich werde diese Lösung auf Japanisch erklären.

Kommentar

Was ich diesmal machen möchte, ist die Nummer "200". Setzen Sie also "Ziel = 200" und den Wert einer Münze

Zunächst beginnt die Erklärung innerhalb jeder Anweisung in der Funktion.

if c < last
  next
end

Dies soll verhindern, dass mehr als die letzte "letzte" hinzugefügt wird. 50 + 50 + 100 und 50 + 100 + 50 sind in dieser Ausgabe identisch. Verwenden Sie daher nur Muster, die in aufsteigender Reihenfolge hinzugefügt werden. next ist der Vorgang, bei dem der Vorgang nach dem nächsten im Block übersprungen wird.

Als nächstes folgt die dritte if-Anweisung in einer Funktion, die eine rekursive Funktion verwendet.

if goal >= c
  total += coin_count(coins, goal - c, c)
end

Dieses Mal ist "c" 1 <= c ", weil es eines der Elemente von" Münzen = [1,2,5,10,20,50,100,200] "ist. Das als Argument an "coin_count" (Münzen, Ziel, letztes) übergebene "Ziel" wird also für "Ziel - c" gegen 0 abnehmen.

Wenn "c = 50 und Ziel = 200" ist, ist es wie folgt.

Beispiel)
Ziel mit rekursiver Funktion-Wenn c wiederholt wird, wird das Argument Ziel
Erstes Mal: 150     ※coin_count(coins, 150, 50)Rufen Sie an mit
Zweites Mal: 100     ※coin_count(coins, 100, 50)
Drittes Mal: 50      ※coin_count(coins, 50, 50)
4 ..: 0       ※coin_count(coins, 0, 50)

Das vierte Mal wird die Funktion mit "coin_count (coin, 0, 50)" aufgerufen

if goal == 0
  return 1
end

Es wird also endlich hier sein,

total += coin_count(coins, goal - c, c)

Die coin_count Funktion von hat einen Rückgabewert von 1. An diesem Punkt wird es schließlich "total + = 1" und 1 wird hinzugefügt.

--Wenn Ziel> 0 --Wenn Ziel <0

In diesem Fall bleibt "total = 0" 0 und wird an den Rückgabewert übergeben. Schließlich wird die Gesamtzahl der Kombinationen als Wert der Summe erhalten.

Illustriert

Ich habe versucht, diesen Zustand herauszufinden, in dem die Funktion wiederholt aufgerufen wird. projecteuler31解説.001.jpeg

Am Ende

Bitte lassen Sie mich wissen, wenn fehlende Punkte, falsche Punkte oder klarere Erklärungen vorhanden sind. Danke fürs Lesen.

[Illustration] Finden der Summe von Münzen mit einer rekursiven Funktion [Ruby]