ниже пишут, что школьная задача :), да для 4го десятка это хорошая и интересная задачка, чтобы мозги растормошить )). в уме уже трудновато представить )) все решение
Вроде бы и понятно описание задачи на высоком уровне, но как это блять работает никак не могу представить. Будто у функции есть мозг, и он все сам делает
Для Ханойской башни я предлагаю простое и мнемоническое решение. Правило следующее: - перемещать наименьший диск по кругу, по часовой стрелке двумя различными способами: - Even для четных дисков (2, 4, 6, 8…): a -> b -> c -> a ->… ˗ для нечетных дисков (1, 3, 5, 7, 9…): a -> c -> b -> a ... - переместите меньший диск, из двух влево, на основной, это единственно возможная операция, - в следующем шаге переместите меньший диск снова по кругу, как показано выше - следующим ходом перемещайте диск единственным возможным способом ... и так далее, пока не будут доставлены все диски от начальной ставки "а" до конечной целевой ставки "с". Я надеюсь, что я был ясен, спасибо за ваше внимание и наслаждайтесь.
Блин.Вот компьбтерные игры - это. Дима фанат игрушек! Надо будет записать в список сделать игрушку ХАнойская Башня. Я как то послднее времяч на Фри Паскле, и Паскаль АБВ. И также вот КуБэйсике64.
Уважаемый Тимофей, подскажите, возможна ли реализация на Пайтон без того чтобы вписывать в функцию три переменные (hanoi(n, i, k, tmp)) ? То есть, только через n, i и k, как в вашем примере на Си? Спасибо!
Все классно, единственное не понятно откуда формула взялась каким образом мы пришли к сумме номеров столбцов)))это прям вообще не очевидно как апельсины с мандаринами сложить и вывести формулу, можно какое то теоретическое обоснование?)))
Здравствуйте,помогите пожалуйста разобраться. Переписал прогу и запустил, все работат. Но я по коду не мооу понять. Почему по дебагу прога, когда выпоняется попадая на первый вызов hanoi( n-1, i, tmp) идет с новым пораметрами снова сверху до проверки n==1, а если это условие выполнятся из функции не выходит,а начинает исполнять код со второго printf ну и дальше аналогично по кругу, в итоге даже не порятно условие выхода из функции hanoi, если финальные значерия переменных 1,1,2 и tmp1. Помогите разобраться, пожалуйста.
Да то что это номера штырьков понятно. Не понятно как "пришли" к формуле i + k + tmp = 6. То что, это 1 + 2 + 3 понятно, то есть для конкретной задачи. Как эту формулу "увидели" изначально, когда в самый первый раз решали её на компьютере, вот что непонятно. Очевидно, что для 4-х штырьков это будет 1 + 2 + 3 + 4 = 10. Формула тогда i + k + p + tmp = 10 и tmp = 10 - i - k - p.
Всё это постепенно становится понятно. Но вот у меня другая проблема. При первом пробеге в рекурсии hanoi(n-1, i, tmp) Выходит так: hanoi(2, 1, 3) Далее идёт printf("move disc %d from %d to %d", n, i, k) , который должен был показать, что первым мы берём второй блинчик?? Ведь n теперь 2. Но программа прекрасно работает, и берёт первый. Как это понять?
@@vladimirvladimir199 ну ведь перед тем, как вывести это на экран, мы же вызываем опять эту функцию hanoi(n-1, i, tmp), получается, мы заходим внутрь ещё раз и так рекурсивно, пока не дойдём до n == 1. Вот тогда и первый раз в программа в консоль выведет наш printf, в котором n = 1. А потом, обратно, выходя в обратном порядке из функций, у нас будет выводится по очереди ответ. Таков алгоритм.
Спасибо за объяснение, не уверен, откуда взялось 1 + 2 + 3 = 6. То есть разве 1, 2 и 3 это не просто нумерация стержней, точно такая же как если бы a, b и с или 2 стержень 10 стержень и стержень x ? Буду благодарен если кто-то пояснит! Спасибо
Насколько я понял (как математик, но не программист), автор хотел сделать обобщенное решение для 3-х стержней и n дисков. Т.е. чтобы было не важно, где была бы изначальная позиция башни и не важно где была бы конечная позиция башни. На рисунке в начале стержни пронумерованы 1, 2, 3 по порядку слева-направо. Это значит, что если начальная позиция (буква i) в задаче допустим находится на стержне №3, а конечная позиция (буква k) допустим на стержне №1, то очевидно что промежуточная позиция в такой конкретной задаче находится в позиции №2, т.е. temp = 2 (а это в том числе подчиняется формуле temp = 6 - i - k). И как бы мы не расположили начальную и конечную позицию башни (т.е. какие бы значения номеров стержней не приняли бы буквы i и k), промежуточная позиция temp всегда окажется под оставшимся единственным номером, который вычисляется по формуле temp = 6 - i - k. Обобщенная задача (общая задача) в математике нужна, чтобы всегда иметь решение для конкретных вводных начальных данных. В данной ситуации вводные начальные данные - это расположение начальной и конечной позиции башни на 3-х стержнях (оно может быть любое, кстати вариантов таких выборов - 6, это обычный расчет комбинаторной задачи), ну и еще начальные данные - это количество дисков в башне (но это уже вопрос про n дисков и наличие рекурсии). Так вот, если закрепить за начальной и конечной позициями башни какие-то конкретные номера стержней из этих 6 комбинаторных вариантов, то мы решим всего-навсего одну задачу. И программа будет выдавать всегда один и тот же ответ. А хочется, чтобы начальная позиция была произвольная среди этих 6 возможных вариантов. Тогда надо начальную и конечную позиции задать не конкретными номерами стержней, а буквами i и k, которые могут принять любое значение среди 1,2,3 (ну естественно что за исключением варианта i=k), тогда временный стержень будет последним оставшимся из 3-х стержней (его позиция должна быть занумерована, а сделать это можно с помощью формулы temp = 6 - i - k)
у тебя всего 3 столбца сумма их порядковых номеров равна 6 (1 + 2 + 3) переменные i, k, tmp как раз таки и являются порядковыми номерами столбцов, а значит i + k + tmp = 6 i и k передаются в функцию аргументами, соответственно мы сможем легко найти порядковый номер временного столбца следующим образом: tmp = 6 - i - k
Всё равно не понял. Как программа может сам понять что не надо ставить диск большего диаметра на меньшую? И как оно перемещает диски вообще по разному а в программе только 2 команды?
Только сейчас узнаю, что это никакая не легенда, а задача, придуманная математиком. Сегодня для меня в мире стало немного меньше красоты. Жалко. А решение прекрасное - спасибо!
@@kosiak10851 ну надо дальше размышлять, чем на один шаг. Если вы к этому относитесь серьезно, значит у этого для вас также должна быть причина. Почему бог завещал конец света и т.п.?Почему богу мы вообще понадобились? Нету ли тут какой-нибудь мнительности на свой человеческий счет? Когда-то люди считали что солнце и луна вращаются вокруг земли.
@@mitri9240 не в саму легенду о наступлении конца света в момент перекладывания последнего колечка, а в существование такой легенды у одного из народов.
@@kosiak10851 у людей не было причин считать, что они являются центром чего-то. Это просто психология. Аристотель подверг сомнению, то что мы находимся на диске, хотя мог отнестись к этому как к данному. Были разные теории, в том числе те, что считали возможным и то, что начало системы координат находиться не у нас под ногами. А что касается реакции церкви она не только сейчас бугуртит на всё подряд, имя Джордано Бруно вам о чем-нибудь говорит? В целом религия пропитана необоснованной эгоцентричностью человечечества. Отрицать это, если вы прочитали Библию, просто глупо. Если человек ученый то все на свете он будет ставить под сомнение, не просто с головы брать толкование всего, а нелогичность будет его раздражать. Взять вот аксиомы в геометрии, никто не говорит что они верные, хотя православные любят утверждать, что математики принимают их на веру, но тогда бы не появлялось неевклидовой геометрии, по типу геометрии Лобачевского. Он поставил под сомнение аксиому, и показал, что если взять те аксиомы выйдет вот так. Взять другие выйдет по другому, но они не являются опорой, они лишь условие задачи. Мы верим в аксиому когда решаем задачу которая в условии утверждает, что эти аксиомы являются верными. Простой пример: находясь на шаре, выбрать кратчайшим путем, между двумя точками, прямую будет попросту неверно, самолёты тратили бы лишнее топливо при перелёте через океан если бы полагались на аксиомы сформулированные Евклидом для плоскости.
Ахаххахах, вспомнила как у меня была довольно простая ошибка в коде, gpt-4 говорил что ошибки нет и все должно работать правильно, но не работало... Самой пришлось додумываться, так что пока ещё ИИ не может заменить эти лекции, так ещё и постоянно выдаёт неправильную инфу под видом правильной
Очередное видео которое просто ставит перед фактом, что задачу нужно начинать с конца и перекладывать n-1 дисков без объяснения как к такому решению пришли. В чём полезность? :(
Неужели нельзя было снять так, чтобы было без этого вот "ой, я сам толком не понимаю, надо вот так, а, нет, это неправильно, надо не вот так а вот эдак, а, хотя нет, подождите"? Только ещё больше запутал. >:(
#include // Функция показывает движение from -> to void move(int to, int from) { printf("%i -> %i ", to, from); } // печатает решение для головоломки размера n, // сдвигая n дисков из колонны "from" // в колонну "to" void hanoi(int n, int to, int from) { if (n == 1) move(to, from); else { int tmp = 6 - to - from; hanoi(n - 1, from, tmp); move(from, to); hanoi(n - 1, tmp, to); } } int main(void) { int n; printf("Insert n: "); scanf("%i", &n);
все таки классные преподаватели получаются из выпускников МФТИ!!
@@kosiak10851 по твоему ответу понятно, что ты сам не далеко ушел от 9го класса!
Господь сам спустился и начал заливать туториалы на Ютуб! Спасибо огромное, столько всего смотрел и только сейчас сумел понять!
Тимофей Фёдорович, огромное Вам спасибо!
Не думал, что написание кода в Си может быть так увлекательно =)
Я наконец понял рекурсию. Спасибо вам, Тимофей, вы лучший!
Вы очень приятный человек :)
Огромное спасибо за столь подробное и чёткое объяснение!
Спасибо, очень интересно и познавательно
Вы лучший! Благодарю)
Круто, спасибо! Очень познавательно и интересно.
Спасибо! Все стало полностью понятно!
Восхитительно, спасибо.
Всё таки стоит сформулировать задачу, стоящую перед программистом: требуется напечатать инструкцию для перекладывающего.
Лучший учитель которого я знаю!
Видно что любит свою работу))
Спасибо за объяснение
Шикарно, спасибо.
Не пойму, за счет чего в данном алгоритме обеспечивается условие "не класть больший диск на меньший", если при перемещении это нигде не обрабатывается
Это магия какая-то, а не программирование
В голове так и не смог прокрутить. Рекурсия там, где она реально необходима слишком сложна для меня
Математика - это от Бога)) просто класс
приперся с питона, где не успели на лекции разобрать эту задачу...
я тоже)
и я)
Спасибо большое!!!
Чем дальше видео в плей-листе, тем меньше просмотров)) Спасибо, Тимофей, за труды!
Учёба и усилие над собов , всем в тягость))) так на любом образовательном канал, чем дальше, тем меньше просмотров. Мотивация слабеет)))
@@user-rn1xs5ne1h это да
Очень интересно
Гениально!!!
ниже пишут, что школьная задача :), да для 4го десятка это хорошая и интересная задачка, чтобы мозги растормошить )). в уме уже трудновато представить )) все решение
Вроде бы и понятно описание задачи на высоком уровне, но как это блять работает никак не могу представить. Будто у функции есть мозг, и он все сам делает
@@manuchehrml3315 соболезную
спасибо огромное
Для Ханойской башни я предлагаю простое и мнемоническое решение. Правило следующее:
- перемещать наименьший диск по кругу, по часовой стрелке двумя различными способами:
- Even для четных дисков (2, 4, 6, 8…): a -> b -> c -> a ->…
˗ для нечетных дисков (1, 3, 5, 7, 9…): a -> c -> b -> a ...
- переместите меньший диск, из двух влево, на основной, это единственно возможная операция,
- в следующем шаге переместите меньший диск снова по кругу, как показано выше
- следующим ходом перемещайте диск единственным возможным способом ...
и так далее, пока не будут доставлены все диски от начальной ставки "а" до конечной целевой ставки "с".
Я надеюсь, что я был ясен, спасибо за ваше внимание и наслаждайтесь.
Спасибо!
супер!
Супер
Тимофей, дайте видео как это сделать списками, или массивом чисел...спс
Блин.Вот компьбтерные игры - это. Дима фанат игрушек! Надо будет записать в список сделать игрушку ХАнойская Башня. Я как то послднее времяч на Фри Паскле, и Паскаль АБВ. И также вот КуБэйсике64.
Уважаемый Тимофей, подскажите, возможна ли реализация на Пайтон без того чтобы вписывать в функцию три переменные (hanoi(n, i, k, tmp)) ? То есть, только через n, i и k, как в вашем примере на Си? Спасибо!
tmp = 6-i-k
Все классно, единственное не понятно откуда формула взялась каким образом мы пришли к сумме номеров столбцов)))это прям вообще не очевидно как апельсины с мандаринами сложить и вывести формулу, можно какое то теоретическое обоснование?)))
Круто , я ведь так пасьянс косынку расскладываю))) теперь надо запомнить как это кодом записать.А ханойская башня , Это косынка.
перепутал ,пасьянс паук
"рекурентный случай" - это тоже самое что рекурсия?
👍👍👍
Magic!😂
👍
Здравствуйте,помогите пожалуйста разобраться. Переписал прогу и запустил, все работат. Но я по коду не мооу понять. Почему по дебагу прога, когда выпоняется попадая на первый вызов hanoi( n-1, i, tmp) идет с новым пораметрами снова сверху до проверки n==1, а если это условие выполнятся из функции не выходит,а начинает исполнять код со второго printf ну и дальше аналогично по кругу, в итоге даже не порятно условие выхода из функции hanoi, если финальные значерия переменных 1,1,2 и tmp1. Помогите разобраться, пожалуйста.
6:25 Народ если что i k tmp это просто номера штырьков. Я полчаса думал откуда эта 6 взялась =)
Да то что это номера штырьков понятно. Не понятно как "пришли" к формуле i + k + tmp = 6. То что, это 1 + 2 + 3 понятно, то есть для конкретной задачи. Как эту формулу "увидели" изначально, когда в самый первый раз решали её на компьютере, вот что непонятно.
Очевидно, что для 4-х штырьков это будет 1 + 2 + 3 + 4 = 10. Формула тогда i + k + p + tmp = 10 и tmp = 10 - i - k - p.
Всё это постепенно становится понятно.
Но вот у меня другая проблема. При первом пробеге в рекурсии
hanoi(n-1, i, tmp)
Выходит так:
hanoi(2, 1, 3)
Далее идёт
printf("move disc %d from %d to %d", n, i, k) , который должен был показать, что первым мы берём второй блинчик?? Ведь n теперь 2.
Но программа прекрасно работает, и берёт первый. Как это понять?
@@vladimirvladimir199 ну ведь перед тем, как вывести это на экран, мы же вызываем опять эту функцию hanoi(n-1, i, tmp), получается, мы заходим внутрь ещё раз и так рекурсивно, пока не дойдём до n == 1. Вот тогда и первый раз в программа в консоль выведет наш printf, в котором n = 1. А потом, обратно, выходя в обратном порядке из функций, у нас будет выводится по очереди ответ. Таков алгоритм.
@@Stevend1 да, спустя время, начинаю понимать) спасибо за ответ)
@@Stevend1 но в голове всю эту последовательность сложно представлять😃
Спасибо за объяснение, не уверен, откуда взялось 1 + 2 + 3 = 6. То есть разве 1, 2 и 3 это не просто нумерация стержней, точно такая же как если бы a, b и с или 2 стержень 10 стержень и стержень x ? Буду благодарен если кто-то пояснит! Спасибо
Насколько я понял (как математик, но не программист), автор хотел сделать обобщенное решение для 3-х стержней и n дисков. Т.е. чтобы было не важно, где была бы изначальная позиция башни и не важно где была бы конечная позиция башни. На рисунке в начале стержни пронумерованы 1, 2, 3 по порядку слева-направо. Это значит, что если начальная позиция (буква i) в задаче допустим находится на стержне №3, а конечная позиция (буква k) допустим на стержне №1, то очевидно что промежуточная позиция в такой конкретной задаче находится в позиции №2, т.е. temp = 2 (а это в том числе подчиняется формуле temp = 6 - i - k). И как бы мы не расположили начальную и конечную позицию башни (т.е. какие бы значения номеров стержней не приняли бы буквы i и k), промежуточная позиция temp всегда окажется под оставшимся единственным номером, который вычисляется по формуле temp = 6 - i - k. Обобщенная задача (общая задача) в математике нужна, чтобы всегда иметь решение для конкретных вводных начальных данных. В данной ситуации вводные начальные данные - это расположение начальной и конечной позиции башни на 3-х стержнях (оно может быть любое, кстати вариантов таких выборов - 6, это обычный расчет комбинаторной задачи), ну и еще начальные данные - это количество дисков в башне (но это уже вопрос про n дисков и наличие рекурсии). Так вот, если закрепить за начальной и конечной позициями башни какие-то конкретные номера стержней из этих 6 комбинаторных вариантов, то мы решим всего-навсего одну задачу. И программа будет выдавать всегда один и тот же ответ. А хочется, чтобы начальная позиция была произвольная среди этих 6 возможных вариантов. Тогда надо начальную и конечную позиции задать не конкретными номерами стержней, а буквами i и k, которые могут принять любое значение среди 1,2,3 (ну естественно что за исключением варианта i=k), тогда временный стержень будет последним оставшимся из 3-х стержней (его позиция должна быть занумерована, а сделать это можно с помощью формулы temp = 6 - i - k)
2:30 ))))
Одно не понятно, откуда именно 6? Это результат сложения n+i+k или результат сложения номеров столбцов?
у тебя всего 3 столбца
сумма их порядковых номеров равна 6 (1 + 2 + 3)
переменные i, k, tmp как раз таки и являются порядковыми номерами столбцов, а значит i + k + tmp = 6
i и k передаются в функцию аргументами, соответственно мы сможем легко найти порядковый номер временного столбца следующим образом:
tmp = 6 - i - k
@@dadoo6912 уже разобрался, спасибо за ответ)
@@dadoo6912 Спасибо, вы мне помогли
Очень простое решение,но ничего не понятно.
Всё равно не понял. Как программа может сам понять что не надо ставить диск большего диаметра на меньшую? И как оно перемещает диски вообще по разному а в программе только 2 команды?
программа умная, а ты нет
@@nicholasspezza9449 умная лишь в этом. В остальном она тупее инфузории так как не сможет решить 1+1 или понять сейчас день или ночь
математика :)
Крайним случаем проще брать n=0 а не 1
+
Я знаю, как получит 5 по технологии
Надо сделать головоломку Ханойские башни
Когда 64 диска будет?? Мне на дом задали
для любого кол-ва дисков будет одно и тоже, уася.
Решение обобщенной проблемы Ханойских башен."Теория и практика строительства Ханойских башен", Жигалик С. Н.
"Теория и практика строительства Ханойских башен", Жигалик С. Н.
Только сейчас узнаю, что это никакая не легенда, а задача, придуманная математиком. Сегодня для меня в мире стало немного меньше красоты. Жалко.
А решение прекрасное - спасибо!
Вы реально верили в эту легенду? Красоты в решении рекурсией этой задачи для меня куда больше чем в этой легенде.
@@kosiak10851 везде есть причинноследственная связь. Если вы не знаете причины, значит и следствие должно быть под вопросом.
@@kosiak10851 ну надо дальше размышлять, чем на один шаг. Если вы к этому относитесь серьезно, значит у этого для вас также должна быть причина. Почему бог завещал конец света и т.п.?Почему богу мы вообще понадобились? Нету ли тут какой-нибудь мнительности на свой человеческий счет? Когда-то люди считали что солнце и луна вращаются вокруг земли.
@@mitri9240 не в саму легенду о наступлении конца света в момент перекладывания последнего колечка, а в существование такой легенды у одного из народов.
@@kosiak10851 у людей не было причин считать, что они являются центром чего-то. Это просто психология. Аристотель подверг сомнению, то что мы находимся на диске, хотя мог отнестись к этому как к данному. Были разные теории, в том числе те, что считали возможным и то, что начало системы координат находиться не у нас под ногами. А что касается реакции церкви она не только сейчас бугуртит на всё подряд, имя Джордано Бруно вам о чем-нибудь говорит?
В целом религия пропитана необоснованной эгоцентричностью человечечества. Отрицать это, если вы прочитали Библию, просто глупо. Если человек ученый то все на свете он будет ставить под сомнение, не просто с головы брать толкование всего, а нелогичность будет его раздражать. Взять вот аксиомы в геометрии, никто не говорит что они верные, хотя православные любят утверждать, что математики принимают их на веру, но тогда бы не появлялось неевклидовой геометрии, по типу геометрии Лобачевского. Он поставил под сомнение аксиому, и показал, что если взять те аксиомы выйдет вот так. Взять другие выйдет по другому, но они не являются опорой, они лишь условие задачи. Мы верим в аксиому когда решаем задачу которая в условии утверждает, что эти аксиомы являются верными. Простой пример: находясь на шаре, выбрать кратчайшим путем, между двумя точками, прямую будет попросту неверно, самолёты тратили бы лишнее топливо при перелёте через океан если бы полагались на аксиомы сформулированные Евклидом для плоскости.
"Теория и практика строительства Ханойских башен"
Вроде все понятно, но на самом деле не понятно.
Чат gpt множит все ваши лекции и других тоже на ноль x0. Вся инфа в идеальном образе получается от искусственного интеллекта
Ахаххахах, вспомнила как у меня была довольно простая ошибка в коде, gpt-4 говорил что ошибки нет и все должно работать правильно, но не работало... Самой пришлось додумываться, так что пока ещё ИИ не может заменить эти лекции, так ещё и постоянно выдаёт неправильную инфу под видом правильной
Очередное видео которое просто ставит перед фактом, что задачу нужно начинать с конца и перекладывать n-1 дисков без объяснения как к такому решению пришли. В чём полезность? :(
Неужели нельзя было снять так, чтобы было без этого вот "ой, я сам толком не понимаю, надо вот так, а, нет, это неправильно, надо не вот так а вот эдак, а, хотя нет, подождите"? Только ещё больше запутал. >:(
тут нет никакого по сути программирования.. чистая математика
Отличный пример для понимания работы рекурсии. Именно в программировании это и нужно показывать
#include
// Функция показывает движение from -> to
void move(int to, int from) {
printf("%i -> %i
", to, from);
}
// печатает решение для головоломки размера n,
// сдвигая n дисков из колонны "from"
// в колонну "to"
void hanoi(int n, int to, int from) {
if (n == 1)
move(to, from);
else {
int tmp = 6 - to - from;
hanoi(n - 1, from, tmp);
move(from, to);
hanoi(n - 1, tmp, to);
}
}
int main(void) {
int n;
printf("Insert n: ");
scanf("%i", &n);
hanoi(n, 1, 3);
return 0;
}