Поиск
 
 

Результаты :
 


Rechercher Расширенный поиск

Кто сейчас на форуме
Сейчас посетителей на форуме: 1, из них зарегистрированных: 0, скрытых: 0 и гостей: 1

Нет

[ Посмотреть весь список ]


Больше всего посетителей (9) здесь было Вс Фев 11, 2018 12:54 pm
Самые активные пользователи за неделю
Ярослав
 


Ханойские башни

Перейти вниз

Ханойские башни

Сообщение автор Gragory023 в Ср Мар 15, 2017 10:54 am

Что то не понятно, как делать эту задачку.
Начал сначала разбираться с рекурсией, но понял, что совершенно не усвоил(
Код:
unsigned long long fibonacci(int n) {
 if (n == 0)
 return 0;
 if (n == 1)
 return 1;
 return fibonacci(n - 1) + fibonacci(n - 2);

}
Вот к примеру берем число 5, те получается return fibonacci(4) + fibonacci(3), но а как дальше происходит?

Так же:
Код:
int f[20];
 
 f[0] = 0;
 f[1] = 1;
 for (int i = 2; i < 20; i++)
 f[i] = f[i - 1] + f[i - 2];
 for (int i = 0; i < 20; i++)
 cout << f[i] << ' ';
 cout << endl;
берем рассматривааем:
f(i0) = f(2-1)+f(2-2);
f(i0) = f(1)+f(0), отсюда следует f(i0) = 1
идем дальше:
f(i1) = f(3-1)+f(3-2);
f(i1) = f(2)+f(1), а тут непонятно почему получается 2 и тд.(((

Gragory023

Posts : 75
Join date : 2016-12-28

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 1:28 pm

Тут написано два разных способа вычислить числа Фибоначчи: рекурсивный и итеративный.

В рекурсивном:
fibonacci(4) = fibonacci(3) + fibonacci(2)
Компьютер не знает, чему равно fibonacci(3); чтобы вычислить его, он заходит в это функцию:
fibonacci(3) = fibonacci(2) + fibonacci(1)
Заходит ещё глубже:
fibonacci(2) = fibonacci(1) + fibonacci(0)
Заходит ещё глубже:
fibonacci(1) = 1, благодаря if в начале функции
Чтобы посчитать fibonacci(2), ему также нужно посчитать правую половину, то есть fibonacci(0):
fibonacci(0) = 0, благодаря if в начале функции
Наконец можно посчитать:
fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
Теперь возвращаемся на этап:
fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + fibonacci(2) = 2 + 1 = 3
и так далее
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 1:32 pm

В итеративном способе мы считаем по очереди все числа Фибоначчи и складируем их в массив:
Код:
f[0] = 0
f[1] = 1 // первые два числа Фибоначчи равны 0 и 1
Цикл начинается с 2. Так что первая операция выглядит как:
f[2] = f[1] + f[0]
f[1] и f[0] уже посчитаны и заполнены. Так что тут написано:
f[2] = 1 + 0 = 1

Затем переходим к i = 3:
f[3] = f[2] + f[1]
Вспоминаем, что f[2] только что посчитали, и f[2] = 1; f[1] = 1.
f[3] = 1 + 1 = 2

Затем
f[4] = f[3] + f[2] = 2 + 1 = 3
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Gragory023 в Ср Мар 15, 2017 2:15 pm

Это понятно,
по поводу задачки,
как я понял, надо рассматривать ее с конца, грубо говоря
для того чтоб переместить последний диск на третью башню, надо сначала переместить все кольцо без последнего на вторую башню, и только тогда переместить последнее кольцо, и соответственно так дальше.
Так же надо применить двумерный массив, и иметь условии в рекурсии для правильного перемещение (меньшее на большее)
Но кроме вот этого, ничего не лезет в голову(
Код:
#include <iostream>

using namespace std;

int const QUALITY = 3;
int const QUALITY_DISCS = 64;

using namespace std;

unsigned long long hanoe(int QUAlITY,int QUALITY_DISCS) {

   if (QUAlITY == 1)
      return 1;
   return

}


int main() {
   int tower[QUALITY][QUALITY_DISCS];
   for (int i=0;i<QUALITY;i++)
      for (int i = 0; i<QUALITY_DISCS; i++)


}


Gragory023

Posts : 75
Join date : 2016-12-28

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 2:22 pm

Я бы разбил эту задачу на несколько функций.

Одна из них самая базовая: как переместить 1 верхний диск с одного штырька на другой.

Другая функция отвечала бы за рисование текущей ситуации на экран.

Главная функция, решающая задачу переноса всех дисков, отвечала бы за такую операцию:
• Перенести стопочку из N верхних дисков с одного штырька (исхогдного) на другой (целевой), используя третий штырёк как вспомогательное пространство.

Именно эта функция была бы рекурсивной. Дело в том, что операция переноса N верхних дисков сводится в задаче переноса N-1 верхних дисков, используя несколько вспомогательных простых переносов 1 диска.
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Gragory023 в Ср Мар 15, 2017 2:35 pm

Это понятно, но как использовать несколько вспомогательных простых переносов( if, else)?

Gragory023

Posts : 75
Join date : 2016-12-28

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 2:52 pm

Как передвинуть башню высоты N с исходного стержня на целевой?
|654321
|
|

Нужно передвинуть башню из N-1 дисков на вспомогательный стержень (используя рекурсивный вызов):
|6
|54321
|

Затем передвинуть 1 диск с исходной позиции на целевую:
|
|54321
|6

Затем передвинуть башню из N-1 дисков со вспомогательного на целевой стержень (рекурсивно):
|
|
|654321

Если мы умеем решать задачу для N-1, то таким способом сможем решить и для N.

Понятно, что процесс закончится, потому что когда мы дойдём до задачи «передвинуть 1 диск с исходной позиции на целевую», мы не будем это делать рекурсивно: нужно просто взять и передвинуть его.
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 2:57 pm

Функция hanoe не должна ничего возвращать. Это не вычисляющая функция, а делающая; то есть void функция.

Она должна сделать некоторое количество перемещений дисков. После каждого перемещения она должна показывать текущую позицию, чтобы пользователь мог проконтролировать, что она работает как надо.
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Gragory023 в Ср Мар 15, 2017 3:08 pm

Как передвинуться башню в теории я понял, но как это запрограммировать совершенно не представляю, + еще выводить перестановку.
Вот используется двумерный массив, индексы это кол-во дисков и кол-во башен, дальше их надо переписывать с условием.

Gragory023

Posts : 75
Join date : 2016-12-28

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 3:13 pm

Можно начать с того, что попроще:

1) Заполнить массивы стартовыми значениями
2) Отобразить их на экране

1. Один из вариантов, что хранить в массиве — это размеры дисков, то есть числа от 1 до 64 (1 — самый маленький диск, 64 — самый большой). Либо 0, если место пустует. Стартовые значения должны быть такими:

64 63 62 61 .... 3 2 1 (первый стержень)
0 0 0 0 0 ... 0 0 0 (второй стержень — изначально пустой)
0 0 0 0 0 ... 0 0 0 (третий стержень — изначально пустой)

Это можно сделать циклом for.

2. Отображаются на экран они почти прямо как написано, единственное — нули заменяются пустым пространством:
| 64 63 62 61 ... 3 2 1
|
|
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Gragory023 в Ср Мар 15, 2017 3:28 pm

Теперь забыл видимо, как заполнять)))
Код:
for (int i = 0; i < QUALITY; i++)
      int tower[QUALITY][1] = i+1;
   for (int i = 0; i < QUALITY; i++)
      int tower[QUALITY][2] = 0;
   for (int i = 0; i < QUALITY; i++)
      int tower[QUALITY][3] = 0;
Вроде по логике так, но подчеркивает красным

Gragory023

Posts : 75
Join date : 2016-12-28

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Ярослав в Ср Мар 15, 2017 3:46 pm

Слово int в начале выражения:
int tower[...][...]
— это создание переменной. Конечно, он будет ругаться, если попытаться создать одну и ту же переменную четырежды.

Чтобы пользоваться уже имеющейся переменной-массивом, надо написать имя переменной и поставить квадратные скобки:
tower[?][?]

Прошу, перепроверь значения индексов. В каком диапазоне может лежать значение первого индекса? В каком диапазоне может лежать значение второго индекса? Что за формулы нужно в них написать?
avatar
Ярослав
Admin

Posts : 616
Join date : 2016-12-21
Location : Москва

Посмотреть профиль http://itstep.forum2x2.ru

Вернуться к началу Перейти вниз

Re: Ханойские башни

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения