У меня есть программа, которая проверяет заданный набор из 25 чисел на предмет построения квадрата Стенли.
Я на форуме ПЕН выложила и исходник, и исполняемую программу (пишу программы на QBASIC).
Коллега
Dmitry40 код программы раскритиковал в пух и прах
Но программа у меня работает! И скорость проверки меня вполне устраивает. Конечно, я не проверяла очень огромные массивы, всего проверила до
.
К тому же, я ведь не заставляю проверять именно моей программой. Каждый волен написать свою программу проверки – более эффективную.
Алгоритм попробую описать.
Обозначим квадрат Стенли так:
Код:
a1 a2 a3 a4 a5
a6 a7 a8 a9 a10
a11 a12 a13 a14 a15
a16 a17 a18 a19 a20
a21 a22 a23 a24 a25
Итак, нам задан набор из 25 чисел такой, что сумма чисел этого набора кратна 5. Поделив сумму всех чисел набора на 5, мы получаем значение индекса квадрата Стенли
.
Для наглядности возьмём конкретный набор из 25 чисел:
Код:
0, 2, 6, 8, 12, 18, 26, 32, 36, 38, 48, 62, 66, 68, 78, 92, 96, 98, 108, 122, 126, 132, 162, 192, 222
Это нормализованный массив (хотя в общем случае массив не обязательно брать нормализованный; но поскольку нам придётся работать с очень большими простыми числами, то лучше, конечно, массив нормализовать – уменьшить все числа массива на минимальное число).
Сумма чисел этого набора равна 1850, следовательно индекс составленного из чисел этого набора квадрата Стенли будет равен 370.
Ещё: поскольку мы будем проверять наборы из 25 последовательных простых чисел, то набор у нас будет ранжирован, то есть числа расположены в порядке возрастания. О наборе всё.
Теперь о фиксировании элемента
.
Основываясь на свойствах квадрата Стенли, можно считать элемент
фиксированным; закрепляем за этим элементом минимальное число массива, то есть 0.
Для перебора у нас остаются 24 числа набора.
Начинаем перебор.
1. задаём элементы
и
(имеем 2 свободные переменные)
Вычисляем элемент
и сразу же проверяем, принадлежит ли он массиву чисел, из которых мы составляем квадрат. Как только нашёлся элемент
, принадлежащий массиву, идём дальше.
(не забудьте, что элемент
у нас равен нулю; если бы это было не так, то формула для вычисления элемента
была бы такой:
)
2. задаём элемент
(основываясь на свойствах квадрата Стенли, элементы можно задавать именно так:
)
(теперь уже 3 свободные переменные:
,
,
)
Вычисляем элемент
и проверяем его на принадлежность массиву. Как только получили допустимый элемент, идём дальше.
Надеюсь, что дальше уже не надо расписывать, идея понятна.
Если пока не совсем понятна, напишите, распишу дальше.
По второму вопросу: можно ли строить шаблоны? Конечно, можно. Алгоритм тот же самый (ведь шаблоны – это те же квадраты Стенли), только исходный массив уже будет состоять не из 25 чисел, а из N чисел (сколько хотите). К тому же, не любой квадрат Стенли может быть именно шаблоном, какие нашёл
Jens K Andersen. Тут надо следить за тем, могут ли числа, вошедшие в шаблон, дать все простые числа (теоретически).
И ещё, как я уже отметила, поиск по шаблонам, как мне кажется, бесперспективен. Очень трудно – почти невозможно – найти набор из 25 последовательных простых под заданный конкретный шаблон.
, 
]
, решение пока не найдено. Это поразительно! Столько наборов проверено и ни одного квадрата.
).
, 
] 
таких наборов из 25 последовательных простых не существует.
.