Comments 12
Теперь еще и это будут на собеседованиях спрашивать?
Этот инвариант полезен в некоторых доказательствах, приведённых ниже; в частности, обратите внимание, что невозможно разделить элемент a, если сумма палочек в «неиспользуемом жёлобе» не меньше a.
Ну это явно же неправда. На картинке сумма в «неиспользуемом жёлобе» 4+5 = 9 (и она постоянна), элемент 6 разделяется на 2+4 или 1+5 (2-й и 3-й шаг преобразования на картинке). Утверждение гласит, что 6 нельзя разделить, если 9 не меньше 6: !(9 < 6) == 9 >= 6 == true. Это условие истинно, но элемент разделяется.
Косяк перевода. В оригинале:
in particular, notice that we cannot ever split an element
aunless the sum of the sticks in the unused gutter is at leasta
То есть невозможно разделить элемент a, если сумма в «неиспользуемом жёлобе» меньше а. Переводчик запутался в тексте и вставил лишний не, который меняет утверждение на противоположное.
Похоже на классическую задачу поиска пути в пространстве состояний.
Удивительно, но я 3 раза прочитал начало статьи, но так и не понял, а чем должен быть переворот.
Потом открыл оригинал и только там нашёл, в чём же суть задачи всё-таки.
Нельзя образовывать число, которое больше максимального числа в исходном списке.
Также все элементы списка должны оставаться различными
Интересно, для чего эти условия? Они выглядят искусственными и с ними задача теряет изящность.
Также все элементы списка должны оставаться различными
Без него можно было бы тупо первым шагом поделить все элементы по единичке, а вторым шагом собрать их в новые группы. Это не интересно.
Нельзя образовывать число, которое больше максимального числа в исходном списке.
Опять же, на первом шаге сливаем все числа в одно большое, на втором шаге делим как надо.
Без него можно было бы тупо первым шагом поделить все элементы по единичке, а вторым шагом собрать их в новые группы. Это не интересно.
Понятно, что без ограничений задача становится абсолютно тривиальной. Интересен практический смысл подобных ограничений кроме как для разминки мозгов.
Это не интересно.
Добро пожаловать в реальную жизнь
Томаш Рокицки уже провел некоторое исследование и OEIS-тификацию
Тут хочется добавить, что это тот самый Tomas Rokicki, главный гуру в recreational computer science, автор программы Golly (самая известная программа по симуляции игры "жизнь" Конвея);
также, он доказал, что кубик Рубика собирается за не больше, чем 20 ходов из любой позиции (они использовали мощности Гугла, и в сумме затратили 35 cpu-лет).
Так что, если такой человек заинтересовался этой задачей, то уже можно считать, что она имеет ненулевое значение в научной и околонаучной тусовке.
Я так понял этот человек математик. Математики не делают практически значимые открытия специально, математики просто любят упарываться в абстракции до упора, после чего их "открытия" лежат не востребованными порой столетия. Для них это просто интеллектуальная мастурбация. А смогут ли как то применить то что они наоткрывали физики, химики, инженеры всех мастей и прочие прикладники их вот вообще нисколько не волнует.
Переворачиваем список целых чисел