Да! Отличное идея. И не в 5 раз, а на скорее порядок, занятно, что четные длины нередко обрабатываются быстрее предыдущих нечетных.
Жаль, что результат нулевой, но это все равно отличная эвристика. Она именно сокращает дерево перебора. Я все и пытался выяснить как в начале цепочки определить, что потом зайдем в тупик.
И мне кажется основание экспоненты роста уменьшается.
То, что сложность не превосходит e^N, я, кстати, могу попробовать доказать.
Для каждой тройки при произвольной второй позиции количество вариантов для третьего числа однозначно определяется первым числом в тройке и самим числом N.
Если первым числом в тройке стоит единица, то на третьей позиции допустимы все N чисел независимо от числа в центре. Если первой идет двойка, то для сохранения делимости допустимы уже не все, а каждое второе число, если тройка — каждое третье и т.д. Т.е. если слева в тройке стоит число k, то при произвольном центре, справа получаем N/k вариантов (округленное вниз, но для верхней оценки это не важно). А поскольку (почти) каждое число в какой-нибудь тройке окажется на первом месте, а центр произволен только для самой левой тройки (в остальных он является третьим числом для соседней тройки, а значит мы его уже посчитали), общее количество вариантов можно оценить произведением этих самых N/k для всех k, т.е. получаем N^N/N!.. Факториал можно оценить формулой Стирлинга и получить искомое O(e^N).
Да, точно, Эрланг. Можно поизучать. Мне Хаскель по книжкам тоже не зашел, а вот курс на Степике здорово помог, Москвин молодец.
Но комментарий ниже прекрасно демонстрирует, что это все игрушки, по большому счету. Если нужна производительность — изучай C.
О, спасибо огромное. А отрицательный результат — тоже результат. Прекрасно показывает разницу в производительности.
У Вас, кстати, основание экспоненты роста тоже оказалось около полутора, точнее 1.4 в среднем. А может там e/2?
Пролог прекрасен, спору нет )
И если Кложур называют наследником Лиспа, то то же можно сказать и про Хаскель с Прологом. Внешне программы очень похожи.
good [_,_] = True
good (a:b:c:t) = mod (a+b+c) a == 0 && good (b:c:t)
Да, занятно, тоже жив, курилка. Но полный перебор я пробовал. Я с этого начал на Питоне, но дальше N=12 не продвинулся. И проблема не (только) в языке, факториал — это круче, чем экспонента.
А так да, Вы правы, перебор и поиск с возвратом )
import Data.List (delete)
pvc :: Int -> Int -> [Int] -> [[Int]]
pvc a b [] = [[a,b]]
pvc a b xs = [a:ys |
x <- xs,
mod (a + b + x) a == 0,
ys <- pvc b x (delete x xs)]
gen :: Int -> [[Int]]
gen n = do
a <- [1..n]
b <- delete a [1..n]
pvc a b $ delete a $ delete b [1..n]
main = do
putStr "Input N > "
n <- readLn
print $ gen n
но числа больше 25 лучше не вводить, может быть очень долго
просто удалите ее и удалите половину строки с `using` parList rseq, оставив только in map hlp ab
эта часть отвечает за распараллеливание вычислений. Одним ядром не согреешься )
В общем, после всех оптимизаций и заточки под конкретную задачу удалось ускориться на три с лишним порядка и циклы в квадрате 6х6 теперь считаются за 10 секунд, в прямоугольнике 6х7 — за 20 минут. И даже в 6х8 за полтора дня находится 55488142 цикла (половинка, по Вашему совету, от всех направленных). Думал, кстати, что будет больше. Но до миллиардов все равно далеко и обсчет 7х8 с моими скоростями, по прикидкам, займет полгода-год.
А Вам он может и поддастся, ориентировочно должно оказаться около 10^10 вариантов, если будет меньше, то под вопросом окажется и оценка из Википедии.
Для 8х8, читал, экспериментально доказали, что тупиковая ситуация существует для любой начальной клетки, если следовать правилу, но выбор при равных соседях делать неслучайно. Думаю, это верно и для других размеров.
В общем-то, действительно, удивительно, что правило так хорошо работает в большинстве случаев.
Хаскель я, безусловно, еще знаю плохо, да и лучшим в мире его не называл. У каждого языка свои достоинства и недостатки. Универсального языка не было, нет, да и не надо.
Но и Вы с функциональным подходом, смотрю, не очень знакомы. И раз уж Вы подталкиваете меня к дальнейшим экспериментам, я тоже попробую. Поизучайте. Только не спрашивайте зачем это все насочиняли. Как показывает практика, map и filter вовсю шагают по планете и внедряются уже в Яву. zip, reduce (он же fold), конструкторы списков и прочие генераторы корнями отсюда же. Ждем распространения монад.
Ну а на дальнейшие статьи планы есть. Буду ждать музу )
Я так думаю, что базу ведут одни, а ценники печатают другие. И проблема как всегда во взаимодействии. Но это уже мои домыслы
Жаль, что результат нулевой, но это все равно отличная эвристика. Она именно сокращает дерево перебора. Я все и пытался выяснить как в начале цепочки определить, что потом зайдем в тупик.
И мне кажется основание экспоненты роста уменьшается.
Для каждой тройки при произвольной второй позиции количество вариантов для третьего числа однозначно определяется первым числом в тройке и самим числом N.
Если первым числом в тройке стоит единица, то на третьей позиции допустимы все N чисел независимо от числа в центре. Если первой идет двойка, то для сохранения делимости допустимы уже не все, а каждое второе число, если тройка — каждое третье и т.д. Т.е. если слева в тройке стоит число k, то при произвольном центре, справа получаем N/k вариантов (округленное вниз, но для верхней оценки это не важно). А поскольку (почти) каждое число в какой-нибудь тройке окажется на первом месте, а центр произволен только для самой левой тройки (в остальных он является третьим числом для соседней тройки, а значит мы его уже посчитали), общее количество вариантов можно оценить произведением этих самых N/k для всех k, т.е. получаем N^N/N!.. Факториал можно оценить формулой Стирлинга и получить искомое O(e^N).
Немного «на пальцах», но, думаю, сойдет.
А задача действительно занятная, сам не ожидал.
Но комментарий ниже прекрасно демонстрирует, что это все игрушки, по большому счету. Если нужна производительность — изучай C.
У Вас, кстати, основание экспоненты роста тоже оказалось около полутора, точнее 1.4 в среднем. А может там e/2?
И если Кложур называют наследником Лиспа, то то же можно сказать и про Хаскель с Прологом. Внешне программы очень похожи.
А так да, Вы правы, перебор и поиск с возвратом )
но числа больше 25 лучше не вводить, может быть очень долго
эта часть отвечает за распараллеливание вычислений. Одним ядром не согреешься )
А Вам он может и поддастся, ориентировочно должно оказаться около 10^10 вариантов, если будет меньше, то под вопросом окажется и оценка из Википедии.
В общем-то, действительно, удивительно, что правило так хорошо работает в большинстве случаев.
Хаскель я, безусловно, еще знаю плохо, да и лучшим в мире его не называл. У каждого языка свои достоинства и недостатки. Универсального языка не было, нет, да и не надо.
Но и Вы с функциональным подходом, смотрю, не очень знакомы. И раз уж Вы подталкиваете меня к дальнейшим экспериментам, я тоже попробую. Поизучайте. Только не спрашивайте зачем это все насочиняли. Как показывает практика, map и filter вовсю шагают по планете и внедряются уже в Яву. zip, reduce (он же fold), конструкторы списков и прочие генераторы корнями отсюда же. Ждем распространения монад.
Ну а на дальнейшие статьи планы есть. Буду ждать музу )