Ralat ingatan semasa menukar masalah syiling rekursif naif

editor php Yu Zai secara tidak sengaja membuat ralat ingatan semasa menyelesaikan masalah syiling rekursif mudah. Masalah ini diberikan sejumlah syiling dan jumlah sasaran, dan diperlukan untuk mengira semua kombinasi berbeza yang membentuk jumlah sasaran. Biasanya, kami boleh menggunakan rekursi untuk menyelesaikan masalah ini, tetapi ralat ingatan saya mengakibatkan pengiraan yang salah. Dalam artikel ini, saya akan menerangkan semula penyelesaian yang betul dan memberikan beberapa petua praktikal untuk mengelakkan kesilapan yang sama.

Kandungan soalan

Saya cuba menyelesaikan masalah berikut:

Dua pemain bermula dengan longgokan syiling, dan setiap pemain boleh memilih untuk mengambil satu atau dua syiling daripada longgokan. Pemain yang mengambil syiling terakhir kalah.

Saya menghasilkan pelaksanaan rekursif mudah berikut (Taman permainan):

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

Kod di atas berfungsi dengan baik.

Walau bagaimanapun, apabila saya menambah baik penyelesaian ini dengan melaksanakan hafalan (lihat di bawah atau di taman permainan), saya mendapat jawapan yang salah.

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

Sebarang bantuan tentang sebab pelaksanaan kedua mengembalikan nilai yang berbeza daripada pelaksanaan pertama akan sangat dihargai!

Penyelesaian

Memori anda salah: pemenang bergantung bukan sahaja pada bilangan syiling semasa, tetapi juga pada giliran siapa. Anda memerlukan sesuatu seperti ini:

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

Atas ialah kandungan terperinci Ralat ingatan semasa menukar masalah syiling rekursif naif. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!