|
Тема |
алгоритми за решаване [re: Cпac] |
|
Автор |
Orнeдишaщ (Змей) |
|
Публикувано | 17.01.02 10:29 |
|
|
Абе и моят е примитивен, ама щом питаш, да ти кажа.
Ето алгоритъмът, с който измъдрих комбинациите само с лист и молив:
1) нарисувах един куб
2) номерирах ръбовете (a,b,...,l)
3) понеже всички ръбове са равностойни, няма значение кой е първият бял; избрах си той да е "a"
4) за останалите два остават (11 над 2) = 55 комбинации - написах ги (bc,bd,...,kl)
5) проверих ги една по една. Не е толкова дълго, колкото изглежда. Всяка нова си я рисувах. Ако е хирална, веднага си рисувам и огледалния и образ. За повечето много бързо се вижда, че се повтарят. Изобщо, не ми отне много време.
Тая работа върви на ръка, защото комбинациите са сравнително малко (55). Ако обаче смяташ да боядисаш 6 ръба в един цвят и 6 - в друг, този бабешки метод не върви, тъй като комбинациите са вече 462 и не е ясно, кои съвпадат след симетрична операция на преобразуване. Тогава бих използвал компютър. Да кажем, ще използвам такъв алгоритъм:
1) правя списък на всички операции на симетрия в куба (има справочници за целта)
2) генерирам всички комбинации; маркирам ги като неброени; броят на търсените различни комбинации е 0
3) ако няма повече неброени комбинации, задачата е решена
4) иначе вземам първата неброена комбинация и я добавям към списъка на търсените различни комбинации; увеличавам броя им с 1; маркирам избраната комбинация като броена
5) прилагам всички операции на симетрия към избраната комбинация и маркирам получените комбинации като броени
6) продължавам от стъпка 3)
Това сигурно може и да се оптимизира още за скорост, ама нейсе.
Между другото, примитивните методи са по-надеждни!Редактирано от Orнeдишaщ на 17.01.02 10:31.
|
| |
|
|
|