полезно в хозяйстве
Jul. 7th, 2016 12:39 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaКонстантин Кноп подсказал, что, оказывается, несколько лет назад был найден гамильтонов цикл на кубике Рубика. Это определенная последовательность поворотов граней, которая проводит кубик сквозь все возможные конфигурации, посещая каждую ровно один раз, и приводит обратно с той, с которой начали.
Это очень полезная штука, потому что с помощью этого цикла всякий может собрать кубик Рубика, не изучая никаких методов. Можно просто двигать грани согласно гамильтонову циклу, и в конце концов вы гарантированно придете к собранному кубику.
Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день.
[вообще-то интересная штука, с программистской точки зрения. Даже *проверить*, что это действительно гамильтонов цикл, кажется не очень простой задачей, хоть автор и попытался ее упростить своей нотацией. Наивные подходы, что приходят мне в голову, требуют очень много памяти]
Это очень полезная штука, потому что с помощью этого цикла всякий может собрать кубик Рубика, не изучая никаких методов. Можно просто двигать грани согласно гамильтонову циклу, и в конце концов вы гарантированно придете к собранному кубику.
Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день.
[вообще-то интересная штука, с программистской точки зрения. Даже *проверить*, что это действительно гамильтонов цикл, кажется не очень простой задачей, хоть автор и попытался ее упростить своей нотацией. Наивные подходы, что приходят мне в голову, требуют очень много памяти]
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2016-07-06 09:53 pm (UTC)no subject
Date: 2016-07-06 10:07 pm (UTC)а из чего это
Date: 2016-07-06 10:10 pm (UTC)Re: а из чего это
Date: 2016-07-06 11:35 pm (UTC)Re: а из чего это
Date: 2016-07-07 11:47 am (UTC)Re: а из чего это
Date: 2016-07-07 12:29 pm (UTC)no subject
Date: 2016-07-10 06:21 am (UTC)кстати, более стандартное наблюдение,
Date: 2016-07-06 10:05 pm (UTC)Re: кстати, более стандартное наблюдение,
Date: 2016-07-06 10:10 pm (UTC)Re: кстати, более стандартное наблюдение,
Date: 2016-07-06 11:21 pm (UTC)no subject
Date: 2016-07-07 06:37 am (UTC)no subject
Date: 2016-07-07 09:30 am (UTC)no subject
Date: 2016-07-07 09:41 am (UTC)no subject
Date: 2016-07-07 11:31 am (UTC)Про рёберные кубики ты прав, но наверняка там какой-нибудь инвариант несложный; и про угловые тоже прав - я сам это понял, когда шёл с обеда (в смысле, что ТОТ кубик провернётся). Но вот что касается "начали с "элементарно", а договорились до орбит", так я только по поводу того говорил "элементарно", что вернёмся к исходному положению, а не по поводу того, сколько нужно шагов. (Да и орбиты-то тут довольно гнилые, единственное математическое понятиэ, которое тут нужно, это эл-си-эм).
Во втором, кажется, на 5 ничто не делится.
no subject
Date: 2016-07-07 11:36 am (UTC)А с инвариантами такое дело: когда они есть, они все несложные, а когда он нужен, но его не видать, то охрененно сложная задача ;)
no subject
Date: 2016-07-07 11:46 am (UTC)no subject
Date: 2016-07-07 12:47 pm (UTC)no subject
Date: 2016-07-07 12:57 pm (UTC)no subject
Date: 2016-07-07 01:05 pm (UTC)no subject
Date: 2016-07-07 01:12 pm (UTC)думаю, примерно двумя словами можно обойтись
no subject
Date: 2016-07-07 02:20 pm (UTC)no subject
Date: 2016-07-07 12:44 pm (UTC)no subject
Date: 2016-07-07 02:30 pm (UTC)no subject
Date: 2016-07-23 02:41 pm (UTC)7 для угловых кубиков, игнорируя, что происходит с боковыми (и тогда видно, что через 9 таких операций угловые вернутся на круги своя)
(теперь эту первую часть можно забыть)
9 для боковых кубиков, игнорируя, что происходит с угловыми (и тогда видно, что через 7 таких итераций боковые вернутся в исходное положение)
no subject
Date: 2016-07-06 10:13 pm (UTC)задача сводится к перебору всех положений этих кубиков, то есть множества известных последовательностей поворотов
no subject
Date: 2016-07-06 10:22 pm (UTC)no subject
Date: 2016-07-06 11:03 pm (UTC)это сложнее, да :о))
no subject
Date: 2016-07-06 11:09 pm (UTC)no subject
Date: 2016-07-07 02:41 am (UTC)no subject
Date: 2016-07-07 02:37 am (UTC)no subject
Date: 2016-07-07 06:17 am (UTC)Шпионы с колодами карт были, шпионы с кубиками рубика в качестве шифроблокнотов.
no subject
Date: 2016-07-07 02:34 pm (UTC)no subject
Date: 2016-07-08 01:09 am (UTC)no subject
Date: 2016-07-07 05:28 am (UTC)А как выглядят эти подходы?
no subject
Date: 2016-07-07 05:59 am (UTC)И это только "Р", а найти его - огого какой "NP"!
no subject
Date: 2016-07-07 06:14 am (UTC)Почему он назыаается гамильтонов?
no subject
Date: 2016-07-07 09:04 am (UTC)no subject
Date: 2016-07-08 06:00 am (UTC)no subject
Date: 2016-07-07 06:48 am (UTC)"Хе, и я так могу" (с) Промокашка.
no subject
Date: 2016-07-07 07:01 pm (UTC)