Maison > développement back-end > Golang > Erreur de mémoire lors de la conversion d'un problème de pièce récursive naïve

Erreur de mémoire lors de la conversion d'un problème de pièce récursive naïve

WBOY
Libérer: 2024-02-08 21:39:38
avant
506 Les gens l'ont consulté

Erreur de mémoire lors de la conversion dun problème de pièce récursive naïve

L'éditeur php Yu Zai a accidentellement commis une erreur de mémoire lors de la résolution du simple problème de pièce récursive. Ce problème reçoit un certain nombre de pièces et un montant cible, et est nécessaire pour calculer toutes les différentes combinaisons qui composent le montant cible. Normalement, nous pourrions utiliser la récursivité pour résoudre ce problème, mais mon erreur de mémoire a entraîné des calculs incorrects. Dans cet article, je vais réexpliquer la bonne solution et fournir quelques conseils pratiques pour éviter des erreurs similaires.

Contenu de la question

J'essaie de résoudre le problème suivant :

Deux joueurs commencent avec une pile de pièces, et chaque joueur peut choisir de prendre une ou deux pièces de la pile. Le joueur qui prend la dernière pièce a perdu.

J'ai trouvé l'implémentation récursive simple suivante (Aire de jeux) :

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"
}
Copier après la connexion

Le code ci-dessus fonctionne bien.

Cependant, lorsque j'améliore cette solution en mettant en œuvre la mémorisation (voir ci-dessous ou dans la cour de récréation), j'obtiens une mauvaise réponse.

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))
}
Copier après la connexion

Toute aide sur les raisons pour lesquelles la deuxième implémentation renvoie des valeurs différentes de celles de la première implémentation serait grandement appréciée !

Solution

Votre mémoire est fausse : le gagnant dépend non seulement du nombre actuel de pièces, mais aussi du tour de qui. Vous aurez besoin de quelque chose comme ceci :

type state struct {
    coinsRemaining int
    currentPlayer string
}
memo := make(map[state]string)
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:stackoverflow.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal