-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy path08_tower_of_hanoi_Recursion.cpp
140 lines (108 loc) · 4.83 KB
/
08_tower_of_hanoi_Recursion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/*
Topic - Tower of Hanoi (Recursion) | Classical Recursion Problem
Tower of Hanoi is a mathematical puzzle where we have three rods and N disks. The objective of the
puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another
stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.
Print all the steps for a given disk value N.
Eg: Input : 2
Output : Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C
Input : 3
Output : Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C
Explaination: Take an example for 2 disks :
Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.
Step 1 : Shift first disk from 'A' to 'B'.
Step 2 : Shift second disk from 'A' to 'C'.
Step 3 : Shift first disk from 'B' to 'C'.
Approach : Shift 'n-1' disks from 'A' to 'B'.
Shift last disk from 'A' to 'C'.
Shift 'n-1' disks from 'B' to 'C'.
*/
#include <iostream>
using namespace std;
// function to print all steps for moving N-disks from source-tower to destination-tower.
void move(int n, char src, char helper, char dest)
{
// base case
if(n == 0)
{
return;
}
// rec case
move(n-1, src, dest, helper);
cout << "Disk:" << n << " moved from " << src << " to " << dest << endl;
move(n-1, helper, src, dest);
return;
}
// function to drive code
int main()
{
int total_disks;
cout << "Enter disks: ";
cin >> total_disks;
cout << "Steps: \n";
move(total_disks, 'A','B','C');
return 0;
}
/*
OUTPUT:
Case 1:
Enter disks: 2
Steps:
Disk:1 moved from A to B
Disk:2 moved from A to C
Disk:1 moved from B to C
Case 2:
Enter disks: 3
Steps:
Disk:1 moved from A to C
Disk:2 moved from A to B
Disk:1 moved from C to B
Disk:3 moved from A to C
Disk:1 moved from B to A
Disk:2 moved from B to C
Disk:1 moved from A to C
APPROACH:
When disk = N
___ | | |
| -|- | |
n-1 | --|-- | |
_|_ ---|--- | |
last _|_ _----|----_ _____|_____ _____|_____
source helper destination
'A' 'B' 'C'
1. Shift 'n-1' disks from 'A' to 'B'.
| | |
| | ___ |
| -|- | |
___ | --|-- | n-1 |
last _|_ _----|----_ __---|---__ _|_ _____|_____
source helper destination
'A' 'B' 'C'
2. Shift last disk from 'A' to 'C'.
| | |
| | ___ |
| -|- | |
| --|-- | n-1 | ___
_____|_____ __---|---__ _|_ _----|----_ _|_ last
source helper destination
'A' 'B' 'C'
3. Shift 'n-1' disks from 'B' to 'C'.
| | | ___
| | -|- |
| | --|-- | n-1
| | ---|--- _|_
_____|_____ _____|_____ _----|----_ _|_ last
source helper destination
'A' 'B' 'C'
*/