summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--introductory_problems/readme.md8
-rw-r--r--introductory_problems/tower_of_hanoi.cpp21
2 files changed, 29 insertions, 0 deletions
diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md
index 8d11138..52a1f51 100644
--- a/introductory_problems/readme.md
+++ b/introductory_problems/readme.md
@@ -104,3 +104,11 @@ There are 88418 paths in a 7 * 7 grid from the upper-left square to the lower-le
**Input**: The only input line has a 48-character string of characters ?, D, U, L, and R. (Example: ??????R??????U??????????????????????????LD????D?)
**Output**: Print one integer: the total number of paths. (Example: 201)
+
+### Tower of Hanoi
+The Tower of Hanoi game consists of three stacks (left, middle, and right) and `n` round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.
+The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk. Your task is to find a solution that minimises the number of moves.
+
+**Input**: The only input line has an integer `n`: the number of disks. (Example: 2)
+
+**Output**: First print an integer `k`: the minimum number of moves. After this, print `k` lines that describe the moves. Each line has two integers `a` and `b`: you move a distk from stack `a` to stack `b`. (Example: 3 12 13 23)
diff --git a/introductory_problems/tower_of_hanoi.cpp b/introductory_problems/tower_of_hanoi.cpp
new file mode 100644
index 0000000..806fc51
--- /dev/null
+++ b/introductory_problems/tower_of_hanoi.cpp
@@ -0,0 +1,21 @@
+// 2165. Tower of Hanoi
+#include <bits/stdc++.h>
+using namespace std;
+
+void move(int from, int to, int depth) {
+ if (depth == 1) {
+ printf("%d %d\n", from, to);
+ return;
+ }
+ int other = 6 - from - to;
+ move(from, other, depth - 1);
+ printf("%d %d\n", from, to);
+ move(other, to, depth - 1);
+}
+
+int main() {
+ static int n;
+ scanf("%d", &n);
+ printf("%d\n", (1 << n) - 1);
+ move(1, 3, n);
+}