/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
en/codes/cpp/chapter_divide_and_conquer/hanota.cpp
66 строк
2 KB
Yudong Jin
Translate all code to English (#1836)
31 дек 2025, 02:44
Не верифицирован
31 дек 2025, 02:44
2778a6f
Код
Авторство
О чём код?
/** * File: hanota.cpp * Created Time: 2023-07-17 * Author: krahets (krahets@163.com) */ #include "../utils/common.hpp" /* Move a disk */ void move(vector<int> &src, vector<int> &tar) { // Take out a disk from the top of src int pan = src.back(); src.pop_back(); // Place the disk on top of tar tar.push_back(pan); } /* Solve the Tower of Hanoi problem f(i) */ void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) { // If there is only one disk left in src, move it directly to tar if (i == 1) { move(src, tar); return; } // Subproblem f(i-1): move the top i-1 disks from src to buf using tar dfs(i - 1, src, tar, buf); // Subproblem f(1): move the remaining disk from src to tar move(src, tar); // Subproblem f(i-1): move the top i-1 disks from buf to tar using src dfs(i - 1, buf, src, tar); } /* Solve the Tower of Hanoi problem */ void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) { int n = A.size(); // Move the top n disks from A to C using B dfs(n, A, B, C); } /* Driver Code */ int main() { // The tail of the list is the top of the rod vector<int> A = {5, 4, 3, 2, 1}; vector<int> B = {}; vector<int> C = {}; cout << "Initial state:\n"; cout << "A ="; printVector(A); cout << "B ="; printVector(B); cout << "C ="; printVector(C); solveHanota(A, B, C); cout << "After disk movement:\n"; cout << "A ="; printVector(A); cout << "B ="; printVector(B); cout << "C ="; printVector(C); return 0; }