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

Ханойские башни, объясните принцип работы! - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Нули между символами в строке http://www.cyberforum.ru/cpp-beginners/thread451548.html
Добрый вечер) Скорее всего нубский вопрос, однако поиском пользовался - ничего не нашел. Собственно суть: Из файла считываю строки: ifstream fs("C:\\test.txt"); string u; while (!fs.eof()) {...
C++ Реализовать команду md-создание каталога в Borland C++ Нужно сделать так, что бы по команде md (пример: md C:\CyberForum) создавалась определенная папка, название какой мы сами установим (принцип командной строки). Прошу помощи, ибо я уже запутался. http://www.cyberforum.ru/cpp-beginners/thread451546.html
C++ Задан массив A из N элементов...
Здравствуйте.помоги,пожалуйста,решить вот эти 2 задачи: 1.Задан массив A из N элементов. Составить программу, определяющую, содержится ли в нем один элемент, имеющий минимальное значение или таких...
C++ Группировка функций разных классов
Всем привет! Возник спорный вопрос. Задача: Есть много классов, но у каждого из них может быть (! а может и нет) по методу, например, следующий набор: fnc1, fnc2, fnc3. Программа должна вызвать...
C++ Вывод строк с двузначными числами, оформление в виде функции http://www.cyberforum.ru/cpp-beginners/thread451519.html
Написать программу, считывающую текст из файла и выводящую на экран строки, содержащие только двузначные числа. Оформить в виде функций законченные последовательности действий. Все необходимые...
C++ Попадает ли точка с заданными координатами в указанную область Нужно создать программу, которая проверяет принадлежность точки заштрихованной области. Помогите пожалуйста!!! подробнее

Показать сообщение отдельно
Mikola-BLR
47 / 47 / 7
Регистрация: 27.12.2011
Сообщений: 65
25.02.2012, 03:45
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны N колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из N колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Количество перекладываний в зависимости от количества колец вычисляется по формуле 2^n − 1 (т.е. большое число дисков не вводите, т.к. решение потребует кучу времени).
В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к не рекурсивным.
Рекурсия — процесс повторения чего-либо самоподобным способом (в данной программе функция hanoi_towers вызывает саму себя, вновь вызванная hanoi_towers вызывает саму себя и т.д.)
Тип void -пустой, т.к. hanoi_towers не возвращает в main никаких значений, она лишь печатает текст типа
1 -> 2
1 -> 3
2 -> 1
и т.д. Это наши ходы, показывающие с какого стержня на какой мы перекладываем диск.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()//отсюда начинается выполнение программы
{
        setlocale(LC_ALL,"rus");//вывод кириллицы не кракозябрами
        int start_peg, destination_peg, buffer_peg, plate_quantity;//Объявление переменных. Мы сообщаем, что будем использовать 4 переменных целочисленного типа. Под них выделяется память.
        cout << "Номер первого столбика:" << endl;
        cin  >> start_peg;//Инициализация переменной. С клавиатуры вводим значение и присваиваем его переменной start_peg (номер начального столбика)
        cout << "Номер конечного столбика:" << endl;
        cin  >> destination_peg;//С клавиатуры вводим значение и присваиваем его destination_peg
        cout << "Номер промежуточного столбика:" << endl;
        cin  >> buffer_peg;//С клавиатуры вводим значение и присваиваем его buffer_peg
        cout << "Количество дисков:" << endl;
        cin  >> plate_quantity;//С клавиатуры вводим значение и присваиваем его plate_quantity
 
        hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg); //вызываем функцию hanoi_towers и передаём ей параметры plate_quantity(Количество дисков), start_peg(Номер первого столбика), destination_peg(Номер конечного столбика), buffer_peg(Номер промежуточного столбика)
return 0;
Сама функция описана выше main(), но начинает работать лишь тогда, когда мы её вызвали из main()
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void hanoi_towers(int quantity, int from, int to, int buf_peg)/*мы только что из main() прислали сюда 4 переменных и в теле этой функции
новым переменным целочисленного типа quantity, from, to, buf_peg присваиваем присланные значения переменных
plate_quantity, start_peg, destination_peg, buffer_peg.
quantity(количество дисков), from(Номер первого столбика), to(номер последнего), buf_peg(номер среднего)*/
{                                                         
        if (quantity != 0)//пока кол-во дисков не равно 0
        {
                hanoi_towers(quantity-1, from, buf_peg, to);/*рекурсия, т.е. мы снова вызываем эту же функцию и передаём ей 4 переменных, но количество дисков уже уменьшаем на один.
                Чуть ниже второй вызов, но там, обратите внимание, переменные передаются в другом порядке, т.е. там мы перекладываем диски на другие столбцы*/
 
                cout << from << " -> " << to << endl;//выводим текстовое сообщение, которое нам показывает с какого на какой столбик мы переложили диск
 
                hanoi_towers(quantity-1, buf_peg, to, from);
        }
}
каким образом это все пишется в void
"Это всё", а точнее наши 4 значения переменных, которые мы пересылаем из функции в функцию и потихоньку меняем, в void не пишутся. Они "пишутся" в quantity, from, to, buf_peg, которые создаются каждый раз во вновь вызванной функции. void - это тип значения, которое возвращает сама функция hanoi_towers по завершении. Но она выводит только текст и ничего не возвращает, поэтому используется пустой тип void.
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru