河内塔方案(递归)

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的问题，下面是一个更简单、更简单的代码版本，用于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