Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.04.2021, 03:35   #1
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
Восклицание Задача о 8 ферзях с помощью алгоритма Лас Вегас

Здравствуйте, подскажите , пожалуйста, как можно реализовать алгоритм для задачи о 8 ферзях (где условие такое, что ферзи не должны бить друг друга) с помощью алгоритма Лас Вегас на с++
polygraph вне форума Ответить с цитированием
Старый 18.04.2021, 03:39   #2
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
По умолчанию

Немного материала нашёл
можно применить алгоритм Лас-Вегаса; на самом деле это более эффективно, чем возврат. Разместите 8 ферзей на шахматной доске, чтобы никто не напал на другую. Помните, что ферзь атакует другие фигуры в том же ряду, столбце и диагоналях. Предположим, что k строк, 0 ≤ k ≤ 8, успешно заняты ферзями. Если k = 8, то остановимся успешно. В противном случае перейдите к строке k + 1. Подсчитайте все позиции в этом ряду, не атакованные существующими ферзями. Если таковых нет, то не получится. В противном случае выберите один случайным образом, увеличьте k и повторите. Обратите внимание, что алгоритмы просто не работают, если ферзь не может быть размещен. Но этот процесс можно повторять, и каждый раз будет генерироваться другая аранжировка.
polygraph вне форума Ответить с цитированием
Старый 19.04.2021, 02:45   #3
Desc
Участник клуба
 
Аватар для Desc
 
Регистрация: 21.11.2007
Сообщений: 1,063
По умолчанию

Так а алгоритм Лас-Вегас как выглядит.
Или тот бред, посом выше, и есть алгоритм.
Если так, то как могут столько ферзей разместиться на одном поле?
I am not a wizard, I am just learning.
Desc вне форума Ответить с цитированием
Старый 19.04.2021, 04:37   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Если верить Вики (ссылка), то алгоритм Лас-Вегаса:
Цитата:
Выполнить алгоритм A с результатом r до тех пор, пока K(r) не будет истиной.
А текст выше описывает сами алгоритмы A и K. На питоне это будет выглядеть примерно так:
Код:
from random import randint

def f(k, e):
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        return True
    candidates = []
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            candidates.append((i, k))
    if candidates:
        e.append(candidates[randint(0, len(candidates) - 1)])
        res = f(k + 1, e)
        if res:
            return True
    return False

def main():
    while True:
        res = f(0, [])
        if res:
            break

main()
На плюсы уж как-нибудь сами переложите
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 21.04.2021, 09:45   #5
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
По умолчанию

Цитата:
Сообщение от Desc Посмотреть сообщение
Так а алгоритм Лас-Вегас как выглядит.
Или тот бред, посом выше, и есть алгоритм.
Если так, то как могут столько ферзей разместиться на одном поле?
Тот бред, который выше, это алгоритм
polygraph вне форума Ответить с цитированием
Старый 21.04.2021, 10:01   #6
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
По умолчанию

Цитата:
Сообщение от BDA Посмотреть сообщение
Если верить Вики (ссылка), то алгоритм Лас-Вегаса:

А текст выше описывает сами алгоритмы A и K. На питоне это будет выглядеть примерно так:
Код:
from random import randint

def f(k, e):
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        return True
    candidates = []
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            candidates.append((i, k))
    if candidates:
        e.append(candidates[randint(0, len(candidates) - 1)])
        res = f(k + 1, e)
        if res:
            return True
    return False

def main():
    while True:
        res = f(0, [])
        if res:
            break

main()
На плюсы уж как-нибудь сами переложите
Подскажите, как можно все решения задачи вывести на экран и показать количество решений?
Для задачи 8х8 это будет 92 решения. там почему-то 60 решений показало

Последний раз редактировалось polygraph; 21.04.2021 в 10:29.
polygraph вне форума Ответить с цитированием
Старый 21.04.2021, 15:50   #7
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Цитата:
Сообщение от polygraph Посмотреть сообщение
Для задачи 8х8 это будет 92 решения. там почему-то 60 решений показало
Да, вроде, 92 и показало.
Код:
from random import randint

sols = 0

def f(k, e):
    global sols
    if k == 8:
        print(e)
        for x, _ in e:
            print(('-' * x) + '*' + ('-' * (7 - x)))
        sols += 1
        return
    for i in range(8):
        for x, y in e:
            if x == i or abs(y - k) == abs(x - i):
                break
        else:
            new_e = list(e)
            new_e.append((i, k))
            f(k + 1, new_e)

def main():
    f(0, [])
    print("solutions:", sols)

main()
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 21.04.2021, 16:21   #8
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
По умолчанию

BDA, спасибо большое
polygraph вне форума Ответить с цитированием
Старый 21.04.2021, 16:54   #9
polygraph
Пользователь
 
Регистрация: 18.04.2021
Сообщений: 10
По умолчанию

BDA, ещё, подскажите, в алгоритме Лас Вегас как я понял, должно же быть рандомное заполнение доски ферзями и проверять бьет ли ферзь другого или нет. Так же? А то я просто я не увидел это до 2 программе
polygraph вне форума Ответить с цитированием
Старый 21.04.2021, 18:11   #10
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Ну да, во второй программе нет рандома, а перебор с возвратом. Только первая программа реализует алгоритм Лас Вегас. Просто таким способом искать все возможные решения может быть достаточно долго.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача о 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