2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 11  След.
 
 Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 10:18 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Мне не даёт покоя метод точных ортогональных покрытий массива в применении к построению идеального квадрата 9-го порядка.
Метод замечательно работает при построении ассоциативных квадратов, и не только 9-го порядка. Я построила этим методом ассоциативные квадраты из различных простых чисел до порядка 16 включительно.

Но пойти дальше – к идеальным квадратам – у меня пока не получается.

Определение 1. Цепочкой для магического квадрата порядка $n$ с заданной магической константой $S$ называется набор из $n$ различных натуральных чисел, сумма которых равна $S$.

Определение 2. Цепочка называется нормализованной, если числа в ней расположены в порядке возрастания.

Теперь пусть задан массив, состоящий из 81 простого числа:

Код:
11 23 29 59 89 101 113 131 173 179 191 263 281 311 383 389 449 479 509 569 593 641 653 659 683 719
743 773 809 821 911 1013 1103 1109 1151 1163 1223 1229 1283 1289 1361 1433 1439 1493 1499 1559 1571
1613 1619 1709 1811 1901 1913 1949 1979 2003 2039 2063 2069 2081 2129 2153 2213 2243 2273 2333 2339
2411 2441 2459 2531 2543 2549 2591 2609 2621 2633 2663 2693 2699 2711

Будем рассматривать ассоциативный магический квадрат 9-го порядка, который мы хотим составить из чисел заданного массива.

Определение 3. Точным покрытием массива, состоящего из 81 чисел, называется набор из 9 цепочек таких, что они составлены из чисел данного массива и ни в каких двух цепочках нет одинаковых чисел.

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

Определение 4. Два точных покрытия массива называются ортогональными, если каждая цепочка первого покрытия имеет точно один общий элемент с каждой цепочкой второго покрытия.

Очевидно, что из пары точных ортогональных покрытий всегда можно построить полумагический квадрат.
А вот магический квадрат не из любой пары точных ортогональных покрытий можно построить.
В случае с ассоциативным квадратом всё проще. В нём суммы в главных диагоналях получаются автоматически (из-за свойства ассоциативности).

Покажу, как метод работает при построении ассоциативного квадрата 9-го порядка из чисел заданного массива.

Первое точное покрытие генерирую случайным образом:

Код:
1289 2213 2039 1163 1571 311 1283 1811 569
383 2243 1619 2693 2063 593 773 653 1229
2003 1499 641 1979 821 809 89 1709 2699
131 263 1613 173 2333 2531 2441 2663 101
11 113 179 449 1361 2273 2543 2609 2711
2621 59 281 191 389 2549 1109 2459 2591
23 1013 2633 1913 1901 743 2081 1223 719
1493 2069 1949 2129 659 29 1103 479 2339
2153 911 1439 2411 1151 1559 683 509 1433

Это цепочки-строки. Генерируется такое покрытие в данном примере мгновенно
(замечу, что цепочки-строки генерируются так, что выполняется свойство ассоциативности будущего квадрата).

Второй этап – получение цепочек-столбцов. Здесь это делается так: переставляем числа в строках до тех пор, пока не получим нужные суммы в столбцах. Этот этап иногда буксует, но, в конце концов, выполняется, если ассоциативный квадрат существует.

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

Код:
1283 311 1811 2213 1571 569 2039 1163 1289
773 653 2243 1619 2063 593 2693 383 1229
1979 1499 2699 641 821 89 809 2003 1709
1613 2531 101 131 2333 2441 2663 263 173
113 179 2711 449 1361 2273 11 2543 2609
2549 2459 59 281 389 2591 2621 191 1109
1013 719 1913 2633 1901 2081 23 1223 743
1493 2339 29 2129 659 1103 479 2069 1949
1433 1559 683 2153 1151 509 911 2411 1439

$K=2722$, $S=12249$

Это, собственно, и есть второе точное покрытие массива (цепочки-столбцы) ортогональное первому точному покрытию.
Как видите, тут всё очень хорошо работает.

Теперь надо пойти дальше – к идеальному квадрату.
Идеальный квадрат – это одновременно ассоциативный и пандиагональный квадрат.
Ассоциативный квадрат у нас уже есть.
Для построения пандиагонального квадрата необходимо иметь четыре точных попарно ортогональных покрытия массива.
К двум уже имеющимся (цепочки-строки и цепочки-столбцы) надо добавить ещё два точных покрытия массива: цепочки-диагонали прямые и цепочки-диагонали обратные. Эти два точных покрытия должны быть ортогональны между собой, а также ортогональны двум первым покрытиям.

Далее, как было установлено для случая пандиагональных квадратов 7-го порядка, наличие комплекта из 4-х точных попарно ортогональных покрытий массива ещё не гарантирует построение из этих покрытий пандиагонального квадрата. То есть это необходимое условие, но не достаточное.
А как будет в случае с идеальными квадратами :?:

whitefox
так как вы знакомы с этим методом, вопрос прежде всего к вам.
Посоветуйте, пожалуйста, как действовать дальше, начиная от уже известного ассоциативного квадрата (двух точных ортогональных покрытий массива).

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

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

Вопрос, конечно, и ко всем форумчанам. Задачка интересная.
К тому же, мне пока не удалось найти минимальный идеальный квадрат 9-го порядка по другому алгоритму. На сегодня имею лучшее решение с магической константой $S=13059$.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 11:29 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Nataly-Mak в сообщении #1025570 писал(а):
Для построения пандиагонального квадрата необходимо иметь четыре точных попарно ортогональных покрытия массива.
К двум уже имеющимся (цепочки-строки и цепочки-столбцы) надо добавить ещё два точных покрытия массива: цепочки-диагонали прямые и цепочки-диагонали обратные. Эти два точных покрытия должны быть ортогональны между собой, а также ортогональны двум первым покрытиям.
Это справедливо только для квадратов нечётного порядка. В случая же чётного порядка, точные покрытия, соответствующие диагоналям, неортогональны, так как всякая прямая диагональ вовсе не пересекается с половиной обратных диагоналей, а с другими обратными диагоналями пересекается ровно в двух точках.

Nataly-Mak в сообщении #1025570 писал(а):
Посоветуйте, пожалуйста, как действовать дальше, начиная от уже известного ассоциативного квадрата (двух точных ортогональных покрытий массива).
А какова группа симметрий идеального квадрата? В пандиагональном, например, любую диагональ можно сделать главной. А в идеальном? Похоже, что нет. А раз так то остаётся только перебрать все симметрии, не сохраняющие ломаные диагонали, из группы симметрий ассоциативного квадрата и проверить полученные квадраты на пандиагональность. А затем перейти к поиску другого ассоциативного квадрата.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 11:49 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #1025585 писал(а):
Это справедливо только для квадратов нечётного порядка. В случая же чётного порядка, точные покрытия, соответствующие диагоналям, неортогональны, так как всякая прямая диагональ вовсе не пересекается с половиной обратных диагоналей, а с другими обратными диагоналями пересекается ровно в двух точках.

Согласна.
Но меня сейчас и интересуют идеальные квадраты нечётного порядка: 9 и 11.

Цитата:
А какова группа симметрий идеального квадрата? В пандиагональном, например, любую диагональ можно сделать главной. А в идеальном? Похоже, что нет.

Да, в идеальном не так.
Но ведь существует куча перестановок симметричных строк/столбцов, которые сохраняют ассоциативность, но изменяют наборы элементов в диагоналях.
(Мы с коллегами подсчитывали количество таких перестановок для ассоциативного квадрата 10-го порядка; получилось огромное число. Кстати, мы пытались получить с помощью этого огромного числа перестановок из ассоциативного квадрата пандиагональный и ассоциативный, то есть идеальный; мимо!)

Но дело даже не совсем в этом.
Меня интересует, как продолжить искать точные покрытия массива, ортогональные уже найденным двум и ортогональные между собой. Вот этот этап прежде всего интересен.

А уже потом идёт этап проверки найденного комплекта из 4-х точных попарно ортогональных покрытий на предмет построения идеального квадрата.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 12:13 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Nataly-Mak в сообщении #1025587 писал(а):
Меня интересует, как продолжить искать точные покрытия массива, ортогональные уже найденным двум и ортогональные между собой. Вот этот этап прежде всего интересен.
Ничего другого кроме, упоминавшегося ранее, метода у меня нет. Полагаю его можно ещё улучшить.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 12:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Это я прекрасно помню.

Вы меня так и не поняли :-(
Мне не нужно проверять все диагонали и трансверсали.

Мне нужно, имея два точных ортогональных покрытия массива из 81 чисел, найти ещё два точных покрытия, чтобы они вместе с двумя известными составили комплект из 4-х точных попарно ортогональных покрытий массива.
Составление точных ортогональных покрытий, как я понимаю, можно выполнять, опираясь на базу всех цепочек. И кроме ортогональности точных покрытий тут ничего проверять не нужно.

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

P.S. Почему я хочу прежде всего получить хотя бы один такой комплект?
Потому что это необходимое условие. Если ни одного такого комплекта получить не удастся, значит, идеальный квадрат 9-го порядка из заданного массива чисел построить невозможно.
Правильно я рассуждаю?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 12:46 
Заслуженный участник
Аватара пользователя


19/12/10
1539

(Оффтоп)

Nataly-Mak в сообщении #1025605 писал(а):
Вы меня так и не поняли
Считаю это опиской. Полагаю Вы хотели сказать: "Вы мня не так поняли".

Nataly-Mak в сообщении #1025605 писал(а):
Мне нужно, имея два точных ортогональных покрытия массива из 81 чисел, найти ещё два точных покрытия, чтобы они вместе с двумя известными составили комплект из 4-х точных попарно ортогональных покрытий массива.
Согласен, приведённый метод проверяет возможность построения пандиагонального квадрата по известной паре ортогональных точных покрытий, и строит такой квадрат если это возможно, тем самым находя недостающую пару точных покрытий. Но так как не всякой четвёрке точных попарно ортогональных покрытий соответствует пандиагональный квадрат, то этот метод Вашу частную задачу не решает. Ибо возможен случай когда четвёрка точных попарно ортогональных покрытий существует, а пандиагональный квадрат — нет.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение10.06.2015, 14:18 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Это полученное мной приближеение к решению, в нём 4 неправильных элемента; неправильность их в том, что они не являются простыми числами, принадлежащими заданному массиву:

Код:
191 101 1223 2711 773 2411 2243 263 2333
2663 2273 743 593 2543 1163 89 2153 29
2039 653 1151 2549 2339 911 521* 23 2063
1013 2081 113 821 1289 1109 1229 2591 2003
1883* 1283 2213 281 1361 2441 509 1439 839*
719 131 1493 1613 1433 1901 2609 641 1709
659 2699 2201* 1811 383 173 1571 2069 683
2693 569 2633 1559 179 2129 1979 449 59
389 2459 479 311 1949 11 1499 2621 2531

Неправильные элементы помечены звёздочкой.

Мы не будем обращать внимание на то, что 4 элемента неправильные. Мы имеем идеальный квадрат 9-го порядка, составленный из различных натуральных чисел.

Массив из 81 числа, соответствующий этому квадрату, будет такой:

Код:
11  23  29  59  89  101  113  131  173  179  191  263  281  311  383  389  449  479  509  521  569  593 
641  653  659  683  719  743  773  821  839  911  1013  1109  1151  1163  1223  1229  1283  1289  1361  1433 
1439  1493  1499  1559  1571  1613  1709  1811  1883  1901  1949  1979  2003  2039  2063  2069  2081  2129 
2153  2201  2213  2243  2273  2333  2339  2411  2441  2459  2531  2543  2549  2591  2609  2621  2633  2663 
2693  2699  2711

Далее я составила 4 точных попарно ортогональных покрытия данного массива на основе приведённого квадрата; цепочки в покрытиях нормализованы.

№ 1 (цепочки-строки)

Код:
101  191  263  773  1223  2243  2333  2411  2711
29  89  593  743  1163  2153  2273  2543  2663
23  521  653  911  1151  2039  2063  2339  2549
113  821  1013  1109  1229  1289  2003  2081  2591
281  509  839  1283  1361  1439  1883  2213  2441
131  641  719  1433  1493  1613  1709  1901  2609
173  383  659  683  1571  1811  2069  2201  2699
59  179  449  569  1559  1979  2129  2633  2693
11  311  389  479  1499  1949  2459  2531  2621

№ 2 (цепочки-столбцы)

Код:
191  389  659  719  1013  1883  2039  2663  2693
101  131  569  653  1283  2081  2273  2459  2699
113  479  743  1151  1223  1493  2201  2213  2633
281  311  593  821  1559  1613  1811  2549  2711
179  383  773  1289  1361  1433  1949  2339  2543
11  173  911  1109  1163  1901  2129  2411  2441
89  509  521  1229  1499  1571  1979  2243  2609
23  263  449  641  1439  2069  2153  2591  2621
29  59  683  839  1709  2003  2063  2333  2531

№ 3 (цепочки-диагонали прямые)

Код:
191  449  821  1151  1361  1571  1901  2273  2531
59  101  389  743  1289  2069  2441  2549  2609
509  593  641  683  1109  1223  2339  2459  2693
479  569  659  911  1229  1439  1709  2543  2711
311  521  719  773  839  1163  2591  2633  2699
23  89  131  1559  1883  1949  2003  2201  2411
11  179  1013  1283  1493  1811  2063  2153  2243
29  263  383  1499  1613  2039  2081  2129  2213
113  173  281  653  1433  1979  2333  2621  2663

№ 4 (цепочки-диагонали обратные)

Код:
389  521  569  1109  1361  1613  2153  2201  2333
89  263  281  911  1289  1493  2531  2693  2699
59  131  659  821  1163  2213  2243  2339  2621
113  449  683  719  1283  1499  2411  2543  2549
11  593  773  1151  1709  1883  1979  2069  2081
641  653  743  839  1013  1571  1949  2129  2711
173  179  311  1223  1439  2003  2039  2273  2609
101  383  479  509  1559  1901  2063  2591  2663
23  29  191  1229  1433  1811  2441  2459  2633

Если мы имеем идеальный квадрат, то мы имеем и соответствующий ему комплект из 4-х точных попарно ортогональных покрытий массива.

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

А для массива из простых чисел мне такой комплект ещё предстоит получить. У меня пока нет ни одного такого комплекта.

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

-- Ср июн 10, 2015 16:12:29 --

Присматриваюсь, приглядываюсь :-)

Обратила внимание, что в каждое из 4-х покрытий входит цепочка, содержащая центральный элемент квадрата - 1361.
Много ли будет цепочек, в которых содержится центральный элемент, а 4 остальные пары комплементарны :?:

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

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение11.06.2015, 16:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Начала писать программку, с большим скрипом получается :-(

Конечно, без программы тут ничего не найдёшь. Ну разве что те найдут, у кого образное мышление очень развито :lol: они то есть в уме могут все эти числа перебирать и проверять ортогональность полученной цепочки двум известным покрытиям.
А я не то что в уме не могу, и по программе-то не сразу :?

Итак,

это точное покрытие № 1 (цепочки-строки, нормализованные):

Код:
311  569  1163  1283  1289  1571  1811  2039  2213
383  593  653  773  1229  1619  2063  2243  2693
89  641  809  821  1499  1709  1979  2003  2699
101  131  173  263  1613  2333  2441  2531  2663
11  113  179  449  1361  2273  2543  2609  2711
59  191  281  389  1109  2459  2549  2591  2621
23  719  743  1013  1223  1901  1913  2081  2633
29  479  659  1103  1493  1949  2069  2129  2339
509  683  911  1151  1433  1439  1559  2153  2411

Это точное покрытие № 2 (цепочки столбцы, нормализованные):

Код:
113  773  1013  1283  1433  1493  1613  1979  2549
179  311  653  719  1499  1559  2339  2459  2531
29  59  101  683  1811  1913  2243  2699  2711
131  281  449  641  1619  2129  2153  2213  2633
389  659  821  1151  1361  1571  1901  2063  2333
89  509  569  593  1103  2081  2273  2441  2591
11  23  479  809  911  2039  2621  2663  2693
191  263  383  1163  1223  2003  2069  2411  2543
173  743  1109  1229  1289  1439  1709  1949  2609

Эти два точных покрытия ортогональные, я взяла их из известного ассоциативного квадрата.

Теперь я хочу найти третье точное покрытие ортогональные этим двум покрытиям. Это будут у меня цепочки-диагонали прямые. Одна цепочка в этом покрытии уже есть - это главная диагональ (соответствующего направления) ассоциативного квадрата:

Код:
23  131  653  1283  1361  1439  2069  2591  2699

С этой цепочкой всё нормально: она имеет точно один общий элемент с каждой цепочкой первого покрытия и с каждой цепочкой второго покрытия.

Далее уже работает программа. Нашла пока одну цепочку и сразу, разумеется, симметричную ей:

Код:
11  59  593  1499  1613  1901  1949  2213  2411
311  509  773  821  1109  1223  2129  2663  2711

Правильно нашла :?:
Господа программисты! Проверьте, пожалуйста!

Сама проверила, вроде всё правильно.

Теперь нужно найти ещё три пары таких цепочек. Это будет полное третье точное покрытие ортогональное первым двум.

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

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение11.06.2015, 18:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ещё пару цепочек (симметричных) нашла, теперь у меня в третьем точном покрытии уже 5 цепочек:

Код:
23  131  653  1283  1361  1439  2069  2591  2699
11  59  593  1499  1613  1901  1949  2213  2411
311  509  773  821  1109  1223  2129  2663  2711
29  113  383  911  1571  1709  2441  2459  2633
89  263  281  1013  1151  1811  2339  2609  2693

Ау, хоть кто-нибудь...
задача-то для хорошего программиста плёвая.
Я туплю при работе с двумерными массивами :oops:

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение12.06.2015, 09:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Всё! На поиске третьей пары цепочек программа ушла в бесконечную задумчивость :-(

Тогда решила протестировать на 4-х известных попарно ортогональных покрытиях (см. их выше).
Ввожу в программу первые два точных покрытия.
Из третьего известна первая цепочка (главная диагональ).
Вторую цепочку задаю искусственно (конкретные параметры для циклов), иначе очень долго идёт поиск (ждать не хочется; может быть, это будет несколько минут, а может, несколько часов - фиг его знает).

Все остальные цепочки программа находит сама в мгновение ока!

Код:
191  449  821  1151  1361  1571  1901  2273  2531
59  101  389  743  1289  2069  2441  2549  2609
509  593  641  683  1109  1223  2339  2459  2693
479  569  659  911  1229  1439  1709  2543  2711
311  521  719  773  839  1163  2591  2633  2699
23  89  131  1559  1883  1949  2003  2201  2411
11  179  1013  1283  1493  1811  2063  2153  2243
29  263  383  1499  1613  2039  2081  2129  2213
113  173  281  653  1433  1979  2333  2621  2663

Сравниваю с известным третьим точным покрытием:

Код:
191  449  821  1151  1361  1571  1901  2273  2531
59  101  389  743  1289  2069  2441  2549  2609
113  173  281  653  1433  1979  2333  2621  2663
11  179  1013  1283  1493  1811  2063  2153  2243
479  569  659  911  1229  1439  1709  2543  2711
23  89  131  1559  1883  1949  2003  2201  2411
311  521  719  773  839  1163  2591  2633  2699
29  263  383  1499  1613  2039  2081  2129  2213
509  593  641  683  1109  1223  2339  2459  2693

Один к одному!

Это был тест.
А в поиске по двум заданным покрытиям из ассоциативного квадрата программа крутилась часа 4 и - ничего! Первые две пары выдаёт, на третьей застревает.

Что делать? Кто подскажет?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение12.06.2015, 10:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот так работает программа и час, и два, и три

Изображение

Как бы это чуть-чуть подтолкнуть? :D

Интересно: для каждой первой пары цепочек находится ровно две вторых пары.
А вот третьей пары не находится ни одной.
Может быть, третьего точного покрытия ортогонального двум введённым в программу и не существует в природе. Трудно искать чёрную кошку в тёмной комнате, особенно если её там нет. Но искать надо :-)

-- Пт июн 12, 2015 12:12:30 --

Появилось некоторое разнообразие: для одной пары цепочек находится и три, и четыре вторых пары цепочек.

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

Поэтому путь этот всё равно плохой. Надо всё начинать с составления базы всех цепочек и уже от этой базы плясать.

-- Пт июн 12, 2015 12:34:43 --

Nataly-Mak в сообщении #1026293 писал(а):
Интересно: для каждой первой пары цепочек находится ровно две вторых пары.

А ничего интересного и нет :lol:
Программа составлена некорректно, и вторые пары получаются одинаковые, только в обратном порядке записаны.

"неуд" за программу :?

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


22/03/08

7154
Саратов
Программа нашла третью пару цепочек! Теперь их уже 7 штук.

Код:
23  131  653  1283  1361  1439  2069  2591  2699
179  263  659  773  1709  1811  2081  2153  2621
101  569  641  911  1013  1949  2063  2459  2543
59  383  809  1103  1559  1613  1901  2213  2609
113  509  821  1109  1163  1619  1913  2339  2663
191  449  743  1151  1493  1499  2039  2243  2441
281  479  683  1223  1229  1571  1979  2273  2531

Но... на последнюю пару цепочек остались следующие числа:

Код:
11  29  89  173  311  389  593  719  1289  1433  2003  2129  2333  2411  2549  2633  2693  2711

Ничего не сложилось :-( если программа мне не врёт.

Продолжу поиск. Может, ещё какой-нибудь вариант найдётся.

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


22/03/08

7154
Саратов
Полный перебор программа выполнила (если не ошиблась в программе).
Третье точное покрытие ортогональное заданным двум точным ортогональным покрытиям не найдено. Ожидаемый результат :!:

Теперь надо начинать с полной базы цепочек. Это технически сложно, по крайней мере, для меня.

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


22/03/08

7154
Саратов
Начать надо, наверное, с цепочек, содержащих центральное число 1361.
Каждый искомый идеальный квадрат должен содержать ровно 4 таких цепочки, причём они будут составлены из различных чисел (не считая, конечно, центральное число).

Пример:

Код:
11  113  179  449  1361  2273  2543  2609  2711
389  659  821  1151  1361  1571  1901  2063  2333
23  131  653  1283  1361  1439  2069  2591  2699
281  383  809  1289  1361  1433  1913  2339  2441

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

Много ли будет таких наборов :?:

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


22/03/08

7154
Саратов
Господа!
Проверьте хотя бы такой элементарный расчёт, правильно я посчитала :?

У нас имеется массив из 80 простых чисел:

Код:
11  23  29  59  89  101  113  131  173  179  191  263  281  311  383  389  449  479  509  569  593  641 
653  659  683  719  743  773  809  821  911  1013  1103  1109  1151  1163  1223  1229  1283  1289  1433  1439 
1493  1499  1559  1571  1613  1619  1709  1811  1901  1913  1949  1979  2003  2039  2063  2069  2081  2129 
2153  2213  2243  2273  2333  2339  2411  2441  2459  2531  2543  2549  2591  2609  2621  2633  2663  2693 
2699  2711

Этот массив состоит из 40 комплементарных пар:

Код:
(11,2711), (23,2699), ..., (1289,1433)

Мы хотим образовать из чисел данного массива все нормализованные цепочки (для магического квдарата порядка 9) , в которых будет содержаться центральное число 1361, а остальные 8 чисел представляют собой 4 комплементарные пары
(все определения даны в стартовом сообщении).

Примеры таких цепочек:

Код:
11  113  179  449  1361  2273  2543  2609  2711
389  659  821  1151  1361  1571  1901  2063  2333
23  131  653  1283  1361  1439  2069  2591  2699
281  383  809  1289  1361  1433  1913  2339  2441

У меня получается, что таких цепочек я смогу образовать 91390.
Это правильно :?:

-- Сб июн 13, 2015 17:29:30 --

Сделала программку, программка выдала мне ровно 91390 цепочек:

Код:
11  23  29  59  1361  2663  2693  2699  2711
11  23  29  89  1361  2633  2693  2699  2711
11  23  29  101  1361  2621  2693  2699  2711
11  23  29  113  1361  2609  2693  2699  2711
11  23  29  131  1361  2591  2693  2699  2711
11  23  29  173  1361  2549  2693  2699  2711
11  23  29  179  1361  2543  2693  2699  2711
11  23  29  191  1361  2531  2693  2699  2711
11  23  29  263  1361  2459  2693  2699  2711
11  23  29  281  1361  2441  2693  2699  2711
11  23  29  311  1361  2411  2693  2699  2711
11  23  29  383  1361  2339  2693  2699  2711
11  23  29  389  1361  2333  2693  2699  2711
11  23  29  449  1361  2273  2693  2699  2711
11  23  29  479  1361  2243  2693  2699  2711
. . . . . . . . . . . . . .
1151  1163  1223  1283  1361  1439  1499  1559  1571
1151  1163  1223  1289  1361  1433  1499  1559  1571
1151  1163  1229  1283  1361  1439  1493  1559  1571
1151  1163  1229  1289  1361  1433  1493  1559  1571
1151  1163  1283  1289  1361  1433  1439  1559  1571
1151  1223  1229  1283  1361  1439  1493  1499  1571
1151  1223  1229  1289  1361  1433  1493  1499  1571
1151  1223  1283  1289  1361  1433  1439  1499  1571
1151  1229  1283  1289  1361  1433  1439  1493  1571
1163  1223  1229  1283  1361  1439  1493  1499  1559
1163  1223  1229  1289  1361  1433  1493  1499  1559
1163  1223  1283  1289  1361  1433  1439  1499  1559
1163  1229  1283  1289  1361  1433  1439  1493  1559
1223  1229  1283  1289  1361  1433  1439  1493  1499
W= 91390

Кажется, всё правильно.

Так, теперь мне нужно образовать все наборы по 4 цепочки из этой базы всех цепочек, так чтобы в каждой паре цепочек из 4-х не было одинаковых чисел (не считая, конечно, центральное число 1361).

Сколько будет таких наборов :?:
Сейчас буду думать, как это подсчитать :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 153 ]  На страницу 1, 2, 3, 4, 5 ... 11  След.

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



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

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


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

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