Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Праздник
0 / 0 / 0
Регистрация: 14.09.2013
Сообщений: 15
#1

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

25.11.2013, 17:12. Просмотров 267. Ответов 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);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2013, 17:12     это оптимальное решение?
Посмотрите здесь:

C++ Оптимальное значение массива
this это адресс объекта, а *this это сам объект. я всё правельно понял? C++
Возможно ли это на с++? C++
C++ Оптимальное заполнение или "Халява"
Есть ли это на c++? C++
Односвязный список: оптимальное удаление элемента C++
Факториал! Для кого-то это легко, а кто-то вообще это не знает! C++
C++ Напишите код на это решение. Найти сумму ряда
C++ Самое оптимальное представление сложной кривой (функции)
Построить оптимальное префиксное алфавитное кодирование C++
C++ Какое оптимальное количество потоков необходимо выбирать?
Преобразовать решение (дано решение без указателей) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
3130 / 1905 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
25.11.2013, 20:46     это оптимальное решение? #2
Вот здесь - в картинках: Ханойская башня на пальцах
Yandex
Объявления
25.11.2013, 20:46     это оптимальное решение?
Ответ Создать тему
Опции темы

Текущее время: 05:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru