Лучший комментарий к прошлому посту:
Парадоксальный факт состоит в том, что количество комбинаций в этой задаче не такое уж и большое по меркам современных компьютеров, тем не менее их все невозможно перебрать "в лоб".
Если взять грубую оценку сверху: 5^9 способов расставить 4 операции (и конкатенацию) в 9 позициях, и 4862 (число Каталана #9) способов расставить скобки. Получается 5^9 * 4862 = 10 млрд. способов. С учетом того, что конкатенация не разрешена между скобками, точное число будет еще меньше.
Если ваш компьютер будет перебирать 100 000 комбинаций в секунду, то ему потребуются всего лишь сутки на полный перебор. К тому же такой перебор без проблем распределяется между разными машинами и 100 000 машин переберут все варианты за 1 секунду.
Почему же ее не могут решить? Проблема состоит в возведении в степень. Условие задачи позволяет делать возведение в степень любого уровня вложенности, например выражение типа 12^(3^(4^5)) - 6^(7^(8^9)) может оказаться равным 10958.
Выражение 6^(7^(8^9)) выглядит безобидно, но для его записи потребуется 10^(113 427 138) цифр. ЦИФР, Карл!!! Это не проблема того, может ли ваш язык программирования оперировать большими числами. Это проблема физики: если бы у нас был жесткий диск размером с видимую вселенную, то он смог бы хранить только первые 10^80 цифр.
Очевидное направление для оптимизации состоит в том, чтобы считать только последние несколько цифр (математики скажут остатки по разным модулям) таких больших чисел - скорее всего 99% комбинаций можно будет сразу отбросить. Из оставшихся примеров 99% не сойдутся по количеству цифр в слагаемых (или по количеству цифр в количестве цифр).
В итоге у нас останется, например, 1 000 000 примеров (0.01% от всех комбинаций), которые будут примерно сходится по порядкам операндов и по простым модулям, при этом не поддающиеся точному вычислению. Эти примеры нужно будет проверять в полу-ручном режиме, придумывая новые методы.
Таким образом даже смарт-часы на вашей руке смогут за несколько дней перебрать 99.99% от комбинаций, тем не менее вы будете как никогда далеки от решения этой задачи
Парадоксальный факт состоит в том, что количество комбинаций в этой задаче не такое уж и большое по меркам современных компьютеров, тем не менее их все невозможно перебрать "в лоб".
Если взять грубую оценку сверху: 5^9 способов расставить 4 операции (и конкатенацию) в 9 позициях, и 4862 (число Каталана #9) способов расставить скобки. Получается 5^9 * 4862 = 10 млрд. способов. С учетом того, что конкатенация не разрешена между скобками, точное число будет еще меньше.
Если ваш компьютер будет перебирать 100 000 комбинаций в секунду, то ему потребуются всего лишь сутки на полный перебор. К тому же такой перебор без проблем распределяется между разными машинами и 100 000 машин переберут все варианты за 1 секунду.
Почему же ее не могут решить? Проблема состоит в возведении в степень. Условие задачи позволяет делать возведение в степень любого уровня вложенности, например выражение типа 12^(3^(4^5)) - 6^(7^(8^9)) может оказаться равным 10958.
Выражение 6^(7^(8^9)) выглядит безобидно, но для его записи потребуется 10^(113 427 138) цифр. ЦИФР, Карл!!! Это не проблема того, может ли ваш язык программирования оперировать большими числами. Это проблема физики: если бы у нас был жесткий диск размером с видимую вселенную, то он смог бы хранить только первые 10^80 цифр.
Очевидное направление для оптимизации состоит в том, чтобы считать только последние несколько цифр (математики скажут остатки по разным модулям) таких больших чисел - скорее всего 99% комбинаций можно будет сразу отбросить. Из оставшихся примеров 99% не сойдутся по количеству цифр в слагаемых (или по количеству цифр в количестве цифр).
В итоге у нас останется, например, 1 000 000 примеров (0.01% от всех комбинаций), которые будут примерно сходится по порядкам операндов и по простым модулям, при этом не поддающиеся точному вычислению. Эти примеры нужно будет проверять в полу-ручном режиме, придумывая новые методы.
Таким образом даже смарт-часы на вашей руке смогут за несколько дней перебрать 99.99% от комбинаций, тем не менее вы будете как никогда далеки от решения этой задачи
Начинаем развиваться в области экономических отношений! https://zen.yandex.ru/media/id/5c534197b1f88200add217dd/pochemu-planovaia-ekonomika-eto-horosho--5f93d8cf46218d3c8429f2d0
Яндекс Дзен
Почему плановая экономика - это хорошо ?
О том, что такое плановая (командная) экономика и как она работает, знают все взрослые жители стран СНГ. Одни вспоминают те времена со слезами ностальгии на глазах, другие – открыто радуются сегодняшнему