Comments 14
Эту задачу можно сформулировать как задачу подобрать целочисленные множители xi для векторного уравнения A + x1*P1 + x2*P2 + ... xn*Pn = Z, где A начальный вектор, Pi - векторы допустимых переходов, Z - конечный вектор, но дополнительно введено условие чтоб компоненты векторов любых промежуточных сумм были неотрицательны?
Подобные статьи прямо-таки симптоматичны для современного научпопа, заражённого раковой опухолью сенсационности. Вместо того, чтобы чему-то научить читателя, они пытаются выбить из него дух. Вместо того, чтобы показать красоту математики, они демонстрируют нам пугающего монстра. Эта статья (как и миллионы ей подобных) - мерзость. И вопрос к переводчику: зачем вы ставите свой ник под машинным переводом?
Я так понял число Грэма выросло из этой проблемы.
Что-то бред какой-то. Вернёмся к исходной посылке: "У Алисы есть яблоко, и нет банана" - это вектор [1;0]. Целевое состояние - вектор (0;1). Единственный путь, который тут возможен - это "меняем яблоко на банан", всё, он один. А в статье расписывают, как для вектора из двух компонент возможны миллионы вариантов.
По сути - со словами "простая детская задача" выдают общий случай, который может быть как угодно генерализирован. Проводя аналогию - тут недавно была статься вида "сложить два числа - это же просто? Вот смотрите, сколько процессорных инструкций занимает строка a+b на питоне". И дальше мы читаем, и видим, что рассматривается предельно общий случай, когда a и b могут быть и строкой, и булевой константой, и вообще чем угодно.
Допустим, доступны только обмены: (-1;4), (1;-3), (-1;-1)
Тогда путь будет (1;0) => (0;4) => (1;1) => (0;5) => (1; 2) => (0;1)
"сложить два числа - это же просто? но посмотрите к каким огромным числам приводит эта простая детская задача! Мы придумали функцию Дакермана, которая равна Акерманиванию функции Акермана Д(2)=А(А(2)) Д(3)=А(А(А(3))) но даже так самое большое число, которое можно получить при сложении оказывается еще больше! Мы ищем самое большое число уже 10 лет и все никак до него не досчитаем, это самая важная работа в нашей жизни!"
"сложить два числа - это же просто? Вот смотрите, сколько процессорных инструкций занимает строка a+b на питоне"
Вот-вот. То ли дело ADD в ASM. Там, правда, сначала нужно переменные (или константы) распихать по регистрам или в память, а потом прочитать полученное, но в целом это немного инструкций как таковых наберется, так что и время выполнения для любого, даже самого захудалого контроллера - чего уж говорить про современные десктопные CPU, окажется более-менее приемлемым.
И дальше мы читаем, и видим, что рассматривается предельно общий случай, когда a и b могут быть и строкой, и булевой константой, и вообще чем угодно.
То есть разбор для хорошо подготовленных специалистов - неважно, профессионалов или энтузиастов, к чему приводит вайтишный код. Впрочем, я совершенно внезапно стану на сторону вайтишников - языки для нас, а не мы для языков. Если язык позволяет производить операции над переменными разных типов, то вообще-то говоря это хорошо, потому что программировать легче, а что результат компиляции тяжелеет, так это уже вопрос нанимателя такого программиста, который может по своему усмотрению устанавливать некий входной порог для соискателей. При этом для аматоров, пишущих что-то для себя в виде хобби, недостижимым пока что идеалом является вообще абсолютно нулевой уровень. Впрочем ChatGPT, кажется, делает этот все еще недостижимый идеал сильно ближе, чем когда-либо раньше.
Простая проблема приводит к слишком большим числам для нашей Вселенной