Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

25.11.2013, 17:12. Просмотров 284. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2013, 17:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос это оптимальное решение? (C++):

Напишите код на это решение. Найти сумму ряда - C++
вот сама задача Оч срочно, нужно решить к четвергу.

как соединить b и с в число, если а это число, б это десятки перевернутого числа, с это единицы перевернутого числа вот в это строчке c=a+b,c; - C++
как соединить b и с в число, если а это число, б это десятки перевернутого числа, с это единицы перевернутого числа вот в это строчке...

Оптимальное значение массива - C++
Третий день уже бьюсь, всё никак не получается... :( Пришлось идти за помощью на форум. Суть в следующем. Имеются массивы r (длины...

Построить оптимальное префиксное алфавитное кодирование - C++
Построить оптимальное префиксное алфавитное кодирование для алфавита {a,b,c,d} со следующим распределением вероятностей появления букв...

Односвязный список: оптимальное удаление элемента - C++
оптимальный способ удаления из односвязное списка любого элемента списка?

Зачем биты нужны это меньше байтов но int 32 бита но я не допер зачем это нужно это 4 байта то есть int не может больше 4 байт весить? - C++
Вот еще один вопрос зачем биты нужны это меньше байтов но int 32 бита но я не допер зачем это нужно это 4 байта то есть int не может...

1
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
25.11.2013, 20:46 #2
Вот здесь - в картинках: Ханойская башня на пальцах
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2013, 20:46
Привет! Вот еще темы с ответами:

Какое оптимальное количество потоков необходимо выбирать? - C++
Здравствуйте! Необходимо написать программу, которая будет обрабатывать большие массивы информации. Вопрос: какое оптимальное число...

Самое оптимальное представление сложной кривой (функции) - C++
Есть сложная кривая f(t), необходимо найти и реализовать наиболее оптимальное её представление по следующим критериям: 1....

this это адресс объекта, а *this это сам объект. я всё правельно понял? - C++
this это адресс объекта, а *this это сам объект. я всё правельно понял?

Факториал! Для кого-то это легко, а кто-то вообще это не знает! - C++
Написать определение функции факториал которая возвращает факториал от полученного в качестве аргумента числа. Реализовать на С++ и...


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

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

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