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

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

Войти
Регистрация
Восстановить пароль
 
rodinjr
2 / 2 / 0
Регистрация: 29.12.2011
Сообщений: 39
#1

Ханойские башни - C++

16.01.2013, 01:46. Просмотров 842. Ответов 4
Метки нет (Все метки)

Ребята, помогите разобраться с алгоритмом, то что сначала перемещаются n-1 дисков на вспомогательный стержень, затем n-ый нижний диск на нужный стержень, а затем n-1 перемещенные изначально перемещаются на нужный стержень используя свободный в качестве вспомогательного, - это все понятно.
Вопрос в том, почему перемещение n-1 дисков идет согласно условию, что больший диск не может находиться выше меньшего, где это указано в коде?
P.S. Код взял из книги.
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
void rec(int, int, int, int);
int _tmain(int argc, _TCHAR* argv[])
{
    int n;
    cin >> n;
    rec(n,1,2,3);
    getch();
    return 0;
}
void rec(int n, int i, int j, int w)
{
    if(n>1)
    {
        rec(n-1,i,w,j);
        rec(1,i,j,w);
        rec(n-1,w,j,i);
    }
    else
        cout << i << "     " << j << endl;
    return;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2013, 01:46     Ханойские башни
Посмотрите здесь:

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

Ханойские башни - C++
Решил задачу о ханойских башнях рекурсивно: void HanBashR(int count, int start, int mid, int final){ if(count == 2){ cout &lt;&lt;...

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

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

Ханойские башни - C++
Уважаемые программисты. Срочно очень нужно рекурсивное решение задачи “Ханойские башни” на С# с графическим отображением. Может у...

Ханойские башни - C++
Легенда гласит,что где-то в Ханое находится храм,в котором размещеа следущая конструкция:на основании укреплены 3 алмазных стержня,на...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iifat
2225 / 1378 / 102
Регистрация: 05.06.2011
Сообщений: 3,799
16.01.2013, 02:40     Ханойские башни #2
Ну, что самый большой диск поверх меньших при таком способе не укладывается, ты понимаешь? Насчёт прочих -- доказывается по индукции.
rodinjr
2 / 2 / 0
Регистрация: 29.12.2011
Сообщений: 39
16.01.2013, 11:26  [ТС]     Ханойские башни #3
Меня интересует работа этой строки: rec(n-1, i, w, j); по сути она должна перенести все кроме нижнего диска, на ось w используя ось j как вспомогательную, если можно объясните принцип ее работы, как она соблюдает условие не класть больший поверх меньшего? не понятно совсем.
Потому что как я понимаю следующая строка:
rec(1, i, j, w); уже осуществляет перенос нижнего диска на j ось.
iifat
2225 / 1378 / 102
Регистрация: 05.06.2011
Сообщений: 3,799
17.01.2013, 04:37     Ханойские башни #4
Дык рекурсивно ж!
Вот смотри: мы как-то переместили n-1 дисков, не трогая n-й, потом переместили n-й, потом положили на него n-1. Самый большой диск никогда не ложится на меньший -- понятно? n-1 меньших перемещаются строкой rec(n-1, i, w, j) два раза, то бишь, n-1-й диск тоже никогда не ложится на меньший. И т.д. -- индукция.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2013, 00:37     Ханойские башни
Еще ссылки по теме:

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

Ханойские башни: демонстрация решения - C++
Добрый день! Требуется решить такую задачу Для начала, хотелось бы попросить помочь с созданием хотя бы прямоугольников в...

Ханойские башни, вывод решения по шагам - C++
Помогите мне пожалуйста!У меня есть готовый исходник решения этого алгоритма!Необходимо сделать вывод по шагам( с наглядным изображением...

Ханойские башни, объясните принцип работы! - C++
Можете мне &quot;расписать&quot; все что происходит в этом коде, плюс отдельные вопросы в &quot;комментариях&quot;, так что бы я сам смог это объяснить если...

Ханойские башни (нужна блок-схема) - C++
Помогите сделать блок-схему для игры Ханойские башни.

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


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

Или воспользуйтесь поиском по форуму:
rodinjr
2 / 2 / 0
Регистрация: 29.12.2011
Сообщений: 39
18.01.2013, 00:37  [ТС]     Ханойские башни #5
Получается функция rec(n-1, i, w, j) вызывается до тех пор, пока каждый из n-1 дисков не окажется на оси w?
Yandex
Объявления
18.01.2013, 00:37     Ханойские башни
Ответ Создать тему
Опции темы

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