So a person needs to follow a few rules for the Tower of Hanoi are: There are specific procedures and rules that you have to follow without violating any rules.The aim is to move disks to another tower without breaking the sequence of arrangements. This puzzle also includes three towers, so these disks are stacked in ascending order on these towers. Tower of Hanoi is a type of Mathematical puzzle in which there are disks of different sizes, which can slide on top of each other. So in this guide, we will consider every single aspect around the Tower of Hanoi and its requirements in C. This was a little history behind the name "Tower of Hanoi," but now a question arises: What is the use of the Tower of Hanoi in C?
That's why it is also called the Tower of Brahma puzzle. According to the monks, the world would end when the first disk came back. The temple priests used to pass these disks from one tower to another with traditional rules. This temple has three towers which are surrounded by sixty-four golden disks in the temple. This puzzle game is related to a religious temple of Hanoi, Vietnam, the name of the temple was the Tower of Hanoi. When you do solve it you'll be surprised to find out how simple, elegant and straightforward the solution is compared to imperative code.A French mathematician Édouard Lucas invented a game puzzle called Tower of Hanoi in 1883. This should give you enough insight to solve the Tower of Hanoi problem. The third stack (not source nor destination) is always the auxiliary stack. However, for the problem “moving disc n - 1 from A to B” the source is A but the destination is B. For the problem “moving disc n from A to C” the source was A and the destination was C. In addition, we need to make use of B which we call the auxiliary stack.Īn important thing to notice is that the source, destination and auxiliary stacks keep on changing. When solving the problem of moving disc n from A to C, we call A the source and C the destination. However, we want to talk about these stacks in terms of source, destination and auxiliary stacks. Now, we have three stacks labeled A, B and C.
By the principle of recursion, we have already solved these subproblems. How do we solve these subproblems? We don't have to. Move all the discs smaller than disc n from B to C.Move all the discs smaller than disc n from A to B.Our problem of moving all the discs from A to C has now been divided into two subproblems: Finally, we move the remaining discs from B to C. First, we move all the discs above disc n from A to B. We can solve our problem in three simple steps. Now, the only way we can move disc n from A to C is by first moving all the discs above it from A to B. Without this invariant, the solution would be trivial. Our job is to move all the discs from stack A to stack C while maintaining the invariant that a bigger disc may never be placed on top of a smaller disc. Given n discs, the smallest disc is labeled 1 and the largest disc is labeled n. I won't give you the solution outright, but I'll explain the intuition behind the solution. Tower of Hanoi is an inherently recursive problem and it has an elegant recursive solution.
HANOI TOWERS RECURSIVE FUNCTION CODE
The code for Hanoi is my attempt to turn my project from C++ into Scheme.Īny help is appreciated. 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. I'm getting an infinite loop since every time it gets used it takes the same value, thus not ever reducing the value. SumSublists returns how many disks there are in the game. (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum))) (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum))) (+ (length (car lst)) (sumSublists (cdr lst))) Here's an example of what I've got on my latest attempt. My professor said they were able to do it with about 6 helper functions.Īs mentioned, I have to solve the problem taking taking the list as the only parameter. 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. I've been ruminating on this for about a week now. I'd like to start off by saying this is homework so I'm not asking for a solution, just some tips.
0 kommentar(er)
