Форум Глазовских локальных домашних сетей |
Полная версия | Вход • Регистрация |
FAQ • Поиск |
Список форумов » Хобби и интересы » Спорт |
Пред. тема | След. тема Страница 1 из 1 [ Сообщений: 21 ] |
Начать новую тему | Ответить |
Версия для печати |
Шахматы и математика |
---|
Шахматы и математика |
Almansor - Сильный медведь |
13 фев 2007, 19:30 |
Математические задачи на шахматной доске
|
Последнее сообщение |
Almansor - Сильный медведь |
13 фев 2007, 19:35 |
Задача о восьми ферзях.
Расставить на доске восемь ферзей так,чтобы они не угрожали друг другу. Число решений. Решения представляются в виде (135...),где указываются номера горизонталей в вертикалях,следующих по порядку. |
Crocodile - Главный флудер |
14 фев 2007, 07:11 |
Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом?:)
PS Ушел терзать паскаль |
Crocodile - Главный флудер |
14 фев 2007, 07:25 |
15863724
|
Vanish - watcher |
14 фев 2007, 10:33 |
Цитата Математические задачи на шахматной доске
Было дело .. тратил вчемя в пустую 18x13! |
Clap - IRCop |
14 фев 2007, 14:04 |
В пустую ничего и не когда не бывает
|
Almansor - Сильный медведь |
14 фев 2007, 18:55 |
Crocodile писал:
Цитата Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом? Вы сами и ответили на свой вопрос. Кстати, для прграммирования этой задачи лучше подойдет язык Prolog. Программа будет изящнее и быстрее,да и язык своеобразный. Рекомендую по Прологу книгу Бартко. Там приведено схематичное решение. Ваше решение верно. А сколько еще м.б. решений?PS Ушел терзать паскаль |
Almansor - Сильный медведь |
14 фев 2007, 18:59 |
Clap, Вы правы.
|
Almansor - Сильный медведь |
14 фев 2007, 19:07 |
Кстати, задачей о восьми ферзях занимался великий математик Карл Фридрих Гаусс. Наверное, ему нравилось тратить время впустую. Он и нашел все ... решения. Тогда компьютеров и паскалей еще не было.
|
Almansor - Сильный медведь |
14 фев 2007, 19:19 |
Задача о часовых. Какое наименьшее число ферзей можно расставить на шахматной доске при условии, что они держат под обстрелом все свободные поля доски?
|
Almansor - Сильный медведь |
24 фев 2007, 22:43 |
Где же решения задач. Кроме одного решения, которое привел Crocodile, других решений пока не вижу. И потом,где обещанные программы на паскале, си и прочая! Слабо?
|
AzazeL - otaku no rida |
24 фев 2007, 23:02 |
Almansor пишет Слабо?
Совсем не слабо вопрос времени: 8 вложенных циклов по 64 - примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали |
Almansor - Сильный медведь |
24 фев 2007, 23:14 |
AzazeL пишет Almansor пишет Слабо? Совсем не слабо вопрос времени: 8 вложенных циклов по 64 - примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали О каком времени вы говорите, времени выполнения программы? Предлагаю посмотреть в книгах по искуственному интелекту. Там рассматриваются такие алгоритмы. А без программы пробовали найти решение? |
AzazeL - otaku no rida |
25 фев 2007, 02:16 |
написания; выполняться на современных компах будет моментально
3 часа работы программиста и 100мсек работы программы и готово Ответ:Похоже что 4 - один из них такой Код @ - положение ферзя # - клетка под ударом 0 - клетка свободна 1 2 3 4 5 6 7 8 a # # # # # @ # # b @ # # # # # # # c # # # # @ # # # d # @ # # # # # # e # # # # # # # @ f # # @ # # # # # g # # # # # # @ # h # # # @ # # # # Так и не понял как оформляется ответ - решил нарисовать. Almansor пишет Задача о часовых Ответ: Похоже что 7 (возможных решений 3*4=12) (решено программно) Код 1 2 3 4 5 6 7 8 a X # # # # # # # b X # # # # # # # c X # # # # # # # d X # # # # # # # e X # # # # # # # f X # # # # # # # g X # # # # # # # h # # # # # # # # 1 2 3 4 5 6 7 8 a X X # # # # # # b X # # # # # # # c X # # # # # # # d X # # # # # # # e X # # # # # # # f X # # # # # # # g # # # # # # # # h # # # # # # # # 1 2 3 4 5 6 7 8 a X # # # # # # # b X # # # # # # X c X # # # # # # # d X # # # # # # # e X # # # # # # # f X # # # # # # # g # # # # # # # # h # # # # # # # # |
Almansor - Сильный медведь |
25 фев 2007, 02:37 |
AzazeL пишет написания; выполняться на современных компах будет моментально
3 часа работы программиста и 100мсек работы программы и готово Ответ: 4 - один из них такой... Так и не понял как оформляется ответ - решил нарисовать. Вы привели 1 решение и утверждаете, что их 4? Правильно я Вас понял? Число решений не 4,а больше. Далее решение оформляется так: если считать положения ферзей как { (1,y1), (2,y2), ... }, где цифры означают номера вертикалей,а y1,y2,...y8 - номера горизонталей, то опустив номера вертикалей, которые всегда будут одинаковые, получаем следующее оформление решения: y1,y2,y3,y4,y5,y6,y7,y8. Можно через пробел или через запятую. Думаю, что вы быстро внесете соответствующие изменения в программу. Желаю успеха! Программу еще не смотрел. Кстати,я писал когда-то программу на 486 машине и программа тоже выполнялась моментально и выдавала все решения. Программу посмотрел. А не много ли ферзей в задаче о часовых? |
AzazeL - otaku no rida |
25 фев 2007, 02:48 |
Almansor
решений то больше, но они все зеркальные (поворот доски на 0,90,180,270 град; отображение слева направо и сверху вниз): если я ничего не перепутал, то мой ответ 16 [на каждую сторону по 4(номально состояние, отображение вертикальное, отображение горизонтальное, отображение горизонтально-вертикальное)] Про часовых...ээээ мозг в 4 ночи не думает моё решение было преведено для для случая когда под ударом должы быть все клетки, потом переделаю для всех свободных |
Almansor - Сильный медведь |
25 фев 2007, 02:52 |
Azazel
Решений больше! 16 каких? Независимых? |
AzazeL - otaku no rida |
25 фев 2007, 02:56 |
Almansor пишет Azazel
Решений больше! 16 каких? Независимых? Зависимых производных от первого Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024 Других путей решения не вижу, даже если очень подумать, посему лучше сдаться |
Almansor - Сильный медведь |
25 фев 2007, 03:13 |
AzazeL пишет Almansor пишет Azazel Решений больше! 16 каких? Независимых? Зависимых производных от первого Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024 Других путей решения не вижу, даже если очень подумать, посему лучше сдаться Тут несколько независимых решений. Остальные получаются поворотами и отражениями. Всего менее 100 решений. Ферзи конечно без номерков. Рано сдаетесь. Попробуйте еще. |
AzazeL - otaku no rida |
25 фев 2007, 11:50 |
Переделал задачу о 8 ферзях получилось что вариантов - 92:
42736851,52473861,35286471,36428571,57138642,46831752,36814752,53847162 57413862,41586372,36418572,47531682,64285713,64718253,17468253,68241753 62714853,47185263,58417263,48157263,27581463,17582463,25741863,42751863 57142863,64158273,51468273,52617483,63728514,27368514,73168524,51863724 15863724,36815724,63175824,75316824,73825164,53172864,25713864,36258174 61528374,83162574,28613574,57263184,36275184,62713584,37286415,63724815 42736815,71386425,16837425,38471625,63741825,74286135,46827135,26174835 24683175,36824175,63184275,84136275,48136275,26831475,72631485,36271485 47382516,48531726,35841726,42857136,57248136,74258136,82417536,72418536 51842736,41582736,52814736,37285146,31758246,82531746,35281746,35714286 52468317,63581427,58413627,42586137,46152837,63185247,53168247,42861357 63571428,64713528,47526138,57263148 Программа получилась красивая и коротакая, но выполняется оч. долго ~35сек Задача про часовых решение: перебор со случайной расстановкой фигур (оказался достаточно эффективным) для 5 фигур были получены решения интуиция подсказывает, что есть решение для 4 и скорее всего оно одно |
Almansor - Сильный медведь |
25 фев 2007, 15:46 |
Отлично, Azazel, Вы полностью решили задачу о восьми ферзях. Число решений правильно. Проверил выборочно случайным образом несколько решений. Остался маленький штрих. Сколько из 92 решений независимых.
Задача о ферзях-часовых.В общем случае задача о ферзях часовых является очень сложной. Оценки для минимального числа P(n) ферзей-часовых,охраняющих все свободные поля доски nxn: n/2 - 1/2 <= P(n) <= 5n/8 + 16 sqrt(n). Число решений для доски 8х8 более 4000. А кто еще решит эти задачи? |
Вернуться к началу |
Начать новую тему | Ответить |
Страница 1 из 1 [ Сообщений: 21 ] Пред. тема | След. тема |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0 |
Список форумов » Хобби и интересы » Спорт |
Полная версия |
STG-Mobile Style © 2008 STG Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group phpBB-Mobile © 2008 STG Русская поддержка phpBB |