Форум программистов, компьютерный форум, киберфорум
Комбинаторика
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.63/64: Рейтинг темы: голосов - 64, средняя оценка - 4.63
34 / 25 / 8
Регистрация: 16.11.2019
Сообщений: 179

Определить количество расстановок ладей на шахматной доске

10.02.2020, 20:16. Показов 11754. Ответов 27
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
какое кол-во способ расставить ладей на шахматную доску, так чтобы они били все свободные поля?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.02.2020, 20:16
Ответы с готовыми решениями:

Сколькими способами можно разместить на шахматной доске восемь ладей?
Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они смогли сьесть друг друга. Помогите пж-ста. ...

Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга?
Помогите решить, задачу,если есть возможность объяснить первый шаг решения задачи,или общий ход решения. Сколькими способами можно...

Генерация списка всех возможных расстановок максимального количества ладей на доске N x N клеток
Добрый вечер, я в хаскелле новичок помогите пожалуйста решить задачу о расстановке ладьей на шахматной доске. Для кого-то может быть...

27
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
10.02.2020, 21:56
=88

Добавлено через 1 минуту
Нет, я не прав. Погорячился. Подумать надо.

Добавлено через 6 минут
Похоже, что так: 2*88 - 8!
Но уверенности нет...
1
Эксперт по математике/физике
 Аватар для jogano
6358 / 4065 / 1512
Регистрация: 09.10.2009
Сообщений: 7,550
Записей в блоге: 4
10.02.2020, 22:10
8! - 8 ладей должны стоять так, чтобы попарно не бить друг друга. Каждая ладья занимает какою-то строку и какой-то столбец. Если строки перебирать по очереди 1-2-...-8, то для 1й строки можно поставить ладью в любой из 8-и столбцов, ладью во 2й строке - в любой из оставшихся 7-и столбцов и так далее.

Если придираться к условию, то ТС-у следовал бы оговорить, что ладей должно быть минимальное количество, а то так можно в каждую клетку поставить по ладье и каждая клетка будет бита, а это один способ.

Цитата Сообщение от Байт Посмотреть сообщение
=88
Если нет условия на то, что ладьи не должны бить друг друга и их минимальное количество, то да. Это уже вопрос к ТС-у, который даёт размытое условие.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
10.02.2020, 23:07
Цитата Сообщение от jogano Посмотреть сообщение
размытое условие.
Да, есть такое дело. И я его, грешным делом, дополнил (для себя), что ладей должно быть 8. Ибо меньше не получится. Но ответ 88 неверен, потому как учитывает расстановку всех по одной горизонтали, но не учитывает ту же вертикальную расстановку. Короче, "включения-исключения" в деле. Но вот как-то уверенности нет....
0
Любитель математики
 Аватар для angor6
1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
10.02.2020, 23:08
Цитата Сообщение от Байт Посмотреть сообщение
Похоже, что так: https://www.cyberforum.ru/cgi-bin/latex.cgi?2*8^8 - 8!
Если мне память не изменяет и я правильно понимаю сформулированную задачу, то ответ именно таков. Конечно, если принять, что количество ладей минимально для контроля над всеми полями шахматной доски.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
10.02.2020, 23:15
Цитата Сообщение от angor6 Посмотреть сообщение
то ответ именно таков.
Память, не память, но интуиция подсказывает такой ответ.
Ход рассуждений. Посчитаем конфигурации, когда на каждой горизонтали одна ладья. Потом те, где по ладье на каждой вертикали. Случай не бьющихся ладей мы посчитали дважды. Но "не аккуратненько как-то"
0
Любитель математики
 Аватар для angor6
1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
10.02.2020, 23:36
К сожалению, я ошибся. Упомянутый мной ответ относится к следующей задаче: "Сколькими способами можно расставить 8 ладей, которые не могли бы бить друг друга, на доске размера 8×8?" Однако, поскольку в данном случае нет указания, что ладьи не должны бить друг друга, то их можно расставить и в один ряд. Поэтому количество вариантов расстановки увеличивается.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
10.02.2020, 23:40
Цитата Сообщение от angor6 Посмотреть сообщение
количество вариантов расстановки увеличивается.
Энто-то ясно. Но вот насколько?
0
Любитель математики
 Аватар для angor6
1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
11.02.2020, 00:09
Байт, наверное, нужно дождаться более точной формулировки задачи от автора вопроса, чтобы избавиться от неопределённости, указанной в сообщениях выше.
0
34 / 25 / 8
Регистрация: 16.11.2019
Сообщений: 179
11.02.2020, 08:54  [ТС]
Какое кол-во вариантов поставить ладей на шахматную доску, так что бы они били все свободные клетки доски(ладьи могут бить друг-друга)
Напишите подробное решение)
0
Эксперт по математике/физике
4183 / 3051 / 918
Регистрация: 19.11.2012
Сообщений: 6,196
11.02.2020, 10:38
Цитата Сообщение от _qikert Посмотреть сообщение
бить друг-друга
Если нет условия на количество ладей, то придется делать так.
Ясно, что на доске должно быть не менее 8 ладей (8 горизонталей должны пробиваться). Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.). Оставшиеся 56 полей можно заполнить ладьями 256 способами (поле занято или нет). Итого получается
8!*256.
Если я нигде не ошибся, это и есть ответ.

Цитата Сообщение от _qikert Посмотреть сообщение
свободные поля?
Вот тебе раз - клон нашелся. Смотрим и мой вариант здесь
у меня получилось 8!*256

Добавлено через 28 минут
Нет, таки ошибся. Некоторые варианты подсчитаны дважды и даже больше.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2020, 11:15
Цитата Сообщение от kabenyuk Посмотреть сообщение
Некоторые варианты подсчитаны дважды и даже больше.
А некоторые не подсчитаны вообще. Например, 8 ладей с линию.

Добавлено через 1 минуту
А по поводу формулировки... Давайте ограничимся 8-ю ладьями, ибо при большем их количестве как-то в звдачке мало смысла...
0
Эксперт по математике/физике
4183 / 3051 / 918
Регистрация: 19.11.2012
Сообщений: 6,196
11.02.2020, 12:59
Цитата Сообщение от Байт Посмотреть сообщение
Например, 8 ладей с линию.
Нет, все подсчитано, только толку от этого никакого. Н-да, коварная оказалась задача.
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2020, 15:09
Цитата Сообщение от kabenyuk Посмотреть сообщение
Нет, все подсчитано,
Простите, не увидел.
Цитата Сообщение от kabenyuk Посмотреть сообщение
Расположить 8 ладей таким способом, чтобы они били все свободные клетки можно 8! способами (на первую горизонталь ладью можно поставить 8-ю способами, на вторую - 7-ю и т.д.).
Вот тут-то и пропущен вариант "8 в линию" Как и многие другие. Типа
a1 b1 c2 d2 e3 f3 g2 h1

Добавлено через 19 минут
Все-таки я склоняюсь к ответу 8*(222 - 7!)
0
Любитель математики
 Аватар для angor6
1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
11.02.2020, 15:14
Я предполагаю следующее:
1) минимальное количество ладей, которое нужно расставить на обычной шахматной доске, чтобы они контролировали все поля, равно восьми;
2) восемь ладей контролируют все поля шахматной доски, если
а) они расставлены по одной на каждой из восьми горизонталей (это можно сделать https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8 способами, причём на одной вертикали может стоять и больше одной ладьи;
б) они расставлены по одной на каждой из восьми вертикалей (это можно сделать https://www.cyberforum.ru/cgi-bin/latex.cgi?8^8 способами, причём на одной горизонтали может стоять и больше одной ладьи.

Среди указанных выше способов дважды учтены расстановки, при которых на каждой горизонтали и каждой вертикали стоит по одной ладье. Количество таких расстановок равно https://www.cyberforum.ru/cgi-bin/latex.cgi?(8!)^2{.} В самом деле первую ладью можно поставить на любое из https://www.cyberforum.ru/cgi-bin/latex.cgi?64 полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из https://www.cyberforum.ru/cgi-bin/latex.cgi?49 полей, на которые можно поставить вторую ладью, и т. д. Значит, рассматриваемых расстановок существует https://www.cyberforum.ru/cgi-bin/latex.cgi?64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4 \cdot 1=(8!)^2{.}

Если расставить восемь ладей так, чтобы хотя бы на одной горизонталям и хотя бы на одной вертикали было больше чем одна ладья, то не все поля шахматной доски будут под контролем.

Следовательно, существует https://www.cyberforum.ru/cgi-bin/latex.cgi?2 \cdot 8^8-(8!)^2 способов, которыми можно расставить на обычной шахматной доске восемь ладей так, чтобы они контролировали все поля.
1
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2020, 15:38
Цитата Сообщение от angor6 Посмотреть сообщение
В самом деле первую ладью можно поставить на любое из 64 полей; вычёркивая вертикаль и горизонталь, которые контролирует эта ладья, получим квадрат из 49
Посмотрите внимательнее на свои рассуждения. Мне кажется, там ошибка. Одну и ту же расстановку считаете много раз.
У вас расстановки a1 b2 и b2 a1 считаются за разные.
Чтобы проверить себя, можно потренироваться на доске 3 х 3

Добавлено через 7 минут
Цитата Сообщение от angor6 Посмотреть сообщение
2) восемь ладей контролируют все поля шахматной доски, если
А вот этот пункт совершенно верен. И именно его мне не хватало! Спасибо!
1
Любитель математики
 Аватар для angor6
1492 / 1002 / 285
Регистрация: 27.01.2014
Сообщений: 3,350
11.02.2020, 15:40
Байт,

Не по теме:

нет, тренироваться я не стану: возраст уже не тот. Нужно смириться с тем, что комбинаторные задачи относятся к числу недостижимых для меня высот. :)

Спасибо за указание на ошибку!
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2020, 15:42
angor6,
Цитата Сообщение от Байт Посмотреть сообщение
на доске 3 х 3
Даже на доске 2 х 2 можно убедиться. Ваши рассуждения дадут 4. А в самом деле - 6
0
2797 / 1843 / 202
Регистрация: 05.06.2011
Сообщений: 5,357
11.02.2020, 15:44
Закину таки ещё вариант.
Разобьём варианты расстановки на три непересекающихся класса:
— присутствуют пустые вертикали (в каждой горизонтали кто-нить да стоит);
— присутствуют пустые горизонтали (в каждой вертикали...);
— нет ни пустых вертикалей, ни горизонталей.
Вариант 1, по формуле включений-исключений https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=\sum\limits_{k=1}^7(-1)^{k-1}C_8^k8^{8-k}
Поскольку https://www.cyberforum.ru/cgi-bin/latex.cgi?(8-1)^8=\sum\limits_{k=0}^8(-1)^{k-1}C_8^k8^{8-k}, https://www.cyberforum.ru/cgi-bin/latex.cgi?N_1=1+8^8-7^8.
Дальше — удвоить и добавить https://www.cyberforum.ru/cgi-bin/latex.cgi?8! (это я не ору, это факториал).
Или я не Винни-Пух. А я — он, значит, всё в порядке.
Или всё же не он?
0
Диссидент
Эксперт C
 Аватар для Байт
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2020, 15:52

Не по теме:

Цитата Сообщение от angor6 Посмотреть сообщение
возраст уже не тот
Да ну? Готов поспорить, что я на пару годков постарше! Давайте так. Каждый год - кружка пива. Идет?:D



Добавлено через 7 минут
Цитата Сообщение от iifat Посмотреть сообщение
это я не ору, это факториал
Да и никто не орет. Это нам еще поперло, что факториалы не двойные...
А по делу. N1 - это ответ? ... Не, кажись ответ 2N1 + 8! , да?
Но чегой-то сложно получается. И не похоже.
А чем вас мой ответ не устраивает?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
11.02.2020, 15:52
Помогаю со студенческими работами здесь

Получить m расстановок 8 ферзей на шахматной доске
Дано натуральное число m. Получить m расстановок 8 ферзей на шахматной доске, при которых ни один из ферзей не угрожает другому. Если m...

Расставить n ладей на шахматной доске n*n
Вообщем нужно расставить n ладей на шахматной доске n*n Вот то что у меня получилось: #pragma argsused #include<iostream.h> ...

Расстановка 8 ладей на шахматной доске (рекурсивно)
Народ, помогите пожалуйста с этой проблемой. Всё сделал. Работает, но вот только я итеративно сделал, может кто подскажет как это сделать,...

Расположить на шахматной доске восемь ладей
Восемь ладей. Расположить на шахматной доске восемь ладей так, чтобы при этом каждая клетка оказалась либо занятой, либо под угрозой...

Получите все расстановки 8 ладей на шахматной доске
Получите все расстановки 8 ладей на шахматной доске , при которых ни одна ладья не угрожает другой


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Не удержался от оценки концепции двигателя Стирлинга.
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
Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер