Go to main page
A journey into the programming realm
The point of no return
Leaping into the unknown
Chapter warning
This chapter will contain some algorithms that are usually learned in school.
It is great if you're able to follow the problem and the solution, but if not, do not discourage yourself!
Algorithms are great for exposing you to different problem-solving techniques. However, you will not use them in your everyday programming, and if you actually do need one, you can always look them up on the internet.
Therefore, it's a good idea to read this chapter, but if you are stuck or simply get bored, feel free to go directly to Chapter 3 and come back later on.
Towers of Hanoi is a puzzle in which we have x rods and y disks. We need to place the entire stack of disks into another rod, while following the rules:
This puzzle is easily implemented through recursion. We need to have a stop point in the recursive function, when we are working with the latest disk from that stack.
In the function, we call the function again for the next disk in the stack, and thus we will keep calling this recursively until we reach the biggest disk. Since that is the stopping point, we can proceed with the next line in the function, in which we will recursively call the function, but this time we will move the disk to the destination stack.
Let’s proceed with an example, to be more clear.
Assuming we have 5 disks that needs to be moved from A to B:
Because we cannot move big disks on top of smaller ones, we need to use the temporary stack as auxiliary.
The first step is to move all disks except the last one, from A to C (destination for remaining disks), using B as a spare.
auxiliary position, we can move the biggest one to our destination.
Now that we have the biggest item in the destination, our purpose will be to move all but one item from source stack (C) to auxiliary stack (A), and then append that item to our destination stack (B)
int disks = 4;
int point_start = 0;
int point_aux = 1;
int point_end = 2;
void towerOfHanoi(int n, int from, int to, int aux) {
if (n == 1) return;
towerOfHanoi(n - 1, from, aux, to);
towerOfHanoi(n - 1, aux, to, from);
}
int main() {
towerOfHanoi(disks, point_start, point_end, point_aux);
return 0;
}
The code is short, but there’s a lot of recursion going on.
We have a few constants (Lines 1-4) defined for our code:
The first function called will be main(), in line 14, which simply calls our algorithm.
The algorithm is called with n = 4 (our disks), from = point_start, to = point_end, aux = point_aux (Line 7).
Line 8 handles the recursion, which exits if we are working with disk 1. We’ll see why later.
The algorithm is implemented with two lines (10-11) – with the help of recursion.
Let’s try to make this simple, by using the following terms:
Let’s take the situation for number of disks = 2. Please follow the code as you follow the steps.
We will call this situation 1.
Let’s take the situation for number of disks = 3. Please follow the code as you follow the steps.
We will call this situation 2.
We see that we can simplify this expression as follows:
Situation 2:
Based on this, we will have the following logic for 4 disks:
Vertex: Node containing data
Edge: The line that connects two vertices
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Cycle: Cycles occur when nodes are connected in a way that they forms a closed structure.
Self loop: An edge that connects a vertex to itself (source = destination).
Divide et impera (Divide and conquer): Break the problem into sub-problems and solve them each recursively.
Negative weight edge refer to edges with a negative cost.