Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Магический квадрат из домино 4 на 4
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию Магический квадрат из домино 4 на 4 - 21.12.2005, 20:43

Помогите!
Дан комплект домино. Составить из n него магических квадратов 4 на 4. Полный перебор не получается (в домино 28 костяшек, из которых 21 может лежать другой стороной=> 49**7 шагов... многовато).

У кого, какие мысли - поделитесь!
Ответить с цитированием
  (#2 (permalink)) Старый
wils0n wils0n вне форума
Member
 
Сообщений: 186
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.11.2005
По умолчанию 22.12.2005, 03:09

Может ограничить перебор. И перебирать по магическому числу (МЧ), учитывая, что
1. в МК должно принимать участие не менее 5 различных чисел, так как в противном случае мы не сможем покрыть его доминошками.
2. из 1. следует , что не существует МК с магическим числом <= 6
3. по всей видимости по тем же соображениям следует , что не существует МК с магическим числом >=18

Отсюда перебор по МЧ от 7 до 17 с учётом 1.

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

Ответить с цитированием
  (#3 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 22.12.2005, 16:43

Цитата:
Originally posted by wils0n
[b]2. из 1. следует , что не существует МК с магическим числом <= 6
Хм...
0 0 2 3
1 2 1 1
3 0 2 0
1 3 0 1

Написал перебором. Если n небольшое (<1000), то это не очtym долго.

Спасибо.
Ответить с цитированием
  (#4 (permalink)) Старый
wils0n wils0n вне форума
Member
 
Сообщений: 186
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.11.2005
По умолчанию 22.12.2005, 17:26

Цитата:
Originally posted by Fuud
[b]Хм...
0 0 2 3
1 2 1 1
3 0 2 0
1 3 0 1
Ага...Что-то я пропустил момент, что есть фишки с одинаковыми числами. В любом случае квадратов такого вида будет мало. Основная часть квадратов будет иметь МЧ больше 5.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Магический квадрат 3х3 MiHanick Prolog 48 24.04.2015 18:14
Задача Домино key_rv Prolog 9 05.12.2012 21:17
Домино!!! Temoxa Prolog 5 16.04.2011 19:17
Домино на C++Builder Ушастик C++ Builder 1 22.11.2010 01:20
Домино zorro Prolog 10 09.12.2009 13:38
Магический Квадрат qu1et Общетематический 13 08.11.2008 19:31
Максимальная цепочка в Домино imported_Любитель Prolog 4 30.12.2007 14:34
Пирамида из домино Flowerrr Prolog 2 30.10.2007 00:57
Алгоритм Домино где его найти sashar2 Алгоритмы 5 16.09.2006 08:45
Магический квадрат где найти исходники к этой программы Хиларион Delphi 6 28.04.2005 17:40
Магический квадрат как его описать Dian Игры разума 15 19.04.2005 10:37
Пирамида из домино Forestt Prolog 4 08.02.2005 15:18



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов