2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 78, 79, 80, 81, 82, 83, 84 ... 192  След.
 
 Re: Магические квадраты
Сообщение12.02.2010, 16:37 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb
Скачала ваш архив и распаковала.
Программа test у меня выполнилась.
Программа, которая имеет вид исполняемой, промелькнула в мгновение ока, что она там делала, не знаю.
Пожалуйста, подскажите, что мне нужно сделать, чтобы скомпилировать программу.
Есть ещё файлы: TPC, turbo, ST11, ST13, ST14.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение12.02.2010, 21:49 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #287442 писал(а):
svb
Программа test у меня выполнилась.
Программа, которая имеет вид исполняемой, промелькнула в мгновение ока, что она там делала, не знаю.
Пожалуйста, подскажите, что мне нужно сделать, чтобы скомпилировать программу.
Есть ещё файлы: TPC, turbo, ST11, ST13, ST14.

Они уже даны откомпилированными, но они ДОСовские, поэтому желательно их запускать по старинке. Я пользуюсь навигатором FAR, он дружит с виндовозом.
Батовский файл test.bat просто запустил по очереди программы mak1.exe, mak3.exe и mak4.exe. Каждая из этих программ создала свой текстовый файл, ST11, ST13, ST14, соответственно. В качестве исходного набора они использовали файл st1.txt с 25 числами 1,..,25 (из виндовоза этот файл вы можете посмотреть тем же блокнотом). Файлов ST11, ST13, ST14 в архиве не было - они уже были созданы на вашей машине. Можете их переименовать с расширением .txt , тогда блокнотом увидите их содержимое - в конце каждого файла указано время исполнения на вашей машине. Файл !README.TXT дан в альтернативной кодировке, поэтому если будете его смотреть блокнотом в виндовозе, то переключитесь на шрифт Terminal. В нем коротко описано, что делать.
Вчера попробовал запустить mak4.exe, скормив ей простые числа из набора prost2.txt - менее 2-х часов понадобилось для создания более 11 тысяч квадратов. И это было только начало, но, похоже, можно сгенерировать весь набор квадратов за "приемлемое" время. У меня возникло ощущение, что простые числа - очень хороший материал для магических квадратов (и для задачи о рюкзаке :) ).
Компилятор tpc.exe я вам прислал для того, чтобы вы переходили на паскаль. Конечно, это уже старенький компилятор для ДОС, но пока им можно работать. Для ваших задач он очень хорош и язык проще BASIC-а. Вам уже советовали переходить на Free Pascal, но, боюсь, он может вас отпугнуть абсолютно ненужными вам вещами - слишком много там добавлено для работы под виндовоз. Для расчетных задач это не нужно. Но там есть аналогичный tpc компилятор fpc.exe, но уже 32 и 64 битовый, что более подходит для современных машин. А самое главное - там можно использовать очень большую память, вам может она понадобиться. Хотя переборным задачам она не всегда нужна - пример, ваш алгоритм.
tpc вы можете использовать уже сейчас - исправьте в тексте программы тип переменной w с integer на longint, а то сумма w быстро превысит 32000 и возникнут проблемы. После компиляции будет новый работоспособный вариант программы.
Если у вас нет навигатора, то в виндовозе в меню запуск наберите CMD - запустится досовское окно. В нем вы сможете запускать присланные программы.

Чтобы не загромождать форум информацией не по теме, можете писать мне на мой адрес svb@ninodom.ru

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение13.02.2010, 07:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb
Спасибо, но пока ничего не поняла :)
Я напишу вам ЛС.

Только вопрос интересный всем: вы какие квадраты порядка 4 строили? Из какого массива? Судя по количеству построенных квадратов, этот массив состоял не из 16 чисел. Так?

Да, простые числа очень хороши для построения магических квадратов.
А вы попробуйте строить те же квадраты порядка 4 из последовательных смитов :)

-- Сб фев 13, 2010 09:29:13 --

maxal
У меня есть вопросы, касающиеся плотности множества простых чисел.
Вы привели параметр, характеризующий эту плотность.

Вопрос 1: каким условиям должен удовлетворять этот параметр, если множество достаточно плотное?

Вопрос 2.
Известно, что для любого натурального $k$ существует отрезок из $k$ последовательных натуральных чисел, в котором нет ни одного простого числа.
Не является ли наличие таких пустых оазисов нарушением достаточной плотности множества простых чисел?
И не будет ли это серьёзным препятствием в построении магических квадратов больших порядков из последовательных простых чисел?

(Извините, если вопрос опять тривиальный, но здесь ведь нет перечня тривиальных и нетривиальных вопросов :( )

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение13.02.2010, 13:16 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak писал(а):
Только вопрос интересный всем: вы какие квадраты порядка 4 строили? Из какого массива? Судя по количеству построенных квадратов, этот массив состоял не из 16 чисел. Так?

Да, простые числа очень хороши для построения магических квадратов.
А вы попробуйте строить те же квадраты порядка 4 из последовательных смитов :)

Я, вроде, писал про порядок 5 ? Исходный массив prost2.txt - 25 простых чисел 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 101 103. Построил 11916 квадратов за 5251.26 сек.
Вот из файла последний квадрат:
11916:
3 41 29 89 71
79 83 23 11 37
17 7 61 101 47
103 59 53 13 5
31 43 67 19 73

Подсунул какой-то набор 25 смитов (чтобы сумма делилась на 5) - программа достаточно быстро сделала полный перебор и не нашла ни одного квадрата. Это, в общем, понято - нет взаимной простоты, по той же четности набор мог не проходить.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение13.02.2010, 13:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Я что-то просмотрела из ваших сообщений? :)

Итак, ваша программа замечательно работает для проверки массивов из 25 чисел. Это же здорово!
Тогда вперёд. Поверим 12d3 , что в первом миллионе нет подходящего массива, складывающегося в магический квадрат. Берите следующий миллион и проверяйте всех кандидатов. Надеюсь, что квадрат 5-го порядка построится хотя бы в пределах 10 миллионов. Хотя как знать! Но квадрат 6-го порядка построился вообще из малюсеньких последовательных смитов - прямо из первого кандидата.

Кстати, протестируйте свою программу для массива смитов, из которого магический квадрат 5-го порядка точно строится, например, вот для такого:

Код:
4 166 634 762 265
382 346 663 355 85
645 517 454 121 94
526 483 58 202 562
274 319 22 391 825

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение13.02.2010, 18:46 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #287578 писал(а):
Итак, ваша программа замечательно работает для проверки массивов из 25 чисел. Это же здорово!

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

Nataly-Mak писал(а):
Кстати, протестируйте свою программу для массива смитов, из которого магический квадрат 5-го порядка точно строится, например, вот для такого:

Код:
4 166 634 762 265
382 346 663 355 85
645 517 454 121 94
526 483 58 202 562
274 319 22 391 825


Что ж :) , программа честно прошла полный перебор, а я с тоской наблюдал и думал, что нужно ее дорабатывать - она работает в 32 раза дольше, чем нужно!
Зря вы дали уже готовый квадрат - он мог оказаться единственным и что тогда отвечать? Но ... все же программа выдала 64 решения, т.е. еще один квадрат:

Код:
319 526 382 483 121
  22 645 562 517  85
634   4 166 202 825
  94 265 663 355 454
762 391  58 274 346

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 01:55 
Модератор
Аватара пользователя


11/01/06
5660
 i  Обсуждение OEIS отделено в тему topic30306.html

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 05:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb
Поздравляю! Это уже хороший результат.

Сколько времени программа выполняла полный перебор для этого массива смитов?

Как я уже отмечала, для смитов перебор должен выполняться гораздо быстрее, чем для простых чисел, потому что смиты плохо складываются в пятёрки, дающие магическую константу квадрата. И магических квадратов из заданного массива смитов строится очень мало. Вот из проверенного вами массива смитов построились всего два квадрата! А из проверенного раньше массива простых чисел построились тысячи квадратов (даже если разделить общее количество на 32, всё равно много получается).

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 06:09 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak в сообщении #287530 писал(а):
Вопрос 1: каким условиям должен удовлетворять этот параметр, если множество достаточно плотное?

Точно сказать затрудняюсь. Может, что-то типа $\geq n^c$, где $c$ - некоторая константа (например, $c=-1/2$).
Nataly-Mak в сообщении #287530 писал(а):
Вопрос 2.
Известно, что для любого натурального $k$ существует отрезок из $k$ последовательных натуральных чисел, в котором нет ни одного простого числа.
Не является ли наличие таких пустых оазисов нарушением достаточной плотности множества простых чисел?
И не будет ли это серьёзным препятствием в построении магических квадратов больших порядков из последовательных простых чисел?

Если говорить о простых числах в начальном отрезке натуральных чисел, то такие "оазисы" без простых чисел проблем доставлять не должны. Дело в том, что в совокупности простые все равно распределены более-менее равномерно (см. Теорему о распределении простых чисел), и если такой оазис не может быть очень большим по сравнению с длиной выбранного отрезка. Например, в пределах первых 100 натуральных чисел максимальное расстояние между простыми равно лишь 8, в пределах первых 1000 натуральных чисел оно равно лишь 20 и т.д. (см. последовательность A038460).

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 07:43 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот пример (если я правильно понимаю определение плотности множества):

n = 1, M = 907, m = 888.

В этом случае:

ρ = 1/(907 - 888 + 1) = 0,05

И это никак не удовлетворяет приведённому вами условию для плотности множества.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 07:50 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak
Не удовлетворяют, но я и не говорил, что всякое множество простых является плотным. Те множества, что возникают в задачах построения магических квадратов больших порядков ($n\geq 5$) из как можно меньших простых, являются подмножествами относительно коротких начальных отрезков натурального ряда. И вот они-то являются плотными.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 08:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
maxal в сообщении #288963 писал(а):
Nataly-Mak
Не удовлетворяют, но я и не говорил, что всякое множество простых является плотным. Те множества, что возникают в задачах построения магических квадратов больших порядков ($n\geq 5$) из как можно меньших простых, являются подмножествами относительно коротких начальных отрезков натурального ряда. И вот они-то являются плотными.

Но почему же "относительно коротких начальных отрезков натурального ряда"?
Если порядок квадрата будет $n = 100000$, разве этот отрезок будет коротким?

svb

Ура! Ваша программа у меня заработала!
Вы наблюдали за её работой с тоской, а я - с восторгом. Потому что такое быстродействие мне и не снилось.
Программа перебрала все параметры для I = 1 за 15 минут и перешла к I = 2.
Для этих значений параметров найдено 8 квадратов.
Восторг! Вот первые два квадрата, записанные в выходной файл:

Код:
1:
   4 166 762 634 265
382 346  58 483 562
517 645 454 121  94
654 355 535 202  85
274 319  22 391 825
2:
   4 166 762 634 265
382 346 535 483  85
517 645 454 121  94
654 355  58 202 562
274 319  22 391 825


Хорошо работает программа.
Если вы её ещё оптимизируете, будет вообще отлично.

А вариант другого языка (с более высоким быстродействием) возможен?

Приглашаю всех искать наименьший магический квадрат 5-го порядка из последовательных смитов по предложенной svb программе.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 15:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Если брать массив, из которого магический квадрат не складывается, такой массив проверяется около 4 минут (обратите внимание: полный перебор всех вариантов!). Всего 4 минуты!

Я проверила уже 10 таких массивов.
Первый массив взяла тот, который первым переваливает за миллион, вот этот:

Код:
999153, ..., 1000462


Беда в том, что массивов-кандидатов очень много, потому что я накладываю на массив только одно условие: сумма всех чисел массива кратна 5.

Значит, надо ещё как-то оптимизировать поиск массивов-кандидатов (как это сделал maxal для кандидатов в квадрат 4х4), чтобы их было поменьше, а то слишком много массивов приходится проверять.

Впрочем, можно и все подряд проверять, но тогда надо в программу вставить блок поиска массивов-кандидатов; сначала ищется массив, потом сразу проверка найденного массива идёт, потом ищется следующий кандидат и проверяется и т. д.
Ввести в эту программу приличный массив смитов и - вперёд. Пусть программа работает несколько часов. За это время она сможет обработать много массивов-кандидатов, если в час она обрабатывает примерно 15 массивов.

svb
Вы поняли моё предложение? :)

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 16:37 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #288968 писал(а):
Если вы её ещё оптимизируете, будет вообще отлично.

А вариант другого языка (с более высоким быстродействием) возможен?

Кое-что я вчера сделал, но сначала несколько слов о вашем алгоритме для тех, кто не стал смотреть текст на васике. В нем идет перебор с помощью вложенных циклов - в таблице ниже показаны переменные перебора i,j,..,v. Прежде чем входить в очередной вложенный цикл идут проверки о необходимости подобного вхождения. Например, после задания переменных i,j,k,l вычисляется элемент с индексом x1 и процесс не идет дальше, если проверки не пройдены. Понятно, что это можно организовать разными способами. У Наталии последовательно вычисляются элементы квадрата с индексами x1,x2,x3,x4,x5,x6, а далее элементы 21,22,23,24,25 (это не числа, а обозначения элементов квадрата). Насколько оптимально это сделано у Наталии? Вопрос, вообще говоря, открыт. Но, по крайней мере, весьма неплохо сделано.
Прежде всего (это сделано уже в программах mak3 и mak4), когда я переписывал алгоритм, то обратил внимание, что индексы x1,..,x6 находились, но из дальнейшего перебора не исключались - я немного поправил текст и быстродействие увеличилось в 4 раза. Выкинул ненужные проверки на финише - сумму элементов последней строки проверять не надо, т.к. уже исходный набор чисел выбран с суммой равной 5 магическим числам. Кстати, особого выигрыша по времени это не дало - до последних операций нужно еще добраться :) .
Код:
i  j  k x1  l       
t x3 x5  m x4     
x6 21  n  v  s
u x2 22  q  r   
o 23 24 25  p


После тестирования на смитах стало очевидно, что молотить уже найденные варианты дополнительно 31 раз совсем ни к чему. Для квадратов 5 порядка, хорошо известно, существует понятие изоморфизма, т.е. повороты и симметрия из любого квадрата дают традиционно эквивалентные квадраты, плюс два специальных преобразования увеличивают набор эквивалентных квадратов до 32.
1. Посмотрим на элементы i,l,p,o,x3,m,q,x2 - максимальный элемент можно с помощью преобразования вывести на внешнюю границу, а затем с помощью поворота перевести его на место i. Итак:
i>l,p,o,x3,m,q,x2
2. Смотрим на элементы j,x1,u,t. Не затрагивая элемента i, можно с помощью второго спец. преобразования (одновременное переворачивание внутренних горизонтальных и вертикальных полос) и симметрии относительно диагонали i-p добиться, чтобы максимальный элемент рассматриваемой группы оказался на месте j. Итак:
j>t,x1,u

Осталось чуть изменить пределы перебора циклов и... модифицированная программа mak5 заработала.
Сначала я протестировал ее на тех же смитах, что предложила Наталия.
Было: 12148.90 сек
Стало: 594.83 сек
Программа, как ей и положено, выдала 2 не изоморфных квадрата.

Далее я подсунул программе исходный набор из простых чисел 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 101 103 и лег спать. Результат:
Время работы: 26968.40 сек
Количество не изоморфных квадратов - 58257, что соответствует 233028 традиционно различным квадратам и 1864224 всех квадратов.

Что дальше? Пока выбор элементов из уменьшающегося набора в алгоритме идет с помощью линейного поиска, что "не есть хорошо" - любая "деревянная" конструкция, обычно, лучше, особенно, если попытаться расширить исходный набор. Выбор другого языка и технических средств - это за пределами алгоритма. Конечно, 16-битовый BP7 нужно заменить на FP - эффект должен быть. Далее, в mak4 я заложил тип integer, что уже на смитах мало - пришлось кое-где поставить longint. В особые свойства иных языков я не очень верю - необходимые ассемблерные вставки можно делать уже древнем паскале. Все-таки, основной эффект дает алгоритм, а не язык (интерпретаторы исключаем :) ), и удачное структурирование данных. Вот здесь всегда есть, над чем поработать.

-- Вс фев 14, 2010 16:51:14 --

Nataly-Mak в сообщении #289028 писал(а):
Если брать массив, из которого магический квадрат не складывается, такой массив проверяется около 4 минут (обратите внимание: полный перебор всех вариантов!). Всего 4 минуты!

Я проверила уже 10 таких массивов.
Первый массив взяла тот, который первым переваливает за миллион, вот этот:

Код:
999153, ..., 1000462



Внимание! Будьте осторожны - в вашем варианте программы тип переменных на дает возможности использовать числа более 32000. Я вам уже писал - замените integer на longint в тексте mak4.pas и откомпилируйте. Строка для запуска компилятора:
tpc.exe mak4.pas

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение14.02.2010, 16:53 
Модератор
Аватара пользователя


11/01/06
5660
svb в сообщении #289039 писал(а):
Но почему же "относительно коротких начальных отрезков натурального ряда"?
Если порядок квадрата будет $n = 100000$, разве этот отрезок будет коротким?

Не коротким, но относительно коротким (по сравнению с количеством простых чисел, равным $n^2$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 78, 79, 80, 81, 82, 83, 84 ... 192  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group