Для Ханойской башни я предлагаю простое и мнемоническое решение. Правило следующее: - перемещать наименьший диск по кругу, по часовой стрелке двумя различными способами: - Even для четных дисков (2, 4, 6, 8…): a -> b -> c -> a ->… ˗ для нечетных дисков (1, 3, 5, 7, 9…): a -> c -> b -> a ... - переместите меньший диск, из двух влево, на основной, это единственно возможная операция, - в следующем шаге переместите меньший диск снова по кругу, как показано выше - следующим ходом перемещайте диск единственным возможным способом ... и так далее, пока не будут доставлены все диски от начальной ставки "а" до конечной целевой ставки "с". Я надеюсь, что я был ясен, спасибо за ваше внимание и наслаждайтесь.
ниже пишут, что школьная задача :), да для 4го десятка это хорошая и интересная задачка, чтобы мозги растормошить )). в уме уже трудновато представить )) все решение
Блин.Вот компьбтерные игры - это. Дима фанат игрушек! Надо будет записать в список сделать игрушку ХАнойская Башня. Я как то послднее времяч на Фри Паскле, и Паскаль АБВ. И также вот КуБэйсике64.
Все классно, единственное не понятно откуда формула взялась каким образом мы пришли к сумме номеров столбцов)))это прям вообще не очевидно как апельсины с мандаринами сложить и вывести формулу, можно какое то теоретическое обоснование?)))
Вроде бы и понятно описание задачи на высоком уровне, но как это блять работает никак не могу представить. Будто у функции есть мозг, и он все сам делает
Спасибо за объяснение, не уверен, откуда взялось 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)
Уважаемый Тимофей, подскажите, возможна ли реализация на Пайтон без того чтобы вписывать в функцию три переменные (hanoi(n, i, k, tmp)) ? То есть, только через n, i и k, как в вашем примере на Си? Спасибо!
Да то что это номера штырьков понятно. Не понятно как "пришли" к формуле 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. А потом, обратно, выходя в обратном порядке из функций, у нас будет выводится по очереди ответ. Таков алгоритм.
Всё равно не понял. Как программа может сам понять что не надо ставить диск большего диаметра на меньшую? И как оно перемещает диски вообще по разному а в программе только 2 команды?
Здравствуйте,помогите пожалуйста разобраться. Переписал прогу и запустил, все работат. Но я по коду не мооу понять. Почему по дебагу прога, когда выпоняется попадая на первый вызов hanoi( n-1, i, tmp) идет с новым пораметрами снова сверху до проверки n==1, а если это условие выполнятся из функции не выходит,а начинает исполнять код со второго printf ну и дальше аналогично по кругу, в итоге даже не порятно условие выхода из функции hanoi, если финальные значерия переменных 1,1,2 и tmp1. Помогите разобраться, пожалуйста.
Ахаххахах, вспомнила как у меня была довольно простая ошибка в коде, gpt-4 говорил что ошибки нет и все должно работать правильно, но не работало... Самой пришлось додумываться, так что пока ещё ИИ не может заменить эти лекции, так ещё и постоянно выдаёт неправильную инфу под видом правильной
Только сейчас узнаю, что это никакая не легенда, а задача, придуманная математиком. Сегодня для меня в мире стало немного меньше красоты. Жалко. А решение прекрасное - спасибо!
@@kosiak10851 ну надо дальше размышлять, чем на один шаг. Если вы к этому относитесь серьезно, значит у этого для вас также должна быть причина. Почему бог завещал конец света и т.п.?Почему богу мы вообще понадобились? Нету ли тут какой-нибудь мнительности на свой человеческий счет? Когда-то люди считали что солнце и луна вращаются вокруг земли.
@@mitri9240 не в саму легенду о наступлении конца света в момент перекладывания последнего колечка, а в существование такой легенды у одного из народов.
@@kosiak10851 у людей не было причин считать, что они являются центром чего-то. Это просто психология. Аристотель подверг сомнению, то что мы находимся на диске, хотя мог отнестись к этому как к данному. Были разные теории, в том числе те, что считали возможным и то, что начало системы координат находиться не у нас под ногами. А что касается реакции церкви она не только сейчас бугуртит на всё подряд, имя Джордано Бруно вам о чем-нибудь говорит? В целом религия пропитана необоснованной эгоцентричностью человечечества. Отрицать это, если вы прочитали Библию, просто глупо. Если человек ученый то все на свете он будет ставить под сомнение, не просто с головы брать толкование всего, а нелогичность будет его раздражать. Взять вот аксиомы в геометрии, никто не говорит что они верные, хотя православные любят утверждать, что математики принимают их на веру, но тогда бы не появлялось неевклидовой геометрии, по типу геометрии Лобачевского. Он поставил под сомнение аксиому, и показал, что если взять те аксиомы выйдет вот так. Взять другие выйдет по другому, но они не являются опорой, они лишь условие задачи. Мы верим в аксиому когда решаем задачу которая в условии утверждает, что эти аксиомы являются верными. Простой пример: находясь на шаре, выбрать кратчайшим путем, между двумя точками, прямую будет попросту неверно, самолёты тратили бы лишнее топливо при перелёте через океан если бы полагались на аксиомы сформулированные Евклидом для плоскости.
у тебя всего 3 столбца сумма их порядковых номеров равна 6 (1 + 2 + 3) переменные i, k, tmp как раз таки и являются порядковыми номерами столбцов, а значит i + k + tmp = 6 i и k передаются в функцию аргументами, соответственно мы сможем легко найти порядковый номер временного столбца следующим образом: tmp = 6 - i - k
Очередное видео которое просто ставит перед фактом, что задачу нужно начинать с конца и перекладывать 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);
![โรงเรียนดัดสันดาน นักเรียนเถื่อน..!! [โรงเรียนไดเม่]](http://i.ytimg.com/vi/vRKPeXn4Fl4/mqdefault.jpg)
все таки классные преподаватели получаются из выпускников МФТИ!!
@@kosiak10851 по твоему ответу понятно, что ты сам не далеко ушел от 9го класса!
Господь сам спустился и начал заливать туториалы на Ютуб! Спасибо огромное, столько всего смотрел и только сейчас сумел понять!
Тимофей Фёдорович, огромное Вам спасибо!
Не думал, что написание кода в Си может быть так увлекательно =)
Огромное спасибо за столь подробное и чёткое объяснение!
Всё таки стоит сформулировать задачу, стоящую перед программистом: требуется напечатать инструкцию для перекладывающего.
Не пойму, за счет чего в данном алгоритме обеспечивается условие "не класть больший диск на меньший", если при перемещении это нигде не обрабатывается
Это магия какая-то, а не программирование
Видно что любит свою работу))
Спасибо, очень интересно и познавательно
Я наконец понял рекурсию. Спасибо вам, Тимофей, вы лучший!
Чем дальше видео в плей-листе, тем меньше просмотров)) Спасибо, Тимофей, за труды!
Учёба и усилие над собов , всем в тягость))) так на любом образовательном канал, чем дальше, тем меньше просмотров. Мотивация слабеет)))
@@Настя-д1д3ш это да
Вы лучший! Благодарю)
Для Ханойской башни я предлагаю простое и мнемоническое решение. Правило следующее:
- перемещать наименьший диск по кругу, по часовой стрелке двумя различными способами:
- Even для четных дисков (2, 4, 6, 8…): a -> b -> c -> a ->…
˗ для нечетных дисков (1, 3, 5, 7, 9…): a -> c -> b -> a ...
- переместите меньший диск, из двух влево, на основной, это единственно возможная операция,
- в следующем шаге переместите меньший диск снова по кругу, как показано выше
- следующим ходом перемещайте диск единственным возможным способом ...
и так далее, пока не будут доставлены все диски от начальной ставки "а" до конечной целевой ставки "с".
Я надеюсь, что я был ясен, спасибо за ваше внимание и наслаждайтесь.
Вы очень приятный человек :)
Спасибо! Все стало полностью понятно!
Математика - это от Бога)) просто класс
Лучший учитель которого я знаю!
Восхитительно, спасибо.
ниже пишут, что школьная задача :), да для 4го десятка это хорошая и интересная задачка, чтобы мозги растормошить )). в уме уже трудновато представить )) все решение
Круто, спасибо! Очень познавательно и интересно.
Спасибо за объяснение
В голове так и не смог прокрутить. Рекурсия там, где она реально необходима слишком сложна для меня
приперся с питона, где не успели на лекции разобрать эту задачу...
я тоже)
и я)
Блин.Вот компьбтерные игры - это. Дима фанат игрушек! Надо будет записать в список сделать игрушку ХАнойская Башня. Я как то послднее времяч на Фри Паскле, и Паскаль АБВ. И также вот КуБэйсике64.
Все классно, единственное не понятно откуда формула взялась каким образом мы пришли к сумме номеров столбцов)))это прям вообще не очевидно как апельсины с мандаринами сложить и вывести формулу, можно какое то теоретическое обоснование?)))
Шикарно, спасибо.
Вроде бы и понятно описание задачи на высоком уровне, но как это блять работает никак не могу представить. Будто у функции есть мозг, и он все сам делает
@@manuchehrml3315 соболезную
Спасибо большое!!!
Круто , я ведь так пасьянс косынку расскладываю))) теперь надо запомнить как это кодом записать.А ханойская башня , Это косынка.
перепутал ,пасьянс паук
спасибо огромное
Гениально!!!
Тимофей, дайте видео как это сделать списками, или массивом чисел...спс
Спасибо за объяснение, не уверен, откуда взялось 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)
Очень интересно
Спасибо!
Уважаемый Тимофей, подскажите, возможна ли реализация на Пайтон без того чтобы вписывать в функцию три переменные (hanoi(n, i, k, tmp)) ? То есть, только через n, i и k, как в вашем примере на Си? Спасибо!
tmp = 6-i-k
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 но в голове всю эту последовательность сложно представлять😃
Всё равно не понял. Как программа может сам понять что не надо ставить диск большего диаметра на меньшую? И как оно перемещает диски вообще по разному а в программе только 2 команды?
программа умная, а ты нет
@@nicholasspezza9449 умная лишь в этом. В остальном она тупее инфузории так как не сможет решить 1+1 или понять сейчас день или ночь
👍👍👍
супер!
Здравствуйте,помогите пожалуйста разобраться. Переписал прогу и запустил, все работат. Но я по коду не мооу понять. Почему по дебагу прога, когда выпоняется попадая на первый вызов hanoi( n-1, i, tmp) идет с новым пораметрами снова сверху до проверки n==1, а если это условие выполнятся из функции не выходит,а начинает исполнять код со второго printf ну и дальше аналогично по кругу, в итоге даже не порятно условие выхода из функции hanoi, если финальные значерия переменных 1,1,2 и tmp1. Помогите разобраться, пожалуйста.
Magic!😂
Супер
Решение обобщенной проблемы Ханойских башен."Теория и практика строительства Ханойских башен", Жигалик С. Н.
"рекурентный случай" - это тоже самое что рекурсия?
Чат gpt множит все ваши лекции и других тоже на ноль x0. Вся инфа в идеальном образе получается от искусственного интеллекта
Ахаххахах, вспомнила как у меня была довольно простая ошибка в коде, gpt-4 говорил что ошибки нет и все должно работать правильно, но не работало... Самой пришлось додумываться, так что пока ещё ИИ не может заменить эти лекции, так ещё и постоянно выдаёт неправильную инфу под видом правильной
Только сейчас узнаю, что это никакая не легенда, а задача, придуманная математиком. Сегодня для меня в мире стало немного меньше красоты. Жалко.
А решение прекрасное - спасибо!
Вы реально верили в эту легенду? Красоты в решении рекурсией этой задачи для меня куда больше чем в этой легенде.
@@kosiak10851 везде есть причинноследственная связь. Если вы не знаете причины, значит и следствие должно быть под вопросом.
@@kosiak10851 ну надо дальше размышлять, чем на один шаг. Если вы к этому относитесь серьезно, значит у этого для вас также должна быть причина. Почему бог завещал конец света и т.п.?Почему богу мы вообще понадобились? Нету ли тут какой-нибудь мнительности на свой человеческий счет? Когда-то люди считали что солнце и луна вращаются вокруг земли.
@@mitri9240 не в саму легенду о наступлении конца света в момент перекладывания последнего колечка, а в существование такой легенды у одного из народов.
@@kosiak10851 у людей не было причин считать, что они являются центром чего-то. Это просто психология. Аристотель подверг сомнению, то что мы находимся на диске, хотя мог отнестись к этому как к данному. Были разные теории, в том числе те, что считали возможным и то, что начало системы координат находиться не у нас под ногами. А что касается реакции церкви она не только сейчас бугуртит на всё подряд, имя Джордано Бруно вам о чем-нибудь говорит?
В целом религия пропитана необоснованной эгоцентричностью человечечества. Отрицать это, если вы прочитали Библию, просто глупо. Если человек ученый то все на свете он будет ставить под сомнение, не просто с головы брать толкование всего, а нелогичность будет его раздражать. Взять вот аксиомы в геометрии, никто не говорит что они верные, хотя православные любят утверждать, что математики принимают их на веру, но тогда бы не появлялось неевклидовой геометрии, по типу геометрии Лобачевского. Он поставил под сомнение аксиому, и показал, что если взять те аксиомы выйдет вот так. Взять другие выйдет по другому, но они не являются опорой, они лишь условие задачи. Мы верим в аксиому когда решаем задачу которая в условии утверждает, что эти аксиомы являются верными. Простой пример: находясь на шаре, выбрать кратчайшим путем, между двумя точками, прямую будет попросту неверно, самолёты тратили бы лишнее топливо при перелёте через океан если бы полагались на аксиомы сформулированные Евклидом для плоскости.
Очень простое решение,но ничего не понятно.
2:30 ))))
Крайним случаем проще брать n=0 а не 1
+
Одно не понятно, откуда именно 6? Это результат сложения n+i+k или результат сложения номеров столбцов?
у тебя всего 3 столбца
сумма их порядковых номеров равна 6 (1 + 2 + 3)
переменные i, k, tmp как раз таки и являются порядковыми номерами столбцов, а значит i + k + tmp = 6
i и k передаются в функцию аргументами, соответственно мы сможем легко найти порядковый номер временного столбца следующим образом:
tmp = 6 - i - k
@@dadoo6912 уже разобрался, спасибо за ответ)
@@dadoo6912 Спасибо, вы мне помогли
"Теория и практика строительства Ханойских башен", Жигалик С. Н.
👍
Когда 64 диска будет?? Мне на дом задали
для любого кол-ва дисков будет одно и тоже, уася.
Я знаю, как получит 5 по технологии
Надо сделать головоломку Ханойские башни
"Теория и практика строительства Ханойских башен"
математика :)
Вроде все понятно, но на самом деле не понятно.
Очередное видео которое просто ставит перед фактом, что задачу нужно начинать с конца и перекладывать 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;
}