Speicherfehler beim Konvertieren eines naiven rekursiven Münzproblems

php-Editor Yu Zai hat beim Lösen des einfachen rekursiven Münzproblems versehentlich einen Speicherfehler gemacht. Dieses Problem erfordert eine bestimmte Anzahl an Münzen und einen Zielbetrag und muss alle verschiedenen Kombinationen berechnen, aus denen sich der Zielbetrag zusammensetzt. Normalerweise könnten wir dieses Problem mithilfe der Rekursion lösen, aber mein Speicherfehler führte zu falschen Berechnungen. In diesem Artikel werde ich die richtige Lösung noch einmal erklären und einige praktische Tipps geben, um ähnliche Fehler zu vermeiden.

Frageninhalt

Ich versuche das folgende Problem zu lösen:

Zwei Spieler beginnen mit einem Stapel Münzen, und jeder Spieler kann wählen, ob er eine oder zwei Münzen vom Stapel nehmen möchte. Der Spieler, der die letzte Münze nimmt, verliert.

Ich habe mir die folgende einfache rekursive Implementierung ausgedacht (Spielplatz):

func gamewinner(coinsremaining int, currentplayer string) string {
    if coinsremaining <= 0 {
        return currentplayer
    }

    var nextplayer string

    if currentplayer == "you" {
        nextplayer = "them"
    } else {
        nextplayer = "you"
    }

    if gamewinner(coinsremaining-1, nextplayer) == currentplayer || gamewinner(coinsremaining-2, nextplayer) == currentplayer {
        return currentplayer
    } else {
        return nextplayer
    }
}

func main() {
  fmt.println(gamewinner(4, "you")) // "them"
}

Der obige Code funktioniert einwandfrei.

Wenn ich diese Lösung jedoch durch die Implementierung der Memoisierung verbessere (siehe unten oder auf dem Spielplatz), bekomme ich die falsche Antwort.

func gameWinner(coinsRemaining int, currentPlayer string, memo map[int]string) string {
    if coinsRemaining <= 0 {
        return currentPlayer
    }

    var nextPlayer string

    if currentPlayer == "you" {
        nextPlayer = "them"
    } else {
        nextPlayer = "you"
    }

    if _, exists := memo[coinsRemaining]; !exists {
        if gameWinner(coinsRemaining-1, nextPlayer, memo) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer, memo) == currentPlayer {
            memo[coinsRemaining] = currentPlayer
        } else {
            memo[coinsRemaining] = nextPlayer
        }
    }

    return memo[coinsRemaining]
}

func main() {
    memo := make(map[int]string)
    fmt.Println(gameWinner(4, "you", memo))
}

Jede Hilfe dazu, warum die zweite Implementierung andere Werte als die erste Implementierung zurückgibt, wäre sehr dankbar!

Lösung

Deine Erinnerung ist falsch: Der Gewinner hängt nicht nur von der aktuellen Anzahl an Münzen ab, sondern auch davon, wer an der Reihe ist. Du brauchst so etwas:

type state struct {
    coinsRemaining int
    currentPlayer string
}
memo := make(map[state]string)

Das obige ist der detaillierte Inhalt vonSpeicherfehler beim Konvertieren eines naiven rekursiven Münzproblems. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!