|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
18.04.2021, 03:35 | #1 |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
Задача о 8 ферзях с помощью алгоритма Лас Вегас
Здравствуйте, подскажите , пожалуйста, как можно реализовать алгоритм для задачи о 8 ферзях (где условие такое, что ферзи не должны бить друг друга) с помощью алгоритма Лас Вегас на с++
|
18.04.2021, 03:39 | #2 |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
Немного материала нашёл
можно применить алгоритм Лас-Вегаса; на самом деле это более эффективно, чем возврат. Разместите 8 ферзей на шахматной доске, чтобы никто не напал на другую. Помните, что ферзь атакует другие фигуры в том же ряду, столбце и диагоналях. Предположим, что k строк, 0 ≤ k ≤ 8, успешно заняты ферзями. Если k = 8, то остановимся успешно. В противном случае перейдите к строке k + 1. Подсчитайте все позиции в этом ряду, не атакованные существующими ферзями. Если таковых нет, то не получится. В противном случае выберите один случайным образом, увеличьте k и повторите. Обратите внимание, что алгоритмы просто не работают, если ферзь не может быть размещен. Но этот процесс можно повторять, и каждый раз будет генерироваться другая аранжировка. |
19.04.2021, 02:45 | #3 |
Участник клуба
Регистрация: 21.11.2007
Сообщений: 1,063
|
Так а алгоритм Лас-Вегас как выглядит.
Или тот бред, посом выше, и есть алгоритм. Если так, то как могут столько ферзей разместиться на одном поле?
I am not a wizard, I am just learning.
|
19.04.2021, 04:37 | #4 | |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,342
|
Если верить Вики (ссылка), то алгоритм Лас-Вегаса:
Цитата:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
|
21.04.2021, 09:45 | #5 |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
|
21.04.2021, 10:01 | #6 | |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
Цитата:
Для задачи 8х8 это будет 92 решения. там почему-то 60 решений показало Последний раз редактировалось polygraph; 21.04.2021 в 10:29. |
|
21.04.2021, 15:50 | #7 | |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,342
|
Цитата:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
|
21.04.2021, 16:21 | #8 |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
BDA, спасибо большое
|
21.04.2021, 16:54 | #9 |
Пользователь
Регистрация: 18.04.2021
Сообщений: 10
|
BDA, ещё, подскажите, в алгоритме Лас Вегас как я понял, должно же быть рандомное заполнение доски ферзями и проверять бьет ли ферзь другого или нет. Так же? А то я просто я не увидел это до 2 программе
|
21.04.2021, 18:11 | #10 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,342
|
Ну да, во второй программе нет рандома, а перебор с возвратом. Только первая программа реализует алгоритм Лас Вегас. Просто таким способом искать все возможные решения может быть достаточно долго.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача о 8 ферзях. Перехват исключений. | nevender | Помощь студентам | 0 | 02.04.2016 16:19 |
Задача о 8 ферзях | Morfik1 | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 03.06.2013 07:59 |
Задача о ферзях. | FCShadow | Помощь студентам | 0 | 04.06.2011 23:56 |
программирование на Си(задача о ферзях) | osichev | Помощь студентам | 4 | 04.10.2009 18:55 |