Question

Как мне go добавить еще один параметр к этой функции, который подсчитывает, сколько ходов потребовалось, т. Е. Сколько раз была вызвана функция перемещения? А потом вернитесь (mycurrentanswer, count). Где count - это новый параметр, добавленный в мою функцию, и он должен быть изначально добавлен как ноль?

def playHanoi(pos,a,b,c,n):
        if n == 0:
           return pos
        if n == 1:
           return move(pos, a, b)
        else:
           return playHanoi(move(playHanoi(pos,a,c,b,n-1),a,b),c,b,a,n-1)

Вот моя функция перемещения:

def move(pos, a, b):
        if pos[a] == []:
           return pos
        elif pos[b] == [] or pos[b][-1] >= pos[a][-1]:
           pos[b].append(pos[a].pop(-1))
           return pos
        else:
           raise ValueError('This is an illegal move')

Я хочу, чтобы функция была похожа на this

def playHanoi(pos,a,b,c,n,counter):
            if n == 0:
               return pos
            if n == 1:
               return move(pos, a, b)
            else:
               return (playHanoi(move(playHanoi(pos,a,c,b,n-1),a,b),c,b,a,n-1),j)

Псевдокод

Введите словарь вида {1: [5,4,3,2,1], 2: [], 3: []} (где цифры - диски такого размера, слева от списка - нижняя часть стопки) наряду с a, b, c являются полюсами проблемы Ханоя, поэтому 1,2 и 3 в некотором порядке.
А затем n - это количество дисков, которые я хочу переместить из кучи 1 в 3, т. е. если n = 3, то моя позиция станет {1: [5,4], 2: [], 3: [3,2,1]}.
И затем счетчик конечных компонентов, который будет считать, как много «шагов», то есть время, когда мне приходилось перемещать диск c, чтобы достичь желаемой цели.

Результат для playHanoi({1: [5,4,3,2,1], 2: [], 3: []},1,3,2,3,0) будет ({1: [5,4], 2: [], 3: [3,2,1]}, #ofsteps).

gelonida · Answer 1 · 22 февраля 2020

Здесь одно решение, которое оно возвращает, перемещает и распечатывает изменения в pos. Не стесняйтесь переименовывать переменные в имена из одной буквы, если это то, что требуется для вашего упражнения. Я лично предпочитаю более длинные имена переменных.

def hanoi(pos, p_from, p_to, p_help, n_disks, moves=0):
    if n_disks == 1:
        disk = pos[p_from].pop()
        pos[p_to].append(disk)
        moves += 1
        print("move %d: move a disk from %s to %s: pos: %s" % (moves, p_from, p_to, pos))
        return moves
    moves = hanoi(pos, p_from, p_help, p_to, n_disks-1, moves)
    moves = hanoi(pos,  p_from, p_to, p_help,1 , moves)
    moves = hanoi(pos, p_help, p_to, p_from, n_disks-1, moves)
    return moves

if __name__ == '__main__':
    pos = {1: [5,4,3,2,1], 2: [], 3: []}
    moves = hanoi(pos, 1,3,2,5,0)
    print("Total moves = %d" % moves)
    print("Final pos = ", pos)

Вывод будет выглядеть так:

move 1: move a disk from 1 to 3: pos: {1: [5, 4, 3, 2], 2: [], 3: [1]}
move 2: move a disk from 1 to 2: pos: {1: [5, 4, 3], 2: [2], 3: [1]}
move 3: move a disk from 3 to 2: pos: {1: [5, 4, 3], 2: [2, 1], 3: []}
move 4: move a disk from 1 to 3: pos: {1: [5, 4], 2: [2, 1], 3: [3]}
move 5: move a disk from 2 to 1: pos: {1: [5, 4, 1], 2: [2], 3: [3]}
move 6: move a disk from 2 to 3: pos: {1: [5, 4, 1], 2: [], 3: [3, 2]}
move 7: move a disk from 1 to 3: pos: {1: [5, 4], 2: [], 3: [3, 2, 1]}
move 8: move a disk from 1 to 2: pos: {1: [5], 2: [4], 3: [3, 2, 1]}
move 9: move a disk from 3 to 2: pos: {1: [5], 2: [4, 1], 3: [3, 2]}
move 10: move a disk from 3 to 1: pos: {1: [5, 2], 2: [4, 1], 3: [3]}
move 11: move a disk from 2 to 1: pos: {1: [5, 2, 1], 2: [4], 3: [3]}
move 12: move a disk from 3 to 2: pos: {1: [5, 2, 1], 2: [4, 3], 3: []}
move 13: move a disk from 1 to 3: pos: {1: [5, 2], 2: [4, 3], 3: [1]}
move 14: move a disk from 1 to 2: pos: {1: [5], 2: [4, 3, 2], 3: [1]}
move 15: move a disk from 3 to 2: pos: {1: [5], 2: [4, 3, 2, 1], 3: []}
move 16: move a disk from 1 to 3: pos: {1: [], 2: [4, 3, 2, 1], 3: [5]}
move 17: move a disk from 2 to 1: pos: {1: [1], 2: [4, 3, 2], 3: [5]}
move 18: move a disk from 2 to 3: pos: {1: [1], 2: [4, 3], 3: [5, 2]}
move 19: move a disk from 1 to 3: pos: {1: [], 2: [4, 3], 3: [5, 2, 1]}
move 20: move a disk from 2 to 1: pos: {1: [3], 2: [4], 3: [5, 2, 1]}
move 21: move a disk from 3 to 2: pos: {1: [3], 2: [4, 1], 3: [5, 2]}
move 22: move a disk from 3 to 1: pos: {1: [3, 2], 2: [4, 1], 3: [5]}
move 23: move a disk from 2 to 1: pos: {1: [3, 2, 1], 2: [4], 3: [5]}
move 24: move a disk from 2 to 3: pos: {1: [3, 2, 1], 2: [], 3: [5, 4]}
move 25: move a disk from 1 to 3: pos: {1: [3, 2], 2: [], 3: [5, 4, 1]}
move 26: move a disk from 1 to 2: pos: {1: [3], 2: [2], 3: [5, 4, 1]}
move 27: move a disk from 3 to 2: pos: {1: [3], 2: [2, 1], 3: [5, 4]}
move 28: move a disk from 1 to 3: pos: {1: [], 2: [2, 1], 3: [5, 4, 3]}
move 29: move a disk from 2 to 1: pos: {1: [1], 2: [2], 3: [5, 4, 3]}
move 30: move a disk from 2 to 3: pos: {1: [1], 2: [], 3: [5, 4, 3, 2]}
move 31: move a disk from 1 to 3: pos: {1: [], 2: [], 3: [5, 4, 3, 2, 1]}
Total moves = 31
Final pos = {1: [], 2: [], 3: [5, 4, 3, 2, 1]}

Ниже моих предыдущих ответов, которые могут быть интересны для некоторых людей.

Одним из способов ведения такого вида бухгалтерского учета было бы добавление одного параметра с постоянным объектом, например, dict. Это решение реализовано так, что не нужно проходить через состояние, если он не заинтересован в получении информации о количестве ходов.

def playHanoi(pos,a,b,c,n,state=None):
        if state is None:
            state = {"moves": 0}
        if n == 0:
           return pos
        if n == 1:
           return move(pos, a, b)
        else:
           return playHanoi(move(playHanoi(pos,a,c,b,n-1, state),a,b, state),c,b,a,n-1, state)

def move(pos, a, b, state):
        state["moves"] += 1
        if pos[a] == []:
           return pos
        elif pos[b] == [] or pos[b][-1] >= pos[a][-1]:
           pos[b].append(pos[a].pop(-1))
           return pos
        else:
           raise ValueError('This is an illegal move')


state = { "moves": 0 }
pos = playHanoi({1: [5,4,3,2,1], 2: [], 3: []}, 1,3,2,5, state)
print("I needed %d moves" % state["moves"])

В этом конкретном случае я мог бы написать:

def playHanoi(pos,a,b,c,n,state={"moves": 0})

и удалил оператор if, который назначает dict для указания, если None,

, но в целом это не очень хорошая практика, так как изменения в сохранении сохраняются Необязательные параметры в Python функции и их значения по умолчанию Зная, что довольно много кода из SO копируется и вставляется в реальные приложения, я не хотел этого делать, поскольку из контекста это может быть опасно.

Простая версия без учета дисков (pos) Вот простая версия Ханоя, которая распечатывает диск для перемещения и возвращает общее количество перемещаемых дисков

def hanoi(n_disks, p_from, p_to, p_help, moves=0):
    if n_disks == 1:
        moves += 1
        print("move %d: move a disk from %s to %s" % (moves, p_from, p_to))
        return moves
    moves = hanoi(n_disks-1, p_from, p_help, p_to, moves)
    moves = hanoi(1, p_from, p_to, p_help, moves)
    moves = hanoi(n_disks-1, p_help, p_to, p_from, moves)
    return moves

moves = hanoi(5, "stackA", "stackB", "stackC")
print("Total moves = %d" % moves)

Вывод будет выглядеть следующим образом:

move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackB to stackA
move a disk from stackC to stackA
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackB to stackC
move a disk from stackB to stackA
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
Total moves = 31

Другое (надеюсь, окончательное) решение после продолжающегося обсуждения:

pos и j (количество ходов) возвращаются. Вместо двух используется только одна функция.

Просто удалите print() внутри функции, если она вам не нужна. Это помогает понять, как работает код, но, возможно, не требуется в вашем случае.

Еще одно примечание. Точно так же, как и в вашем исходном коде, также изменяется модификация, переданная функции playHanoi.

В некоторых ситуациях это нежелательно. Если интересно, я могу предоставить версию, в которой initial_pos не будет изменен.

def playHanoi(pos, a, b, c, n, j=0):
    if n == 1:
        disk = pos[a].pop()
        pos[b].append(disk)
        j += 1
        print("move %d: move a disk from %s to %s: pos: %s" % (j, a, b, pos))
        return pos, j
    pos, j = playHanoi(pos, a, c, b, n-1, j)
    pos, j = playHanoi(pos,  a, b, c,1 , j)
    pos, j = playHanoi(pos, c, b, a, n-1, j)
    return pos, j

initial_pos = {1: [5,4,3,2,1], 2: [], 3: []}
pos, j = playHanoi(initial_pos, 1,3,2,5,0)
print("Final pos", pos)
print("Total j = %d" % j)
print("look even initial_pos has been modified", initial_pos)

jksjkashalskajdjalaklskalska · Answer 2 · 22 февраля 2020

Мне удалось поиграть с тем, что вы предоставили и что я ищу, и нашел решение для того, что я хочу. Я уверен, что есть бесчисленное множество более элегантных способов, однако, это делает, как требуется.

def playHanoi2(pos,a,b,c,n,j):
    def playHanoi3(pos,a,b,c,n,j):
        if n == 1:
            disk = pos[a].pop()
            pos[b].append(disk)
            j += 1
            return j
        j = playHanoi3(pos, a, c, b, n-1, j)
        j = playHanoi3(pos,  a, b, c,1 , j)
        j = playHanoi3(pos, c, b, a, n-1, j)
        return j
    j = playHanoi3(pos,a,b,c,n,j)
    return (playHanoi(pos,a,b,c,n),j)

Как бы я посчитал количество ходов этой рекурсивной функции?

Псевдокод

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Как бы я посчитал количество ходов этой рекурсивной функции?

Псевдокод

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы