方案:河内塔(递归) [英] Scheme: Towers of Hanoi (recursion)

问题描述

我首先要说这是家庭作业；所以我不是在寻求解决方案，只是一些技巧.我已经对此进行了大约一个星期的思考.我想出的每个解决方案都不会递归地执行此操作，因为我无法用列表作为唯一参数来递归地执行此操作.我的教授说，他们能够使用大约6个辅助功能来做到这一点.

I'd like to start off by saying this is homework; so I'm not asking for a solution, just some tips. I've been ruminating on this for about a week now. Every solution I come up with doesn't do it recursively, seeing as I can't manage to wrap my head around doing it recursively with the list as the only parameter. My professor said they were able to do it with about 6 helper functions.

如上所述，我必须解决将列表作为唯一参数的问题.这是我最近尝试的例子.

As mentioned, I have to solve the problem taking taking the list as the only parameter. Here's an example of what I've got on my latest attempt.

(define (sumSublists lst)
  (if (= (length lst) 0)
      0
      (+ (length (car lst)) (sumSublists (cdr lst)))
  )
)

(define (hanoi towersNum)
  (sub1 (sumSublists towersNum))

    (if (= (sumSublists towersNum) 1)
        (print towersNum)
        (begin (if (= (sumSublists towersNum) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) 
               )
        )
    )
)

sumSublists返回游戏中的磁盘数量.我遇到了一个无限循环，因为每次使用它时它都会获得相同的值，因此永远不会减小该值.我的问题是，我很习惯使用命令式命令和OOP，因此我不确定在河内只接受一个参数的情况下如何做到这一点.

sumSublists returns how many disks there are in the game. I'm getting an infinite loop since every time it gets used it takes the same value, thus not ever reducing the value. My problem with that, is I'm so used to imperative and OOP with the use of variables that I'm not sure how I can do this when Hanoi only takes one parameter.

河内的代码是我试图将我的项目从C ++变成Scheme.

The code for Hanoi is my attempt to turn my project from C++ into Scheme.

感谢您的帮助.顺便说一下，我正在使用Racket博士作为我的IDE.

Any help is appreciated. I'm using Dr. Racket as my IDE by the way.

推荐答案

如果您知道如何使用包含三个列表A，B和C的三个参数来解决该问题，那么您已经知道如何解决它带有一个参数，该参数将列表中的三个列表保存在(A B C)中.

If you know how to solve it with the three arguments holding the three lists A, B and C, you already know how to solve it with the one argument holding the three lists in a list, (A B C).

这个问题正在计数，因为您不允许使用单独的参数将数字保存在其中.没关系，您可以通过列出列表的长度来计数，该列表的长度可以用作数字.并且，如果列表的长度为n，则很容易从列表中创建长度为n-1的列表.所以最后您只需要null?.

The problem is counting, as you're not allowed to use a separate argument to hold the number in it. Never mind that, you can count by making a list, its length to serve as the number. And if a list's length is n, it is easy to make a list with length n-1 from it. So in the end all you need is null?.

此方案将使您始终将head元素用作临时项，将参数从参数列表上的第一个条目移至第二个条目，并根据需要在其中打开和关闭新的级别".必须命名三个极点"，然后将其归类为原始顺序以最终得到回报.

This scheme would have you always move items from the first entry on the argument list to the second, using the head element as temporary, where you'd open and close new "levels" as needed. The three "poles" would have to be named, to be sorted back into the original order for the final return.

(请参见

(cf. another answer of mine which discusses the actual recursive algorithm itself).

这篇关于方案:河内塔(递归)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！