Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
| Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
|
Страница 45 из 421 |
[ Сообщений: 4210 ] | На страницу Пред. 1 ... 42, 43, 44, 45, 46, 47, 48 ... 421 След. |
|
| Автор | Сообщение | |
|---|---|---|
| Nataly-Mak |
|
|
|
Берём в качестве исходного ДЛК Брауна 0 8 5 1 7 3 4 6 9 2 Нет у нас пока всех его трансверсалей. Сколько всех, мы не знаем. Надо их искать, но я пока не знаю, как писать программу, хотя знаю, как их искать вручную. Зато могу предложить набор из 46 трансверсалей, тут есть найденные мной вручную и найденные по программе Алексея (по известным ортогональным парам). Вот эти трансверсали: ▼
Вот такой небольшой набор, всего 46 трансверсалей. Попробуйте написать программу, которая выберет из этого набора ровно 4 комплекта из 10 непересекающихся трансверсалей. Они тут есть. На простой задаче легче просекать пути решения. Надо придумать методу и не одну. И каждую опробовать на этом простом примере. Посмотреть, какая будет лучше работать. Первый этап - нахождение всех трансверсалей пока пропустила. Но там, как мне кажется, проще. Я вот даже визуально нашла 8 трансверсалей. Это же и вручную понятно, как искать. Двигаемся по строкам сверху вниз и выбираем элементы в лексикографическом порядке. Или же выбор удачно завершится до последней строки, или же зайдём в тупик. Последний раз редактировалось Nataly-Mak 28 фев 2016, 20:47, всего редактировалось 1 раз. |
||
| Вернуться к началу | ||
| ivashenko |
|
|||||||||||||||||||||||||
|
Есть ЛК:
1,2,3,4 2,1,4,3 3,4,1,2 4,3,2,1 и ортогональный ему: 1,2,3,4 3,4,1,2 4,3,2,1 2,1,4,3 Выпишем все трансверсали первого ОЛК: 1,3,4,2 1,4,2,3 2,4,3,1 2,3,1,4 3,1,2,4 3,2,4,1 4,2,1,3 4,1,3,2 Всего нашлось их 8, поправьте если не так. Нетрудно найти непересекающиеся трансверсали: 1,3,4,2 3,1,2,4 2,4,3,1 4,2,1,3 Однако нам необходимо найти их с помощью метода, а не простым перебором. Точнее необходимо придумать эффективный метод. Рассортируем все 8 трансверсалей следующим образом: В первый столбец поместим трансверсали отсортированные по первому разряду, а в первую строку- отсортированные по значениям второго разряда, на пересечении строк и столбцов запишем пересечение множеств в соответствующих ячейках:
На второстепенной диагонали 4 непересекающиеся трансверсали, вне нее еще одно множество из 4-х непересекающихся трансверсалей. На главной диагонали располагаются тривиальные нули. Нужно пробовать еще для других квадратов и искать закономерность. Может это конечно и просто совпадение. |
||||||||||||||||||||||||||
| Вернуться к началу | ||||||||||||||||||||||||||
| За это сообщение пользователю ivashenko "Спасибо" сказали: Nataly-Mak |
||||||||||||||||||||||||||
| Nataly-Mak |
|
|
|
ivashenko
у вас неплохо получилось с ЛК 4-го порядка. Вы видели ссылку на книгу Кнута на русском языке? (svb выложил) Мне коллега Белышев пишет, чтобы я смотрела в этой книге алгоритм "танцующих связей". Там описывается, как из всех 808 трансверсалей выбрать 10 непересекающихся. Это быстро делается. И в этом наборе из 808 трансверсалей есть только один комплект из 10 непересекающихся трансверсалей. Значит, есть только один ЛК ортогональный данному. Но я и сама ещё не начинала разбираться с этим алгоритмом. Посмотрите, я думаю, у вас получится. Avgust, bimol и вы тоже посмотрите. Ну, должны же мы осилить этот метод. Паркер за 45 минут решал эту задачу на машине 50 лет назад. |
||
| Вернуться к началу | ||
| bimol |
|
|
|
Стал смотреть как в книге Кнута строится первая трансверсаль 0214365897.
Если строить слева направо как в книге то 5 и 7 в одной строке, если сверху вниз то 14 в одном столбце. Что за выверт. Возвращаюсь к построению Т у Брауна |
||
| Вернуться к началу | ||
| Nataly-Mak |
|
|
|
svb писал(а): Приятное чтение (на русском) для вхождения в историю латинских квадратов: Д.Кнут, т.4А Я скачала книгу, пошла читать Да, сейчас ещё выложу ссылку, которую мне Алексей прислал, на алгоритм "танцующих связей" в Википедии. Потанцуем? ![]() |
||
| Вернуться к началу | ||
| bimol |
|
|
|
Вот что выдает моя корявая программа для Брауна
Может на этот раз хоть трансверсали правильные |
||
| Вернуться к началу | ||
| Nataly-Mak |
|
|
|
bimol писал(а): Стал смотреть как в книге Кнута строится первая трансверсаль 0214365897. Если строить слева направо как в книге то 5 и 7 в одной строке, если сверху вниз то 14 в одном столбце. Что за выверт. Возвращаюсь к построению Т у Брауна Да, плохо, что у Кнута трансверсали строятся по столбцам. Я уже привыкла двигаться по строкам сверху вниз и перепривыкать трудно Буду и дальше так искать.Но, в принципе, от этого ничего не должно измениться, трансверсалей должно быть столько же. Ну, а потом из них выбираем непересекающиеся. |
||
| Вернуться к началу | ||
| Nataly-Mak |
|
|
|
bimol писал(а): Вот что выдает моя корявая программа для Брауна Уточните, пожалуйста, какой у вас Браун - нормализованный или нет? Я проверю трансверсали. |
||
| Вернуться к началу | ||
| bimol |
|
|
|
Чтобы не путаться, стал искать как на этой странице, изначальный не нормализованный.
|
||
| Вернуться к началу | ||
| Nataly-Mak |
|
|
|
Здесь алгоритм "танцующих связей"
https://en.wikipedia.org/wiki/Dancing_Links Здесь пример реализации https://github.com/blynn/dlx Эх-ма, всё на английском Ну, тут все вроде читают по-английски, кроме меня. |
||
| Вернуться к началу | ||
|
На страницу Пред. 1 ... 42, 43, 44, 45, 46, 47, 48 ... 421 След. | [ Сообщений: 4210 ] |
| Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
|---|---|---|---|---|
| О теме "Отрогональные латинские квадраты 10-го порядка" | 21 |
2646 |
14 июн 2018, 05:28 |
|
|
Ортогональные векторы
в форуме Векторный анализ и Теория поля |
2 |
273 |
02 ноя 2021, 15:04 |
|
| Ортогональные собственные вектора | 0 |
252 |
18 апр 2019, 23:18 |
|
| Ортогональные центральные композиционный план | 2 |
488 |
08 дек 2016, 09:20 |
|
| Ряд Фурье и другие ортогональные разложения | 1 |
515 |
29 апр 2015, 14:47 |
|
|
Обобщенные вещественно ортогональные формы в радиосвязи
в форуме Линейная и Абстрактная алгебра |
2 |
593 |
14 июн 2015, 13:37 |
|
|
Доказать, что ортогональные проекции вершин н-мерного куба
в форуме Геометрия |
13 |
587 |
18 сен 2020, 21:29 |
|
| Квадраты | 20 |
864 |
18 июл 2021, 17:46 |
|
|
Квадраты и степени
в форуме Теория чисел |
1 |
319 |
23 дек 2019, 01:08 |
|
|
Квадраты в окружности
в форуме Начала анализа и Другие разделы школьной математики |
8 |
622 |
20 май 2020, 09:48 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: 3axap и гости: 2 |
| Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |