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

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

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

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

16.01.2013, 01:46. Просмотров 818. Ответов 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++ Ханойские башни
Ханойские башни (нужна блок-схема) C++
Ханойские башни C++
Ханойские башни C++
C++ Ханойские башни
C++ Ханойские башни
C++ Ханойские башни: демонстрация решения
Ханойские башни, объясните принцип работы! C++
Ханойские башни C++
C++ Ханойские башни
C++ Ханойские башни
Ханойские башни C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iifat
2206 / 1359 / 101
Регистрация: 05.06.2011
Сообщений: 3,745
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
2206 / 1359 / 101
Регистрация: 05.06.2011
Сообщений: 3,745
17.01.2013, 04:37     Ханойские башни #4
Дык рекурсивно ж!
Вот смотри: мы как-то переместили n-1 дисков, не трогая n-й, потом переместили n-й, потом положили на него n-1. Самый большой диск никогда не ложится на меньший -- понятно? n-1 меньших перемещаются строкой rec(n-1, i, w, j) два раза, то бишь, n-1-й диск тоже никогда не ложится на меньший. И т.д. -- индукция.
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