Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
1 / 1 / 0
Регистрация: 22.12.2020
Сообщений: 28

Автоматизация задачи "Ханойские башни"

22.04.2022, 19:48. Показов 1306. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
C++
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
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <vector>
#include <cmath>
#include <windows.h>
 
using namespace std;
 
struct SDisk {
    int size;
    int color;
};
 
void gotoxy(int x, int y)
{
    COORD c = { x, y };
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), c);
}
 
void showTower(vector <SDisk> tower) {
    for (int i = 0; i < tower.size(); i++) {
        cout << tower[i].size << " ";
    }
    cout << endl;
}
 
void setColor(int background, int text) {
    HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hStdOut, (WORD)((background << 4) | text));
}
 
enum COlnsoleColor {
    BLACK = 0,
    BLUE = 1,
    GREEN = 2,
    CYAN = 3,
    RED = 4,
    MAGENTA = 5,
    BROWN = 6,
    LIGHT_GRAY = 7,
    DARKGRAY = 8,
    LIGHT_BLUE = 9,
    LIGHT_GREEN = 10,
    LIGHT_CYAN = 11,
    LIGHT_RED = 12,
    LIGHT_MAGENTA = 13,
    YELLOW = 14,
    WHITE = 15
}
;
 
void showDisk(SDisk disk, int x, int y) {
    gotoxy(x, y);
    setColor(BLACK, disk.color);
    for (int i = 0; i < disk.size; i++) {
        cout << (char)219;
    }
    setColor(BLACK, WHITE);
}
 
void showTowers(vector <vector<SDisk>> towers, int px, int py, int sx) {
 
    int x = px;
    int y = py;
 
    gotoxy(x, y);
 
    for (int i = 0; i < towers.size(); i++) {
        for (int j = 0; j < towers[i].size(); j++) {
            
            showDisk(towers[i][j], x, y);
            y--;
        }
        y = py;
        x = x + sx;
    }
}
 
 
int main(int argc, char* argv[]) {
    //system("chcp 1251 > nul");
 
    vector <SDisk> tower0;
    vector <SDisk> tower1;
    vector <SDisk> tower2;
 
    const int N = 3;
 
    vector <vector <SDisk>> towers;
 
    SDisk disk;
 
    disk.size = 10;
    disk.color = BROWN;
 
    tower0.push_back(disk);
    tower1.push_back(disk);
    tower2.push_back(disk);
 
    for (int i = N; i >= 1; i--) {
 
        disk.size = i;
        disk.color = 1 + rand() % 5;
        tower0.push_back(disk);
    }
 
    towers.push_back(tower0);
    towers.push_back(tower1);
    towers.push_back(tower2);
 
    int source = 0;
    int destination = 0;
 
    SDisk disk0;
    SDisk disk1;
    while (true) {
 
        system("cls");
        showTowers(towers, 45, 10, 11); //45 10 11
        gotoxy(0, 15); //15
 
        cout << "FROM: ";
        cin >> source;
        cout << "TO: ";
        cin >> destination;
 
        source--;
        destination--;
 
        disk0 = towers[source][towers[source].size() - 1];
        disk1 = towers[destination][towers[destination].size() - 1];
 
        if (disk0.size < disk1.size) {
            towers[source].pop_back();
            towers[destination].push_back(disk0);
        }
        else cout << " --> ERROR <-- " << endl;
        
        if (towers[2].size() == static_cast<unsigned long long>(N) + 1) {
            cout << " --> WIN <--" << endl;
            system("cls");
            showTowers(towers, 45, 10, 11);
            break;
        }
 
    }
    showTowers(towers, 45, 10, 11);
    gotoxy(53, 12);
    setColor(BLACK, CYAN);
    cout << "Game over: win!" << endl;
    setColor(BLACK, WHITE);
    return 0;
}
Есть код, визуализирующий процесс решения задачи о Ханойских Башнях. Не получается "автоматизировать" процесс решения с выводом башен на каждый шаг, выводятся башни с дисками, не соответствующие данному шагу. Как это корректно сделать?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.04.2022, 19:48
Ответы с готовыми решениями:

Реализовать алгоритм решения задачи «Ханойские башни»
задание: Реализовать алгоритм для решения задачи «Ханойские башни». Выписать последовательность ходов для перекладывания n дисков башни...

Ханойские башни
Кто-то из вас может решить адачу о ханойских башнях на си++ рекурсивным способом, а тоя никак не могу догнат что в даное задаче является...

Ханойские башни
Ханойские башни. Алгоритм я приблизительно понимаю, но программу написать не могу... Мне не нужно решение, просто скажите, может лучше...

12
place status here
 Аватар для gunslinger
3190 / 2227 / 640
Регистрация: 20.07.2013
Сообщений: 6,023
22.04.2022, 23:28
Посмотри здесь (билдер): Ханойские башни.
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,279
26.04.2022, 15:04
Делаю на Qt, без рекурсии. Пока не сделал.
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,279
28.04.2022, 06:43
Вот так получилось:
Миниатюры
Автоматизация задачи "Ханойские башни"  
1
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
01.05.2022, 22:54
Цитата Сообщение от alexu_007 Посмотреть сообщение
Вот так получилось:
Вот так получилось

Qt 5.15, GUI на QML. Тоже без рекурсии.
Умеет ходить на один шаг вперед/назад.
Умеет автоматически идти вперед с анимацией.
Скорость анимации можно менять.
Умеет перемещаться в заданную позицию.
Вообще, идея была сделать итератор (hanoi_iterator), но встала проблема какой он должен быть категории.
Передумал, сделал просто класс для логики и всё, без всяких итераторов.
2
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,279
01.05.2022, 23:04
Цитата Сообщение от Croessmah Посмотреть сообщение
Тоже без рекурсии.
А без рекурсии - это с заменой рекурсии на стек?
0
place status here
 Аватар для gunslinger
3190 / 2227 / 640
Регистрация: 20.07.2013
Сообщений: 6,023
01.05.2022, 23:15
Вроде как не обязательно:
через стек - https://habr.com/ru/post/318964/
через "степенью двойки" (насколько я понял) - http://upbyte.net/news/khanojs... -04-26-170
0
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
01.05.2022, 23:27
Цитата Сообщение от alexu_007 Посмотреть сообщение
А без рекурсии - это с заменой рекурсии на стек?
Нет. Вики: Ханойская башня

Циклическое решение
Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3.
Добавлено через 8 минут
alexu_007, если интересно: https://github.com/croessmah/TowerOfHanoi
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.05.2022, 23:29
С рекурсией тоже тривиально сделать хождение вперед-назад и к заданному шагу А с учетом экспоненциального роста количества шагов от количества колец, никакого стековерфлоу не будет до конца жизни вселенной, как в Фибоначчах.
1
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
02.05.2022, 00:02
Цитата Сообщение от _Ivana Посмотреть сообщение
С рекурсией тоже тривиально сделать хождение вперед-назад и к заданному шагу
Там еще головой надо думать. Фу.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.05.2022, 00:21
Можно и головой, с разделением по потокам и их взаимодействием. А можно и тупо, в одном потоке и на глобальных мутабельных флагах, типа такого
C++
1
2
3
4
5
6
7
8
9
void f(int n) {
    if (n>=0 && n<=10) {
        std::cout << n << "\n";
        int d; std::cin >> d; f(n+d);
    } else
        std::cout << "Game over!";
}
 
int main() { f(0); }
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,279
02.05.2022, 07:13
Цитата Сообщение от Croessmah Посмотреть сообщение
чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3
А назад возвращать диски?

Я взял алгоритм отсюда: http://algolist.manual.ru/maths/combinat/hanoi.php

1. Определяем число дисков, откyда находим как бyдет перемещаться наименьший диск
(данный шаг делается в начале, притом один раз).
2. Смотрим номер хода: если нечетный - переносим наименьший диск в направлении, определенном в п.1.
если четный - то возможный ход один единственный - берем наименьший из двyх верхних дисков
и переносим его.
Пришлось написать три "функции":

1. Находит диск №1 и переносит по схеме - нечетные ходы
2. Находит наименьший диск больше 1.
3. Находит "единственно возможный ход" и делает его - четные ходы.
0
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
03.05.2022, 00:27
Цитата Сообщение от alexu_007 Посмотреть сообщение
А назад возвращать диски?
Ну мы же остановились в каком-то месте в этой последовательности.
Просто идем в обратном порядке по ней, точно с теми же правилам.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
03.05.2022, 00:27
Помогаю со студенческими работами здесь

Ханойские башни
Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков ...

Ханойские башни
У Дейтлов есть задача: Не могу до конца сформулировать алгоритм. Предположим, я беру 3 колышка и 4 диска int k1, k2, k3;...

Ханойские башни
Головоломка «Ханойские башни» состоит из трёх стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков...

Ханойские башни
Ребята, помогите разобраться с алгоритмом, то что сначала перемещаются n-1 дисков на вспомогательный стержень, затем n-ый нижний диск на...

Ханойские башни
Не могу понять где ошибка,проверяла на 3 монетках ,разного достоинства, наложенных друг на друга,на основе этого и составляла код.но...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru