Имя: Пароль:
LIFE
 
OFF: Предлагаю челлендж: Ханойские башни на 1С
, , ,
0 Гений 1С
 
гуру
06.01.21
09:39
Что-то накрыла меня ностальгия. Вспомнил, как решали в 1993 году на Паскале на "гробах" (класс терминалок) задачу про Ханойские башни.
Решил "могу повторить".
Повторение заняло два часа, прежде чем осознал, как это делается.
А делается крайне просто. ;-)
Попробуйте сами, если решали или нет.
Мои мучения на видео, писал конечно же на 1С:
https://youtu.be/ya9LcawDm10
1 fisher
 
06.01.21
10:02
"Гений 1С: Возвращение к истокам"
Часть 10. Сортировка вставками
2 RomanYS
 
06.01.21
10:02
Если рекурсия проходит, то задача примитивная.
Страшно подумать кому может быть интересно видео в таком (2ч) формате.
Ну и для челленджа секцию хотя бы надо было правильно указать (математика и алгоритмы) и задачу описать.
3 Гений 1С
 
гуру
06.01.21
10:04
(2) Вот описание:
https://ru.wikipedia.org/wiki/Ханойская_башня
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Прошу админов поменять секцию.
Мучения были связаны с попытками "вспомнить" алгоритм. Так то гуглится быстро, согласен. Но я решил по-честному.
4 Волшебник
 
06.01.21
10:16
В чём заключается челлендж?
5 Гений 1С
 
гуру
06.01.21
10:23
(4) написать это на 1с. естественно, если это делали давно или алгоритм не знаете. Смысл - не заглядывать в гугл
6 AntiBuh
 
06.01.21
10:32
Ты ж фузиной хотел заняться
сбацай на ней
предполагаю там это делается "одной строчкой" (с)
7 Гений 1С
 
гуру
06.01.21
10:37
Вот подробнее про мою мотивацию на эти башни: https://geniy1s.ru/nostalgiya-po-hanojskim-bashnyam/
8 Волшебник
 
06.01.21
10:37
(5) Многие просто не умеют программировать без гугла https://habr.com/ru/post/521104/
9 Гений 1С
 
гуру
06.01.21
10:43
(8) класс, поржал. Но я чуть было не сдался в конце. И все же, все же, помогло, наверное, что я уже решал эту задачу.
10 PR
 
06.01.21
10:56
Геня птица-дристун
Завел тему, дристанул в нее, потерял интерес, завел другую, дристанул, потерял интерес...
Так за неделю до десятка и больше веток
11 RomanYS
 
06.01.21
10:58
Процедура КнопкаВыполнитьНажатие(Кнопка)
    
    Переложить(6, "A", "B", "С");
    
КонецПроцедуры

Процедура Переложить(Сколько, Откуда, Куда, Буфер)
    
    Если Сколько = 1 Тогда
        Сообщить(""+Откуда + "    >> " + Куда);
    иначе
        Переложить(Сколько - 1, Откуда, Буфер, Куда);
        Переложить(1, Откуда, Куда, Буфер);
        Переложить(Сколько - 1, Буфер, Куда, Откуда);
    КонецЕсли;
    
КонецПроцедуры
12 RomanYS
 
06.01.21
11:16
(11) даже попроще

Процедура Переложить(Сколько, Откуда, Куда, Буфер)
    
    Если Сколько > 0 Тогда
        Переложить(Сколько - 1, Откуда, Буфер, Куда);
        Сообщить(""+Откуда + "    >> " + Куда);
        Переложить(Сколько - 1, Буфер, Куда, Откуда);
    КонецЕсли;
    
КонецПроцедуры
13 Вафель
 
06.01.21
11:56
это же не программерская задача. тут просто нужно знать последовательнось и она не такая уж и сложная.
никаких перебоов тут нет
14 Вафель
 
06.01.21
11:58
или нужно решить именно перебором всех ходов?
15 fisher
 
06.01.21
12:05
(13) Ну вот заставить компьютер "знать последовательность" - и есть типичная программерская задача.
А конкретно эта - одна из классических задачек по программированию. Фактически часть программерского фольклора.
16 _DAle_
 
06.01.21
12:24
(14) Код, который выше написан - это не перебор все ходов. Это рекурсивная генерация ходов, перебора там нет.
17 jbond
 
06.01.21
13:02
Фиксация фиксина на 1С такая фиксация.

Обычно сейчас такие вещи модно писать на Haskell
18 Asmody
 
06.01.21
13:03
(0) Геня, покажи класс — напиши башни на Фузине!
19 Asmody
 
06.01.21
13:12
(17) на haskell она вообще должна решаться чуть ли не "в терминах постановки". Его ленивая природа как нарочно для таких случаев.
20 RomanYS
 
06.01.21
13:37
(15) ага, одна из тех задач, которые можно давать как базовую по рекурсии (кому в голову пришла мысль фрактал рекурсивно считать :))?)
(16) да, классическая задача переложить всё с одной на другую примитивна. А вот переход из одного произвольного состояния в другое произвольное можно как олимпиадную давать
21 fisher
 
06.01.21
13:42
(20) Рекурсивный расчет факториала - это очень удобный пример для того, чтобы после объяснения рекурсии тут же объяснить ее ограничения и почему на практике так делать не надо :)
22 RomanYS
 
06.01.21
13:46
(21) Логично :) Ещё логичнее показать сначала задачи, которые решить рекурсивно на порядок проще (например эту).
23 Гений 1С
 
гуру
06.01.21
13:55
(10) я возвращаюсь в свои ветки, но онлайн их не мониторю
24 Гений 1С
 
гуру
06.01.21
13:56
(11) неа
25 RomanYS
 
06.01.21
13:58
(24) Переложил по выданной инструкции, а башни не мигрировала :)? Что "неа"?
26 Вася Теркин
 
06.01.21
14:03
Так и не ответили на главный вопрос: "наименьшее число ходов"  - это сколько? Поэтому предлагаю голосовать.
27 RomanYS
 
06.01.21
14:06
(26) для 6 колец - 63 хода. Для N колец - 2^N-1 ходов
28 Вася Теркин
 
06.01.21
14:09
Дурацкая задача на игру слов: "нельзя класть большее кольцо на меньшее." надо понимать буквально. То есть самое большое на самое маленькое можно.
29 Вася Теркин
 
06.01.21
14:11
А вообще надо не кольца двигать а стержни. И всё. Раз задача такая хитрая, то по условиям явно не запрещено двигать стержень. Я Энштейн!
30 Вася Теркин
 
06.01.21
14:13
(27) Ответ 0 ходов.
31 RomanYS
 
06.01.21
14:13
(28) Филолог?
(29) Эйнштейн вроде не был филологом, но свою фамилию наверное умел правильно написать))
32 Конструктор1С
 
06.01.21
14:15
(0) фузину уже забросил что ли?
33 Вася Теркин
 
06.01.21
14:16
(31) Так он был немец наверное На зло нам.
34 Вася Теркин
 
06.01.21
14:17
(32) Никогда такое не пил.
35 Вася Теркин
 
06.01.21
14:18
К нам его не возят видимо. Коронавирус. Граница на замке.
36 Гений 1С
 
гуру
06.01.21
15:14
(32) еще не приступал. Есть текущая работа, за которую платят деньги
37 RomanYS
 
06.01.21
15:16
(36) На (25) ответь. Что у тебя не получилось?
38 mkalimulin
 
06.01.21
15:17
(33) Наверное не немец )))
39 Гений 1С
 
гуру
06.01.21
15:21
(37) у тебя перекладывает твой код, тогда ок.
скачай у меня в статье обработку, если хочешь, посмотри код. Он несколько другой
40 Провинциальный 1сник
 
06.01.21
15:21
Помню делал такое на языке prolog, там вообще было крайне просто всё. Это язык, специально предназначенный для решения рекурсий.
41 Гений 1С
 
гуру
06.01.21
15:22
Короче как-то так:

Цель(КоличествоБлинов, 1, 3);
    
Процедура Цель(Уровень, СтерженьИсточник, СтерженьПриемник) //Пирамиду какого уровня на каком стержне хотим видеть
    //Если уровень = 1, тогда просто ставим стержень туда куда нам надо
    Если Уровень = 1 Тогда
        Переставить(СтерженьИсточник, СтерженьПриемник); //Тогда просто переставляем...
    Иначе
        СтерженьИсключающий = Исключающий(СтерженьИсточник, СтерженьПриемник);
        Цель(Уровень - 1, СтерженьИсточник, СтерженьИсключающий);
        Переставить(СтерженьИсточник, СтерженьПриемник);
        Цель(Уровень - 1, СтерженьИсключающий, СтерженьПриемник);
    КонецЕсли;
КонецПроцедуры
42 Гений 1С
 
гуру
06.01.21
15:25
(40) да, Пролог и Лисп - это true BDSM
Помню когда-то ковырял что-то на XSLT, а это функциональный язык.
Сломался и плюнул, т.к. не мог контекст передавать через всю структуру кода (глобальные настройки)
43 PR
 
06.01.21
15:40
(23) Геня, ты настолько туп, что даже не понимаешь, что я не про ветки
44 Глупый ответ
 
06.01.21
15:53
(43) Тебе жалко что ли? Он тебе в компот дрищет что ли? Если администрация решит, что Серега перестарался, то введут какой ни будь параметр типа. Не больше 10 веток в месяц. Правда Гения это не усмирит, он себе еще 5 ников заведет и под ними дристать будет. Тут только личная беседа поможет.
45 Глупый ответ
 
06.01.21
15:54
я бы не сказал, что ветки фиксы прям совсем плохие. Народ в них сидит, развлекается, значит это кому то нужно. В крайнем случае их всегда опустить можно. Но зачем? Если они по 1000 постов набирают?
46 RomanYS
 
06.01.21
15:57
(41) так это (11) практически 1в1. Только ты буфер зачем-то вычисляешь, а я явно передаю.
47 Глупый ответ
 
06.01.21
15:59
(8) бабло убивает программирование, никто не хочет ждать пока кто-то там накрапает на листике свой "гениальный" велосипед, все хотят результат. А результат это библиотеки, фреймворки, которые только гуглить. Так то очень полезный навык писать алгоритмы ручкой, но всем нужно вчера и за 5 копеек.
48 Asmody
 
06.01.21
16:21
(42) да ладно! ЛИСП — прекрасный язык. Конечно, если вас не пугают скобочки.
49 Гений 1С
 
гуру
06.01.21
16:39
(45) Как говаривал Доржи "Пусть цветут все цветы", раз меня комментируют, значит это кому-то нужно. ;-)
(46) Какой буфер?
(48) по мне так он сугубо академический, я знаю, что он используется в Автокаде, но не понимаю зачем.
50 Гений 1С
 
гуру
06.01.21
16:41
(46) я по смыслу - переложить на 1 меньшую пирамидку в свободное место, потом перекинуть большой блин, потом перекинуть пирамидку на целевой блин.
51 RomanYS
 
06.01.21
16:59
(49)(50) "буфер"  это и есть свободное (не занятое и не целевое) место. У тебя это СтерженьИсключающий
52 Доктор Манхэттен
 
06.01.21
17:43
(0) Решается рекурсией очень легко. Рекурсию можно так же легко преобразовать в цикл, если вдруг захочется решать без рекурсии. Бессмысленная задача, так как слишком легкая и неинтересная, только зря время тратить на кодинг. Тут выкладывали гораздо более интересные задачи.
53 Гений 1С
 
гуру
06.01.21
17:57
(52) а вот я потратил два часа, прикинь.
54 Гений 1С
 
гуру
06.01.21
17:57
(51) а, ну может быть
55 Доктор Манхэттен
 
06.01.21
18:03
(53) Вполне допускаю что можно потратить на это два часа. Поэтому не хочется даже начинать, ибо жалко двух часов на ерундую