Вход  •  Регистрация









По вопросам подключения звоните 6-67-20 7(922)515-56-51 -Мегафон 7(912)461-36-10 -МТС 7(904)833-55-28 -Теле2 7(964)180-28-08 -Билайн
с 08:00 до 22:00
пн - пт

с 10:00 до 22:00
сб - вс


Имя пользователя:

Пароль:



Шахматы и математика

Раздел посвященный спорту.

Модераторы: xameleon, APTEMKA

Шахматы и математика

Сообщение #1 Almansor » 13 фев 2007, 19:30

Математические задачи на шахматной доске
Последний раз редактировалось Almansor 24 фев 2007, 22:47, всего редактировалось 1 раз.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #2 Almansor » 13 фев 2007, 19:35

Задача о восьми ферзях.
Расставить на доске восемь ферзей так,чтобы они не угрожали друг другу. Число решений.
Решения представляются в виде (135...),где указываются номера горизонталей в вертикалях,следующих по порядку.
Последний раз редактировалось Almansor 24 фев 2007, 22:38, всего редактировалось 1 раз.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #3 Crocodile » 14 фев 2007, 07:11

Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом?:)

PS Ушел терзать паскаль
Я завидую крокодилам - даже ходят лёжа!

Аватара пользователя
Crocodile
Главный флудер
 
Сообщения: 327
Зарегистрирован: 29 сен 2005, 10:17
Последний визит: 07 июл 2009, 18:21
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пол: Оно
    Неизвестно Неизвестно

Сообщение #4 Crocodile » 14 фев 2007, 07:25

15863724
Я завидую крокодилам - даже ходят лёжа!

Аватара пользователя
Crocodile
Главный флудер
 
Сообщения: 327
Зарегистрирован: 29 сен 2005, 10:17
Последний визит: 07 июл 2009, 18:21
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пол: Оно
    Неизвестно Неизвестно

Сообщение #5 Vanish » 14 фев 2007, 10:33

Математические задачи на шахматной доске

Было дело .. тратил вчемя в пустую 18x13!

Аватара пользователя
Vanish
watcher
 
Сообщения: 237
Зарегистрирован: 17 сен 2005, 22:56
Последний визит: 10 июл 2007, 10:04
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пол: Муж.
Возраст: 40
    Неизвестно Неизвестно

Сообщение #6 Clap » 14 фев 2007, 14:04

В пустую ничего и не когда не бывает

Аватара пользователя
Clap
IRCop
 
Сообщения: 152
Зарегистрирован: 16 дек 2006, 17:37
Последний визит: 04 мар 2011, 22:00
Благодарил (а): 0 раз.
Поблагодарили: 4 раз.
Пол: Муж.
Возраст: 34
    Неизвестно Неизвестно

Сообщение #7 Almansor » 14 фев 2007, 18:55

Crocodile писал:
Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом?

PS Ушел терзать паскаль
Вы сами и ответили на свой вопрос. Кстати, для прграммирования этой задачи лучше подойдет язык Prolog. Программа будет изящнее и быстрее,да и язык своеобразный. Рекомендую по Прологу книгу Бартко. Там приведено схематичное решение. Ваше решение верно. А сколько еще м.б. решений?
Последний раз редактировалось Almansor 24 фев 2007, 22:45, всего редактировалось 1 раз.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #8 Almansor » 14 фев 2007, 18:59

Clap, Вы правы.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #9 Almansor » 14 фев 2007, 19:07

Кстати, задачей о восьми ферзях занимался великий математик Карл Фридрих Гаусс. Наверное, ему нравилось тратить время впустую. Он и нашел все ... решения. Тогда компьютеров и паскалей еще не было.
Последний раз редактировалось Almansor 24 фев 2007, 22:47, всего редактировалось 1 раз.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #10 Almansor » 14 фев 2007, 19:19

Задача о часовых. Какое наименьшее число ферзей можно расставить на шахматной доске при условии, что они держат под обстрелом все свободные поля доски?

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #11 Almansor » 24 фев 2007, 22:43

Где же решения задач. Кроме одного решения, которое привел Crocodile, других решений пока не вижу. И потом,где обещанные программы на паскале, си и прочая! Слабо?

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #12 AzazeL » 24 фев 2007, 23:02

Almansor пишет:Слабо?

Совсем не слабо вопрос времени: 8 вложенных циклов по 64 -
примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали :arrow:

Аватара пользователя
AzazeL
otaku no rida
otaku no rida
 
Сообщения: 2024
Зарегистрирован: 26 янв 2006, 16:45
Последний визит: 12 июл 2009, 21:53
Благодарил (а): 2 раз.
Поблагодарили: 24 раз.
Пол: Муж.
Возраст: 37
    Неизвестно Неизвестно

Сообщение #13 Almansor » 24 фев 2007, 23:14

AzazeL пишет:
Almansor пишет:Слабо?

Совсем не слабо вопрос времени: 8 вложенных циклов по 64 -
примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали :arrow:

О каком времени вы говорите, времени выполнения программы? Предлагаю посмотреть в книгах по искуственному интелекту. Там рассматриваются такие алгоритмы. А без программы пробовали найти решение?

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #14 AzazeL » 25 фев 2007, 02:16

написания; выполняться на современных компах будет моментально
3 часа работы программиста и 100мсек работы программы :) и готово
Ответ:Похоже что 4 - один из них такой :arrow:
Код: Выделить всё
@ - положение ферзя
# - клетка под ударом
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 # # # # # # # #

Аватара пользователя
AzazeL
otaku no rida
otaku no rida
 
Сообщения: 2024
Зарегистрирован: 26 янв 2006, 16:45
Последний визит: 12 июл 2009, 21:53
Благодарил (а): 2 раз.
Поблагодарили: 24 раз.
Пол: Муж.
Возраст: 37
    Неизвестно Неизвестно

Сообщение #15 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 машине и программа тоже выполнялась моментально и выдавала все решения.
Программу посмотрел. А не много ли ферзей в задаче о часовых?
Последний раз редактировалось Almansor 25 фев 2007, 02:50, всего редактировалось 1 раз.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #16 AzazeL » 25 фев 2007, 02:48

Almansor
решений то больше, но они все зеркальные (поворот доски на 0,90,180,270 град; отображение слева направо и сверху вниз): если я ничего не перепутал, то мой ответ 16 [на каждую сторону по 4(номально состояние, отображение вертикальное, отображение горизонтальное, отображение горизонтально-вертикальное)]
Про часовых...ээээ мозг в 4 ночи не думает моё решение было преведено для для случая когда под ударом должы быть все клетки, потом переделаю для всех свободных
Последний раз редактировалось AzazeL 25 фев 2007, 02:55, всего редактировалось 1 раз.

Аватара пользователя
AzazeL
otaku no rida
otaku no rida
 
Сообщения: 2024
Зарегистрирован: 26 янв 2006, 16:45
Последний визит: 12 июл 2009, 21:53
Благодарил (а): 2 раз.
Поблагодарили: 24 раз.
Пол: Муж.
Возраст: 37
    Неизвестно Неизвестно

Сообщение #17 Almansor » 25 фев 2007, 02:52

Azazel
Решений больше! 16 каких? Независимых?

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #18 AzazeL » 25 фев 2007, 02:56

Almansor пишет:Azazel
Решений больше! 16 каких? Независимых?

Зависимых производных от первого

Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024
Других путей решения не вижу, даже если очень подумать, посему лучше сдаться :)

Аватара пользователя
AzazeL
otaku no rida
otaku no rida
 
Сообщения: 2024
Зарегистрирован: 26 янв 2006, 16:45
Последний визит: 12 июл 2009, 21:53
Благодарил (а): 2 раз.
Поблагодарили: 24 раз.
Пол: Муж.
Возраст: 37
    Неизвестно Неизвестно

Сообщение #19 Almansor » 25 фев 2007, 03:13

AzazeL пишет:
Almansor пишет:Azazel
Решений больше! 16 каких? Независимых?

Зависимых производных от первого

Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024
Других путей решения не вижу, даже если очень подумать, посему лучше сдаться :)

Тут несколько независимых решений. Остальные получаются поворотами и отражениями. Всего менее 100 решений. Ферзи конечно без номерков. Рано сдаетесь. Попробуйте еще.

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно

Сообщение #20 AzazeL » 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 и скорее всего оно одно 8)

Аватара пользователя
AzazeL
otaku no rida
otaku no rida
 
Сообщения: 2024
Зарегистрирован: 26 янв 2006, 16:45
Последний визит: 12 июл 2009, 21:53
Благодарил (а): 2 раз.
Поблагодарили: 24 раз.
Пол: Муж.
Возраст: 37
    Неизвестно Неизвестно

Сообщение #21 Almansor » 25 фев 2007, 15:46

:D Отлично, Azazel, Вы полностью решили задачу о восьми ферзях. Число решений правильно. Проверил выборочно случайным образом несколько решений. Остался маленький штрих. Сколько из 92 решений независимых.
Задача о ферзях-часовых.В общем случае задача о ферзях часовых является очень сложной. Оценки для минимального числа P(n) ферзей-часовых,охраняющих все свободные поля доски nxn:
n/2 - 1/2 <= P(n) <= 5n/8 + 16 sqrt(n). Число решений для доски 8х8 более 4000.
А кто еще решит эти задачи?

Аватара пользователя
Almansor
Сильный медведь
 
Автор темы
Сообщения: 697
Зарегистрирован: 10 фев 2007, 00:39
Последний визит: 02 июл 2014, 00:26
Откуда: из СССР
Благодарил (а): 24 раз.
Поблагодарили: 23 раз.
Пол: Муж.
Возраст: 70
    Неизвестно Неизвестно



Список форумов Хобби и интересы Спорт

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

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