Башни Ханоя в схеме (рекурсивный)

Question

Я написал следующий код в схеме сегодня, но оценка неверна. Пожалуйста, не говори мне, что я сосу при программировании, я понимаю, что это классическая проблема рекурсии, но у меня возникли проблемы с ним:

(define (towers-of-hanoi n source temp dest) 
(if (= n 1) 
    (begin (display "Move the disk from ") 
     (display source) 
     (display " to ") 
     (display dest) 
     (newline)) 
(begin (towers-of-hanoi (- n 1) source temp dest) 
     (display "Move the disk from ") 
     (display source) 
     (display " to ") 
     (display dest) 
     (newline) 
    (towers-of-hanoi(- n 1) temp source dest)))) 

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

Answer 1

В вашем коде последний рекурсивный вызов представляется неправильным, и существует проблема с порядком параметров процедуры. Попробуйте вместо этого:

(define (towers-of-hanoi n source dest temp) 
    (if (= n 1) 
     (begin 
     (display "Move the disk from ") 
     (display source) 
     (display " to ") 
     (display dest) 
     (newline)) 
     (begin 
     (towers-of-hanoi (- n 1) source temp dest) 
     (display "Move the disk from ") 
     (display source) 
     (display " to ") 
     (display dest) 
     (newline) 
     (towers-of-hanoi (- n 1) temp dest source)))) 

Я заметил, что вы задавали вопросы помечен как racket, вот более идиоматический и сокращенный вариант той же коду, для Ракетки:

(define (towers-of-hanoi n source dest temp) 
    (cond [(= n 1) 
     (printf "Move the disk from ~a to ~a~n" source dest)] 
     [else 
     (towers-of-hanoi (sub1 n) source temp dest) 
     (printf "Move the disk from ~a to ~a~n" source dest) 
     (towers-of-hanoi (sub1 n) temp dest source)])) 

В любом случае, это работает, как ожидалось:

(towers-of-hanoi 3 "source" "dest" "temp") 

Move the disk from source to dest 
Move the disk from source to temp 
Move the disk from dest to temp 
Move the disk from source to dest 
Move the disk from temp to source 
Move the disk from temp to dest 
Move the disk from source to dest