34 / 25 / 8
Регистрация: 16.11.2019
Сообщений: 179
|
|
Определить количество расстановок ладей на шахматной доске10.02.2020, 20:16. Показов 11754. Ответов 27
Метки нет Все метки)
(
0
|
10.02.2020, 20:16 | |
Ответы с готовыми решениями:
27
Сколькими способами можно разместить на шахматной доске восемь ладей?
Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток |
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
10.02.2020, 21:56 | |
=88
Добавлено через 1 минуту Нет, я не прав. Погорячился. Подумать надо. ![]() Добавлено через 6 минут Похоже, что так: 2*88 - 8! Но уверенности нет...
1
|
![]() ![]() |
|
10.02.2020, 22:10 | |
8! - 8 ладей должны стоять так, чтобы попарно не бить друг друга. Каждая ладья занимает какою-то строку и какой-то столбец. Если строки перебирать по очереди 1-2-...-8, то для 1й строки можно поставить ладью в любой из 8-и столбцов, ладью во 2й строке - в любой из оставшихся 7-и столбцов и так далее.
Если придираться к условию, то ТС-у следовал бы оговорить, что ладей должно быть минимальное количество, а то так можно в каждую клетку поставить по ладье и каждая клетка будет бита, а это один способ. Если нет условия на то, что ладьи не должны бить друг друга и их минимальное количество, то да. Это уже вопрос к ТС-у, который даёт размытое условие.
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
10.02.2020, 23:07 | |
Да, есть такое дело. И я его, грешным делом, дополнил (для себя), что ладей должно быть 8. Ибо меньше не получится. Но ответ 88 неверен, потому как учитывает расстановку всех по одной горизонтали, но не учитывает ту же вертикальную расстановку. Короче, "включения-исключения" в деле. Но вот как-то уверенности нет....
![]()
0
|
Любитель математики
![]() 1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
|
|
10.02.2020, 23:08 | |
Если мне память не изменяет и я правильно понимаю сформулированную задачу, то ответ именно таков. Конечно, если принять, что количество ладей минимально для контроля над всеми полями шахматной доски.
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
10.02.2020, 23:15 | |
Память, не память, но интуиция подсказывает такой ответ.
Ход рассуждений. Посчитаем конфигурации, когда на каждой горизонтали одна ладья. Потом те, где по ладье на каждой вертикали. Случай не бьющихся ладей мы посчитали дважды. Но "не аккуратненько как-то" ![]()
0
|
Любитель математики
![]() 1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
|
|
10.02.2020, 23:36 | |
К сожалению, я ошибся. Упомянутый мной ответ относится к следующей задаче: "Сколькими способами можно расставить 8 ладей, которые не могли бы бить друг друга, на доске размера 8×8?" Однако, поскольку в данном случае нет указания, что ладьи не должны бить друг друга, то их можно расставить и в один ряд. Поэтому количество вариантов расстановки увеличивается.
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
10.02.2020, 23:40 | |
0
|
![]() 4183 / 3051 / 918
Регистрация: 19.11.2012
Сообщений: 6,196
|
|
11.02.2020, 10:38 | |
Если нет условия на количество ладей, то придется делать так.
Ясно, что на доске должно быть не менее 8 ладей (8 горизонталей должны пробиваться). Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.). Оставшиеся 56 полей можно заполнить ладьями 256 способами (поле занято или нет). Итого получается 8!*256. Если я нигде не ошибся, это и есть ответ. Вот тебе раз - клон нашелся. Смотрим и мой вариант здесь у меня получилось 8!*256 Добавлено через 28 минут Нет, таки ошибся. Некоторые варианты подсчитаны дважды и даже больше.
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.02.2020, 11:15 | |
А некоторые не подсчитаны вообще. Например, 8 ладей с линию.
Добавлено через 1 минуту А по поводу формулировки... Давайте ограничимся 8-ю ладьями, ибо при большем их количестве как-то в звдачке мало смысла...
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.02.2020, 15:09 | |
Простите, не увидел.
Вот тут-то и пропущен вариант "8 в линию" Как и многие другие. Типа
a1 b1 c2 d2 e3 f3 g2 h1 ![]() Добавлено через 19 минут Все-таки я склоняюсь к ответу 8*(222 - 7!) ![]()
0
|
Любитель математики
![]() 1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
|
|
11.02.2020, 15:14 | |
Я предполагаю следующее:
1) минимальное количество ладей, которое нужно расставить на обычной шахматной доске, чтобы они контролировали все поля, равно восьми; 2) восемь ладей контролируют все поля шахматной доски, если а) они расставлены по одной на каждой из восьми горизонталей (это можно сделать б) они расставлены по одной на каждой из восьми вертикалей (это можно сделать Среди указанных выше способов дважды учтены расстановки, при которых на каждой горизонтали и каждой вертикали стоит по одной ладье. Количество таких расстановок равно Если расставить восемь ладей так, чтобы хотя бы на одной горизонталям и хотя бы на одной вертикали было больше чем одна ладья, то не все поля шахматной доски будут под контролем. Следовательно, существует
1
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.02.2020, 15:38 | |
Посмотрите внимательнее на свои рассуждения. Мне кажется, там ошибка. Одну и ту же расстановку считаете много раз.
У вас расстановки a1 b2 и b2 a1 считаются за разные. Чтобы проверить себя, можно потренироваться на доске 3 х 3 ![]() Добавлено через 7 минут А вот этот пункт совершенно верен. И именно его мне не хватало! Спасибо!
1
|
Любитель математики
![]() 1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
|
|
11.02.2020, 15:40 | |
Байт,
Не по теме: нет, тренироваться я не стану: возраст уже не тот. Нужно смириться с тем, что комбинаторные задачи относятся к числу недостижимых для меня высот. :)
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.02.2020, 15:42 | |
angor6,
Даже на доске 2 х 2 можно убедиться. Ваши рассуждения дадут 4. А в самом деле - 6
0
|
2797 / 1843 / 202
Регистрация: 05.06.2011
Сообщений: 5,357
|
|
11.02.2020, 15:44 | |
Закину таки ещё вариант.
Разобьём варианты расстановки на три непересекающихся класса: — присутствуют пустые вертикали (в каждой горизонтали кто-нить да стоит); — присутствуют пустые горизонтали (в каждой вертикали...); — нет ни пустых вертикалей, ни горизонталей. Вариант 1, по формуле включений-исключений Поскольку Дальше — удвоить и добавить Или я не Винни-Пух. А я — он, значит, всё в порядке. Или всё же не он?
0
|
Диссидент
![]() ![]() 27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
11.02.2020, 15:52 | |
Не по теме: Да ну? Готов поспорить, что я на пару годков постарше! Давайте так. Каждый год - кружка пива. Идет?:D Добавлено через 7 минут Да и никто не орет. ![]() А по делу. N1 - это ответ? ... Не, кажись ответ 2N1 + 8! , да? Но чегой-то сложно получается. И не похоже. А чем вас мой ответ не устраивает?
0
|
11.02.2020, 15:52 | ||||||
Помогаю со студенческими работами здесь
20
Расставить n ладей на шахматной доске n*n Расстановка 8 ладей на шахматной доске (рекурсивно) Расположить на шахматной доске восемь ладей
Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
|
Метод с двумя буферами (или double buffering) или ping-pong buffering
Hrethgir 02.04.2025
Из ответов LM модели.
Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .
|
На любовном киберфронте
Alexander-7 01.04.2025
Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка:
«Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
|
Как работает Node.js изнутри
run.dev 29.03.2025
Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
|
Моки в Python: Mock Object Library
py-thonny 29.03.2025
Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
|
JavaScript: Управление памятью и улучшение производительности
run.dev 29.03.2025
В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .
|
Мультитенантная архитектура со SpringBoot и PostgreSQL
ArchitectMsa 29.03.2025
SaaS-приложения редко обслуживают одного клиента и обычно они должны поддерживать множество организаций, каждая из которых работает в своём изолированном пространстве. Мультитенантная архитектура. . .
|
std::span в C++: Производительность и лучшие практики
NullReferenced 28.03.2025
std::span — одно из самых недооценённых нововведений стандарта C++20, которое радикально меняет подход к работе с непрерывными последовательностями данных. По сути, это невладеющее представление. . .
|
Многопоточность в C#: Threadpool
UnmanagedCoder 28.03.2025
Пул потоков в C# — это коллекция заранее созданных и готовых к использованию потоков, которые находятся в распоряжении приложения. Вместо того чтобы создавать и уничтожать потоки для каждой небольшой. . .
|
Вопросы на собеседованиях по микросервисам
ArchitectMsa 27.03.2025
Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .
|