Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 4210 ]  На страницу Пред.  1 ... 45, 46, 47, 48, 49, 50, 51 ... 421  След.
Автор Сообщение
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 07:24 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
svb
опробовала вашу программу. Класс!
Ввела в качестве исходного ДЛК Брауна (в первоначальном виде).
Программа выдала 5504 трансверсалей.
М-н-о-о-о-г-о-о :)

Теперь надо научиться выбирать в этом массиве наборы по 10 непересекающихся трансверсалей.
Если эту операцию удастся выполнять так же быстро, как поиск всех трансверсалей, будет здорово.
Алгоритм поиска пары ОДЛК по заданному ДЛК будет реализован!

А. Белышев пишет, что у Кнута всё подробно расписано, как из 808 трансверсалей выбрать 10 неперескающихся.
Осилим? :)

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 07:36 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Проверила программу svb для ЛК Паркера из книги Кнута.
Программа нашла 808 трансверсалей

Изображение

Результат выдаётся мгновенно!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 07:41 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Avgust
для вашего квадратика программа нашла 4224 трансверсали, поменьше, чем для ДЛК Брауна, но вполне достаточно, чтобы среди них оказался нужный набор из 10 неперескающихся трансверсалей.

Теперь вам задачка прямо в лоб :)
Все трансверсали для вашего ДЛК найдите по программе svb. Это одно мгновение.
А потом среди этих трансверсалей ищите 10 неперескающихся. Как найдёте, так новая пара ОДЛК будет построена - для преобразованного квадрата Брауна.

Можете написать программу для выбора из заданного массива n трансверсалей 10 неперекающихся?


Последний раз редактировалось Nataly-Mak 29 фев 2016, 08:04, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 07:51 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Для ДЛК, построенного методом Гергели,

0 1 2 3 4 5 6 7 8 9
8 2 6 4 0 9 5 3 7 1
2 3 4 9 8 1 0 5 6 7
3 4 0 8 7 2 1 9 5 6
5 0 8 2 3 6 7 1 9 4
6 5 9 1 2 7 8 0 4 3
7 6 5 0 1 8 9 4 3 2
1 7 3 5 9 0 4 6 2 8
9 8 7 6 5 4 3 2 1 0
4 9 1 7 6 3 2 8 0 5

программа нашла 2816 трансверсалей.

Вот хороший пример для тестирования следующей программы - выбора комплекта из 10 непересекающихся трансверсалей.
Форумчанин на форуме boinc.ru проверил этот квадрат и написал, что у него нет ортогонального соквадрата.
Это значит, что среди всех 2816 трансверсалей нет 10 непересекающихся.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 08:16 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Вот ещё пример для тестирования - пара ОДЛК, найденная в проекте SAT@home

ДЛК №1

0 1 2 3 4 5 6 7 8 9
2 4 9 7 0 3 5 1 6 8
9 7 1 5 6 4 8 3 0 2
1 0 8 6 9 2 7 4 5 3
8 6 5 0 7 1 3 2 9 4
6 3 4 9 2 8 0 5 1 7
5 9 7 8 3 0 2 6 4 1
3 8 0 4 5 7 1 9 2 6
7 5 6 2 1 9 4 8 3 0
4 2 3 1 8 6 9 0 7 5

ДЛК №2

0 1 2 3 4 5 6 7 8 9
4 9 1 5 6 0 2 8 7 3
2 0 7 8 9 1 5 4 3 6
5 2 9 4 8 3 1 6 0 7
7 5 4 1 3 2 9 0 6 8
1 8 0 7 5 6 4 3 9 2
9 3 6 0 1 7 8 2 5 4
6 4 8 2 7 9 3 5 1 0
8 6 3 9 0 4 7 1 2 5
3 7 5 6 2 8 0 9 4 1

Для ДЛК №1 программа svb выдала 820 трансверсалей.
(Близко к количеству трансверсалей в ЛК Паркера.)

Набор из 10 непересекающихся трансверсалей я нашла по программе А. Белышева:

0 6 3 2 1 4 7 8 5 9
1 8 7 5 2 9 4 3 0 6
2 4 6 3 0 5 8 1 9 7
3 0 4 7 9 8 1 6 2 5
4 9 1 6 8 0 5 2 7 3
5 2 8 0 4 3 9 7 6 1
6 7 9 4 5 1 2 0 3 8
7 5 0 1 3 2 6 9 8 4
8 3 5 9 7 6 0 4 1 2
9 1 2 8 6 7 3 5 4 0

Как утверждают ребята с проекта, у ДЛК №1 только один ортогональный соквадрат, значит, комплект из 10 непересекающихся трансверсалей только один. Вот надо его выбрать из 820 известных трансверсалей.

Замечание: в программке А. Белышева в качестве исходного введён ДЛК №2, а в качестве ортогонального соквадрата - ДЛК №1.

#include <iostream>

using namespace std;

int sokvadrat[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{2,4,9,7,0,3,5,1,6,8},
{9,7,1,5,6,4,8,3,0,2},
{1,0,8,6,9,2,7,4,5,3},
{8,6,5,0,7,1,3,2,9,4},
{6,3,4,9,2,8,0,5,1,7},
{5,9,7,8,3,0,2,6,4,1},
{3,8,0,4,5,7,1,9,2,6},
{7,5,6,2,1,9,4,8,3,0},
{4,2,3,1,8,6,9,0,7,5}};

int ishodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{4,9,1,5,6,0,2,8,7,3},
{2,0,7,8,9,1,5,4,3,6},
{5,2,9,4,8,3,1,6,0,7},
{7,5,4,1,3,2,9,0,6,8},
{1,8,0,7,5,6,4,3,9,2},
{9,3,6,0,1,7,8,2,5,4},
{6,4,8,2,7,9,3,5,1,0},
{8,6,3,9,0,4,7,1,2,5},
{3,7,5,6,2,8,0,9,4,1}};

int otvet[10][10];

int main(){
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
otvet[sokvadrat[i][j]][i] = ishodn[i][j];
}
}
cout << endl;
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
cout << otvet[i][j] << (j != 9 ? ' ' : '\n');
}
}
cout << endl;
}


Поэтому набор 10 неперескающихся трансверсалей может быть другой.

P. S. А для ДЛК №2 программа svb нашла 840 трансверсалей.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 08:37 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Кстати, об ортогональных соквадратах для каждого из ДЛК известной пары.
Вот есть пара ОДЛК Брауна:

ДЛК №1

0 1 2 3 4 5 6 7 8 9
5 4 1 2 6 9 7 0 3 8
2 3 8 7 9 4 5 6 1 0
3 0 5 9 8 7 2 1 4 6
6 9 3 5 2 8 1 4 0 7
7 2 4 8 1 6 0 3 9 5
8 6 9 0 7 1 3 2 5 4
9 8 7 1 0 2 4 5 6 3
1 5 6 4 3 0 9 8 7 2
4 7 0 6 5 3 8 9 2 1

ДЛК №2

0 1 2 3 4 5 6 7 8 9
2 3 4 9 8 1 0 5 6 7
3 4 9 8 2 7 1 0 5 6
8 7 6 5 0 9 4 3 2 1
5 0 1 7 6 3 2 8 9 4
6 5 0 1 7 2 8 9 4 3
4 9 8 2 3 6 7 1 0 5
7 6 5 0 1 8 9 4 3 2
9 8 7 6 5 4 3 2 1 0
1 2 3 4 9 0 5 6 7 8

ДЛК №1 имеет только одного ортогонального собрата (это показанный тут ДЛК №2).

А вот ДЛК №2 (знаменитый квадрат Брауна) имеет аж 4 ортогональных соквадрата!

Поэтому надо проверять оба ДЛК в известной паре ОДЛК.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 09:53 
Не в сети
Продвинутый
Зарегистрирован:
27 фев 2016, 23:19
Сообщений: 50
Cпасибо сказано: 5
Спасибо получено:
25 раз в 15 сообщениях
Очков репутации: 10

Добавить очки репутацииУменьшить очки репутации
Программа для поиска ортогональных квадратов с исходником на паскале
Lat02
Lat02.exe - программа для поиска трансверсалей и ортогональных квадратов
латинского квадрата со стороной 10.

a41.txt, q1.txt - примеры исходных латинских квадратов.

После запуска программа запрашивает имя файла с латинским квадратом
и максимальное число выводимых ортогональных квадратов.
Затем выводится исходный квадрат и строка с количеством трансверсалей
в блоках. Последнее число - общее количество трансверсалей.

Создается файл:
trans.txt - набор трансверсалей для исходного квадрата.

Трансверсаль h[0],h[1],...,h[9] - это набор ячеек квадрата с координатами
[0,h[0]],[1,h[1]],...,[9,h[9]]

После этого начинается поиск ортогональных квадратов,
ort.txt - ортогональные квадраты.

Примечание.
Квадрат q1.txt взят из книги:
Кнут Д. Искусство программирования. Том 4А.
Для этого квадрата находится только один ортогональный квадрат.

Для квадрата A41.txt квадратов очень много, поэтому пришлось ввести
ограничение на максимальное число выводимых квадратов.
Кроме этого, в начало файла ort.txt записывается строка со значением
номера начальной трансверсали блока 0, с которой начинается перебор.
Новое значение этого номера можно записать в файл lat.ini, тогда
программа начнет работать с этого номера.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю svb "Спасибо" сказали:
Nataly-Mak
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 10:17 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
svb писал(а):
Программа для поиска ортогональных квадратов с исходником на паскале
Lat02

Высший пилотаж! :Bravo:
Ввела ДЛК Брауна и max=5, программа выдала 5 ортогональных квадратов.
Я даже испугалась сначала - откуда 5, когда должно быть всего 4?
Посмотрела на квадраты, а они... не диагональные. То есть программа ищет все ортогонгальные соквадраты для заданного - и диагональные, и не диагональные. Класс!
И для ДЛК Гергели нашла 2 обычных ортогональных ЛК, и для квадрата, который Avgust изобрёл тоже нашла обычные ортогональные ЛК - 2 шт.

Теперь осталось совсем немного - выбирать из всего множества построенных ортогональных ЛК диагональные, потому что у нас задача: строить пары ОДЛК (ортогональных диагональных латинских квадратов).

svb
наверное, можно, вашей программе дать такое задание: строить только диагональные ортогональные ЛК.
Сделать вариант программы для ДЛК.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 10:23 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7460
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
645 раз в 565 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Ах, да...
теперь можно приступать к решению задачи века :)
найти тройку попарно ортогональных ЛК 10-го порядка.
Программа выдаёт для заданного ЛК целую кучу ортогональных соквадратов. Но вот... взаимно ортогональных среди них не находится. А вдруг и найдутся.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 29 фев 2016, 10:25 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13564
Откуда: Москва
Cпасибо сказано: 1291
Спасибо получено:
3625 раз в 3182 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak, то, что в подправленном квадрате Брауна 4224 трансверсалей (число палиндромное! ) - для меня полная неожиданность. Это же жутко много. Проги svb у меня нет, увы, самому писать долго будет. Гораздо проще это сделать Вам. Ведь только пару раз Enter нажать. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.    На страницу Пред.  1 ... 45, 46, 47, 48, 49, 50, 51 ... 421  След.  Страница 48 из 421 [ Сообщений: 4210 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
О теме "Отрогональные латинские квадраты 10-го порядка"

в форуме Предложения, Замечания, Обратная связь

Nataly-Mak

21

2646

14 июн 2018, 05:28

Ортогональные векторы

в форуме Векторный анализ и Теория поля

kala12

2

273

02 ноя 2021, 15:04

Ортогональные собственные вектора

в форуме Аналитическая геометрия и Векторная алгебра

HJey

0

252

18 апр 2019, 23:18

Ортогональные центральные композиционный план

в форуме Исследование операций и Задачи оптимизации

AHAHAC

2

488

08 дек 2016, 09:20

Ряд Фурье и другие ортогональные разложения

в форуме Ряды Фурье и Интегральные преобразования

Chelovekley

1

515

29 апр 2015, 14:47

Обобщенные вещественно ортогональные формы в радиосвязи

в форуме Линейная и Абстрактная алгебра

mike84

2

593

14 июн 2015, 13:37

Доказать, что ортогональные проекции вершин н-мерного куба

в форуме Геометрия

Arzybek

13

587

18 сен 2020, 21:29

Квадраты

в форуме Интересные задачи участников форума MHP

Krash

20

864

18 июл 2021, 17:46

Квадраты и степени

в форуме Теория чисел

ammo77

1

319

23 дек 2019, 01:08

Квадраты в окружности

в форуме Начала анализа и Другие разделы школьной математики

nerzul88

8

622

20 май 2020, 09:48


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2024 MathHelpPlanet.com. All rights reserved