Как-то забыл отписываться про вес, восполняю этот пробел. В данный момент вешу около 97,4 кг. Трудно сказать определенно, весы дурацкие и не всегда показывают точно. Промежуточный итог - 5 кг за 3 недели, не так уж и плохо.
Еще одна
задачка с braingames для обсуждения.
Цитата
Во время уборки Мегамозг заметил, что в собрании сочинений его любимого писателя все тома стоят в обратном порядке - с 15-го по 1-й. Мегамозг решил расставить их по возрастанию. Он может взять любое количество соседних книг и переставить на другое место. Сколько таких действий ему понадобится, чтобы упорядочить 15-томник? Доказательство минимальности не требуется.
Решить ее, разумеется, можно и аналитически, но разве не интереснее написать свой велосипед для поиска?
Я решил попробовать следующий, довольно стремный подход.
1. Берем все возможные состояния массива из n уникальных элементов, которых всего n!
2. Определяем эти состояния как вершины графа.
3. Начинаем добавлять ребра. Ребро между двумя состояниями имеется, если одно состояние из другого можно получить перестановкой непрерывного блока. Например, для вершины [1,2,3,4] ребро с вершиной [1,3,4,2] будет существовать, а с вершиной [2,1,4,3] нет.
4. Запускаем поиск кратчайшего пути между начальным состоянием и обратным.
Т.к. сложность подобного способа оценивается как О((n!)^2) или, простым языком, уже при n = 9 количество необходимых операций будет не менее 131 миллиарда, что оказалось многовато для моей рабочей машины, то хочется упростить все это дело.
Для сравнения, при n = 7 поиск занимает около 1 секунды, при n = 8 около 30 секунд, для n = 9 больше 40 минут (потом я вырубил процесс, не дождавшись результата). При n = 15, которое стоит в условии задачи, цифру мне даже страшно представить.
Собственно, стоит вопрос -
как можно сделать это умнее? Точно известно, что сделать это можно за 11 перестановок.
Выбрал я такой способ для тренировки работы с графами и лямбда-выражениями, которые появились в java 8.
P.S. код здесь -
https://pastebin.com/6KuB3Lep
Да, в фильме этот момент очень подробно разбирается, но фильм я смотрел более полугода назад, да и когда смотрел, в тонкости не вникал) Если я правильно помню, основный смысл в том, что средний человек сейчас потребляет дохрена сахара. И если попробовать то же количество получать из фруктов (винограда и бананов, как пример сладких фруктов), то во-первых тебя очень быстро начнёт от них воротить (потому что их надо будет съесть много), а во-вторых, это всё-равно будет полезней, т.к. помимо сахара получишь ещё клетчатку, витамины и проч.
Да, потребление соков тоже резко сократил. Сейчас пью только те, что без добавления сахара, которые ребёнку покупаю, и в среднем не больше пары стаканов в неделю.