Как-то раз мне было грустно, и я решил написать какой-нибудь генетический алгоритм. Ведь, как известно, это лучший способ развеселиться. Ну, по крайней мере, я всегда так делаю.
Так как для реальных подвигов нужны реальные задачи, написал скриптик на PHP, который из цифр от 1 до 9 и расставленных между ними знаков сложения, вычитания, умножения, деления, корня, факториала и возведения в степень, составляет заранее заданное число.
Например,
2019 = 1+2*34-5*6*(7-8*9)
2019 = (1*23+4+5-6)*78-9
2019 = -1+2/3+4*(5/6+7*8*9)
2019 = 1+2*34+5*6*(7*8+9)
В общем, идея ясна. Побаловался и забыл.
А вчера я узнал, что есть число 10958, которое таким образом представить невозможно (но это неточно, потому что не доказано).
Откопал в архиве скрипт, запустил - а ведь верно.
Для других чисел отрабатывает мгновенно, а тут не работает никак, всю ночь работал.
Интересненько. Возможно, правда, скрипт плохо работает, в конце концов, он работает только над полем рациональных чисел, да и с вложенными корнями не особо дружит. Надо допилить, видимо.
Ах да, забыл. В чём суть генетического алгоритма в данном случае? Берём 123456789, и щедро сыпем между ними все возможные знаки, плюсы, минусы, факториалы - вот это вот всё. Получаются ужасные формулы, которые к тому же и некорректны.
Для всех ужасных формул запускаем мутации - удаляем, добавляем или меняем знаки. Рано или поздно появляется выражение, которое можно вычислить. Ну, то есть, не 1-*/2345678+++()(((((9, а, например, 1*2345678+(9) - это уже что-то. В суровой математической эволюции выживают те, кто даёт хоть какой-то ответ, вытесняя нежизнеспособные формулы под солнцем.
Затем при помощи тех же мутаций формулы продолжают совершенствоваться, постепенно давая ответ всё ближе к заданному числу, и в конце концов давая верный результат.
Выглядит туповато, но именно так всё и работает. Да и мы, в определённом смысле, тоже продукты схожих процессов.