Prime Sums

[svb]

Nataly-Mak

Цитата:

Открыла одну из страничек по ссылке magic.txt

Формулировка самой задачи на моей страничке - не бойтесь, там вирусов нет

Цитата:

То есть у вас полный перебор более 40 элементов даже в случае отсутствия решения прошёл очень быстро?

Просто схема такая, а может ошибка в программе

Цитата:

Ну, ровно столько, сколько вам, нам с whitefox уже повезло

Нехорошо смеяться над ... Но я имел в виду вашу схему, когда говорил "повезет" - я же работал со случайными.

[Nataly-Mak]

Эксперимент продолжается...

Итак, 11 зачётных линий находятся легко и быстро. Это 40 перебираемых элементов.
Следующий шаг: добавила ещё 2 элемента, теперь перебираются 42 элемента и ищется 12 правильных зачётных линий. Это тоже легко и быстро! Решений с 12 правильными зачётными линиями я нашла тысячи. Программу крутила долго, и всё время решения выдаются.
Так, делаю сдедующий шаг: добавляю ещё два элемента и ищу 13-ую зачётную линию. Теперь перебираются 44 элемента.
Запускаю программу, решения с 12 зачётными линиями снова посыпались, кручу программу час, 13-ая зачётная линия не находится; решения с 12 правильными зачётными линиями продолжают выдаваться. Судя по динамике переменных циклов, которые я вывожу на экран, перебор будет выполняться ещё очень и очень долго, выполнить его до конца не реально. Прервала. Думаю...

Предположим: правильная 13-ая зачётная линия найдена.
Обозначим сумму простых сумм по 13 найденным зачётным линиям $S_1$.
$S_2=1802-S_1$
Вопрос такой: может ли $S_2$ оказаться:
а) не простым числом;
б) простым числом, имеющимся среди значений найденных 13 сумм

Думаю, что вполне возможно и то, и другое. Может, ошибаюсь?

Оставшиеся 2 элемента перебирать уже не надо, они и так очевидны (то, что осталось). Вставляем их в две пустые ячейки, вычисляем сумму в 14-ой зачётной линии, это сумма $S_2$. Если полученное значение $S_2$ простое число и не повторяет значения первых 13 простых сумм, то искомое решение найдено.

[Nataly-Mak]

svb в сообщении #653497 писал(а):

Я пробовал несколько случайных схем с оценкой 1802, перебор прошел очень быстро, но решения не было.

Всё думаю над этим сообщением. Не могу понять... Как может вот такая куча вложенных циклов

(Оффтоп)

914 NEXT I44
916 NEXT I43
918 NEXT I42
920 NEXT I41
922 NEXT I40
924 NEXT I39
926 NEXT I38
928 NEXT I37
930 NEXT I36
932 NEXT I35
934 NEXT I34
936 NEXT I33
938 NEXT I32
940 NEXT I31
942 NEXT I30
944 NEXT I29
946 NEXT I28
948 NEXT I27
950 NEXT I26
952 NEXT I25
954 NEXT I24
956 NEXT I23
958 NEXT I22
960 NEXT I21
962 NEXT I20
964 NEXT I19
966 NEXT I18
968 NEXT I17
970 NEXT I16
972 NEXT I15
974 NEXT I14
976 NEXT I13
978 NEXT I12
980 NEXT I11
982 NEXT I10
984 NEXT I9
986 NEXT I8
988 NEXT I7
990 NEXT I6
992 NEXT I5
994 NEXT I4
996 NEXT I3
998 NEXT I2
1000 NEXT I1

выполниться "очень быстро"?

[перебираются 44 элемента; они пробегают разное количество значений в зависимости от того, какому множеству принадлежит элемент; множеств всего 4; в одном всего 3 числа, во втором - 19 чисел, и в двух по 12 чисел; прикиньте-ка этот полный перебор!]

Это возможно только в том случае, если перебор не выполняется весь, а решение "сидит" где-то в самом начале перебора. Но вот если решения вообще не существует, то такой перебор не выполнить и за тыщу лет Ну, разве что на кластере.

Или я что-то не то делаю? Может, уже совсем ослабла в программировании?

Нужно придумывать какие-то критерии отсечения ветвей перебора.
Уже мозги у меня кипят, ничего не придумывается

[svb]

Nataly-Mak

Цитата:

Нужно придумывать какие-то критерии отсечения ветвей перебора.

Конечно, это самое важное при переборе, вовремя отсечь варианты. Но я особых критериев не нашел. Есть проверка простоты линий и важно правильно выбрать последовательность проверяемых линий. Вспомните, как это делалось с магическими квадратами (maxal еще спорил с вами). К сожалению даже эту задачу я полноценно не решил и ограничился интуитивным расположением порядка проверки.
Далее, как обычно, важен принцип "вынесения за скобки", т.е. все, что можно вычислить раньше, нужно вычислять раньше. Эти "технические" детали зависят от конкретной реализации, но очень важны для ускорения перебора.

Но со схемами 1802 я сам был удивлен. Беру схему 1798, ищу такое же решение 1802 и конца края не видно - никаких шансов на полный перебор. А вот выбираю случайную схему 1802 и, действительно, очень быстро. Но я не проверял все схемы 1802, поэтому и написал осторожно (но сам я не очень верю, что имеется такая схема).

[Nataly-Mak]

svb в сообщении #654239 писал(а):

Вспомните, как это делалось с магическими квадратами (maxal еще спорил с вами).

Всё это я отлично помню. Потерей памяти пока не страдаю
Стараюсь всё делать оптимально. Простоту суммы в каждой линии проверяю сразу, как только сумма в линии может быть вычислена.
Порядок перебора элементов тоже стараюсь выбирать оптимальный.
И несмотря на всё это перебор получается огромный (для поиска уже 13 зачётных линий) и за реальное время не выполняется.

Я даже удивляюсь, как удаётся находить 12 зачётных линий, для них уже нужны 42 элемента!

Сейчас, насладившись одной прекрасной схемой, принимаюсь за вторую, не менее прекрасную
Творческие муки очень приятны и полезны.

Кстати, Pavlovsky куда-то пропал. Слава Богу, хоть с конкурса не пропал результаты вводит, однако

[Pavlovsky]

Написал алгоритм для нечетных N. Алгоритм оказался удачным. Получил 1802 для N=7.

[Nataly-Mak]

Pavlovsky в сообщении #654262 писал(а):

Написал алгоритм для нечетных N. Алгоритм оказался удачным. Получил 1802 для N=7.

Поздравляю! Искренне рада за вас.

[Pavlovsky]

Впрочем ничего особенного в алгоритме нет. Обычный перебор. Только перебор заменен на случайный выбор.

-- Вт дек 04, 2012 23:48:55 --

Для 50 баллов, осталось решить N=5,6 максимум и минимум. N=7,8,10 максимум.

[Nataly-Mak]

Pavlovsky в сообщении #654270 писал(а):

Впрочем ничего особенного в алгоритме нет. Обычный перебор. Только перебор заменен на случайный выбор.

А я пробовала тоже случайный выбор. Точнее у меня комбинирование случайного выбора с полным перебором. 19 элементов (с одинаковым весом) расставляю в квадрате случайной генерацией, для остальных 27 элементов полный перебор. Программа работает, "летает" но находит только 12 зачётных линий; это легко, море таких решений. Однако 13-ую зачётную линию так и не нашла ни разу. Правда, я не крутила эту программу долго, посчитала, что всё же случайный выбор мало надёжен.

Может, покрутить её?

[Pavlovsky]

Nataly-Mak в сообщении #654286 писал(а):

случайный выбор мало надёжен.

Полагаю, что полный перебор и случайный выбор одно и тоже. Особенно когда полный перебор за реальное время невозможен. Для меня замена полного перебора случайным выбором, часто используемое, стандартное решение.

[Nataly-Mak]

Тут надо ловить удачу за хвост Как повезёт...
Ну, вот 12 зачётных линий находятся почти при любом случайном раскладе 19 элементов. Но дальше этого, увы, не идёт

Я тоже часто использовала этот приём при построении магических квадратов, именно комбинацию случайного выбора и полного перебора.

Хм... а может ещё в этой схеме и вообще решения нет Потому оно и не находится.
Очень трудно искать чёрную кошку в тёмной комнате, особенно если её там нет

[svb]

Nataly-Mak

Цитата:

Потерей памяти пока не страдаю

А вот у меня очень большие проблемы и с памятью и с работой мозга. Впервые это стал замечать где-то в 55 . Кажется японцы рекомендуют больше "думать" для улучшения ситуации - вот и заставляю себя решать задачки, чтобы не превратиться в растение.

[whitefox]

Pavlovsky в сообщении #654294 писал(а):

Полагаю, что полный перебор и случайный выбор одно и тоже.

Почти.
Случайный выбор без повтора есть полный перебор в случайном порядке.

[Nataly-Mak]

whitefox в сообщении #654430 писал(а):

Pavlovsky в сообщении #654294 писал(а):

Полагаю, что полный перебор и случайный выбор одно и тоже.

Почти.
Случайный выбор без повтора есть полный перебор в случайном порядке.

Случайный перебор трудно сделать полным перебором
Как вы уследите за случайным порядком перебора? Это ведь в программе не записывается. По крайней мере, у меня.

[whitefox]

Трудно не значит невозможно.

Случайный выбор без повтора как раз и можно реализовать записывая выбранные элементы.
Я не настаиваю на этом методе, лишь указываю на его эквивалентность полному перебору.