Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 14.09.2013
Сообщений: 15
1

это оптимальное решение?

25.11.2013, 17:12. Просмотров 501. Ответов 1
Метки нет (Все метки)

Даны три стержня, на один из которых
нанизаны восемь колец, причем кольца
отличаются размером и лежат меньшее на
большем.
Задача состоит в том, чтобы перенести
пирамиду из N колец за наименьшее число
ходов.
За один раз разрешается переносить только
одно кольцо, причём нельзя класть большее
кольцо на меньшее.

Вот мой код:

C++ (Qt)
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
// HanoyTowers.cpp : Рекурсивное решение задачи о Ханойских башнях
 
#include "stdafx.h"
#include <windows.h>
#include <locale.h>
 
// Высота башен
const int kTowerSize = 6;
 
// Башни (массивы, содержащие номера дисков)
int tower1[kTowerSize] = {0};
int tower2[kTowerSize] = {0};
int tower3[kTowerSize] = {0};
int move = 0; //Количество ходов
 
 
void initTowers();  //Инициализация массивов
void printTowers(); //Печать башен на экране
void hanoy(int* from, int* to, int* stack, int size); //Решение задачи о башнях
int myPow(int base, int exp); //Возведение в степень (пример еще одной рекурсии)
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
    initTowers();
    printTowers();
    hanoy(tower1, tower3, tower2, kTowerSize);
    printf("Готово!\n");
    system("pause");
    return 0;
}
 
/*************************************
    Устанавливает начальные значения
    для башен и количества ходов
**************************************/
void initTowers()
{
    move = 0;
 
    //-------------------------------
    // Заполнение массивов начальными
    // значениями:
    //-------------------------------
    for (int i = 0; i < kTowerSize; ++i)
    {
        tower1[i] = kTowerSize - i;
        tower2[i] = 0;
        tower3[i] = 0;
    }
}
 
/*********************************************
    Печать одного этажа одной башни на экране. 
    Функция печатает номер диска или |, если 
    место пусто.
*********************************************/
void printDisc(int val)
{
    if (0 == val)
        printf(" | \t\t");
    else
        printf("%2d \t\t", val);
}
 
/*********************************************
    Печатает башни на экране.
        t1 - первая башня
        t2 - вторая башня
        t3 - третья башня
*********************************************/
void printTowers(int* t1, int* t2, int* t3)
{
    system("cls");
    printf("Решение задачи о Ханойских башнях высотой %d.\n", kTowerSize);
    printf("Минимально возможное количество пермещений: %d.\n\n\n", myPow(2, kTowerSize) - 1);
 
    for (int i = kTowerSize - 1; i >= 0; --i)
    {
        printf("   ");
        printDisc(t1[i]);       
        printDisc(t2[i]);
        printDisc(t3[i]);
        printf("\n");
    }
    printf("--------------------------------------\n");
    printf("Количество выполненных перемещений: %d\n\n", move);
    Sleep(100);
}
 
 
/*************************************************
    Уплотнение башни для вывода на экран. Функция 
    перемещает все ненулевые элемены вниз башни.
        original    - исходная башня
        compr       - уплотненная башня
*************************************************/
void compress(int* original, int* compr)
{
    int z = 0;
    for (int i = 0; (i + z) < kTowerSize; ++i)
    {
        compr[i] = original[i + z];
 
        while (i + z < kTowerSize && original[i + z] == 0)
        {
            compr[i] = original[i + ++z];
        }
    }
 
    for (int i = 0; i < z; ++i)
        compr[kTowerSize - i - 1] = 0;
 
 
}
 
/******************************************************
    Печать башен на экране.
    Данные для печати берутся из глобальных переменных.
******************************************************/
void printTowers()
{
    int ct1[kTowerSize];
    int ct2[kTowerSize];
    int ct3[kTowerSize];
 
    compress(tower1, ct1);
    compress(tower2, ct2);
    compress(tower3, ct3);
    printTowers(ct1, ct2, ct3);
}
 
 
/***********************************************
    Находит индекс верхнего диска в башне
    tower   - башня
    size    - высота башни (на текущем ходе)
 
    Возврат: индекс верхнего диска в башне
************************************************/
int findTopIndex(int* tower, int size)
{
    for (int i = size - 1; i >= 0; --i)
    {
        if (tower[i] != 0)
            return i;
    }
    return -1;
}
 
/************************************************
    Возвращает номер верхнего диска в башне
        tower   - башня
        size    - высота башни (на текущем ходе)
 
    Возвращает: номер верхнего диска в башне
************************************************/
int top(int* tower, int size)
{
    int idx = findTopIndex(tower, size);
    if (idx != -1)
        return tower[idx];
    return 0;
}
 
/*******************************************
    Снять диск с верха башни
        tower - башня
        size    - высота башни
 
    Возвращает номер верхнего диска в башне
*******************************************/
int pop(int* tower, int size)
{
    int idx = findTopIndex(tower, size);
    if (idx != -1)
    {
        int disc = tower[idx];
        tower[idx] = 0;
        return disc;
    }
    return 0;
}
 
/************************************
    Поместить диск в башню.
        tower   - башня
        disc    - номер диска
        size    - высота башни
************************************/
void push(int* tower, int disc, int size)
{
    int idx = findTopIndex(tower, size);
 
    if (idx < kTowerSize - 1)
    {
        tower[idx + 1] = disc;
    }
}
 
/***************************************************************************
    Решение задачи о башнях.
        from  - откуда перемещать диски
        to    - куда перемещать диски
        stack - какую из башен использовать в качестве временного хранилища
        size  - высота башни на текущем ходе
***************************************************************************/
void hanoy(int* from, int* to, int* stack, int size)
{
    //----------------
    // Базовый случай:
    //----------------
    if (size == 1)
    {
        //----------------------------------
        // Переместить элемент из from в to:
        //----------------------------------
        push(to, pop(from, size), size);
 
        //-------------------------------------------
        // Увеличить кол-во ходов и напечатать башни:
        //-------------------------------------------
        ++move;
        printTowers();
 
        //----------------------
        // Базовый случай решен!
        //----------------------
        return;
    }
 
    //-----------------------------
    // Переместить size-1 дисков на
    // запасную башню:
    //-----------------------------
    hanoy(from+1, stack+1, to+1, size-1);
 
    //-----------------------
    // Переместить один диск:
    //-----------------------
    hanoy(from, to, stack, 1);
 
    //------------------------------------
    // Переместить size-1 дисков c 
    // запасной башни на башню назначения:
    //------------------------------------
    hanoy(stack+1, to+1, from+1, size-1);
}
 
/********************************************************************
    Функция возведения в степень умножением. 
    Еще одна демонстрация использования рекурсии.
    
    f(base, exp) = 1, если exp = 1
    f(base, exp) = base^2 * f(base, exp/2), если exp > 0 и еxp четная
    f(base, exp) = base * f(base, exp-1), если exp > 0 и еxp нечетная
*********************************************************************/
int myPow(int base, int exp)
{
    if (0 == exp)
        return 1;
 
    if (exp % 2 == 0)
        return myPow(base*base, exp/2);
 
    return base * myPow(base, exp - 1);
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.11.2013, 17:12
Ответы с готовыми решениями:

Оптимальное решение задачи
Задача на картинке. Я придумал такое решение #include &lt;iostream&gt; #include &lt;windows.h&gt; #include...

Оптимальное решение?
Есть таблица: ************************************************************ * а здесь...

Оптимальное решение
Есть задачка: Требуется определить, сколько цифр N встречается в диапазоне между L числом ряда...

Оптимальное решение
Приветствую! И так для начала опишу основной принцип: 1. Будет реализовано ПО, которое...

1
3167 / 1926 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
25.11.2013, 20:46 2
Вот здесь - в картинках: Ханойская башня на пальцах
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.11.2013, 20:46

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Оптимальное решение по парсеру
Добрый день всем. Дело вот в чем задумал я сделать парсер контента, но перед тем как начать хотел...

Найти оптимальное решение
Поставлена задача, программно переводить предложение (каждый символ) в таблицу cp1251. То есть,...

Более оптимальное решение
Хочу сделать игру с реальной физикой космоса. У корабля есть двигатели, которые прилагают силу...

Оптимальное решение вывода из БД
Доброго времени суток! Помогите, кто может, решить такой вопрос... У меня в БД есть две таблицы...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.