|
|
|
dm9 |
|
|||
Дмитрий Копытин Профиль Группа: Vingrad developer Сообщений: 3876 Регистрация: 22.7.2002 Где: Москва Репутация: нет Всего: 137 |
AISIN, ну вот я тебе скажу, что таких кроссвордов очень много в газетах
На чисто-человеческой логике ты сделаешь, это не интересно. А вот такие задачки порешать программно - это уже требует неких затрат серого вещества ) Я вот не знаю, как решать такие задачи. Подумаю на досуге. Подняли старый вопрос, самому захотелось додумать проблему |
|||
|
||||
dvs |
|
|||
Владимир Драпалюк Профиль Группа: Участник Клуба Сообщений: 660 Регистрация: 25.8.2003 Где: Воронеж->Москв а Репутация: нет Всего: 19 |
эх, рекурсия, рекурсия... бул там алгоритм, чей-то на рекурсии. Не помню из-за чего, но так и не осознал как работает....
-------------------- Любите друг друга! |
|||
|
||||
fess |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 17.2.2005 Где: г. Мурманск, Росс ия Репутация: нет Всего: 3 |
Когда встречаются неоднозначные случаи, то необходимо использовать перебор и выводить все варианты решения.
--------------------
Компьютер не подчиняется законам физики. Только в нём глюки возникают из ничего, файлы исчезают в никуда, а объём измеряется в метрах и называется весом. |
|||
|
||||
dm9 |
|
|||
Дмитрий Копытин Профиль Группа: Vingrad developer Сообщений: 3876 Регистрация: 22.7.2002 Где: Москва Репутация: нет Всего: 137 |
fess, перебор как? 2^S вариантов, где S - число клеточек?
|
|||
|
||||
dvs |
|
|||
Владимир Драпалюк Профиль Группа: Участник Клуба Сообщений: 660 Регистрация: 25.8.2003 Где: Воронеж->Москв а Репутация: нет Всего: 19 |
dm9 ты меня пугаешь... Нет конечно, нужно учитывать значения количества закрашенных.
-------------------- Любите друг друга! |
|||
|
||||
dm9 |
|
|||
Дмитрий Копытин Профиль Группа: Vingrad developer Сообщений: 3876 Регистрация: 22.7.2002 Где: Москва Репутация: нет Всего: 137 |
Дык вот это и задача как раз... перебор, но умный.
Одну клеточку поставили, остальное довели логикой. Опять тупик - ещё клеточку поставили. Пришли к противоречию - идём на шаг назад. Только, мне кажется, долго получится всё равно. В общем, надо пробовать на практике, так оценить я затрудняюсь |
|||
|
||||
~FoX~ |
|
|||
НЕ рыжий!!! Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
Хех, товарисчи, так у вас ничего не выйдет. Если кроссворд имеет более одного решения, то мы упираемся в задачу распознания и идонтифицирования образов.
|
|||
|
||||
dvs |
|
|||
Владимир Драпалюк Профиль Группа: Участник Клуба Сообщений: 660 Регистрация: 25.8.2003 Где: Воронеж->Москв а Репутация: нет Всего: 19 |
~FoX~ расскажи подробнее, как это ты представляешь?
-------------------- Любите друг друга! |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Собсно алгоритм несложен.
Имеем по каждой вертикали и горизонтали количество закрашенных клеток. Просматриваем каждую. На каждом шаге. Самый простой вариант - по одной из вертикалей или горизонталей имеется однозначное соответствие (с учетом на текущий момент известных клеток) - тогда клетки красятся и вновь возвращаемся к просмотру. Более сложный вариант - однозначности нет. Тогда приходится делать предположения - т.е. ветвимся. Соответственно наиболее выгодное ветвление - на минимальное количество веток, причем каждая ветка рассматривается уже как окончательная (и она придет либо к решению, либо к противоречию/неоднозначности и будет отсечена). Т.е. приходим к обычному рекурсивному спуску с отсечениями - фактически полный перебор. Несколько ускорить процесс могут генетические алгоритмы выбора ветви - но это гораздо более сложно в программной реализации. Хотя и возможно. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
~FoX~ |
|
|||
НЕ рыжий!!! Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
dvs15
Я на самом деле себе это плохо представляю, но вот есть у нас кросворд в котормо более одного решения, на рисунке которого изображен допустим квадрат малевича вид под углом в 18 градусов. При решении возникает вероятная точка внутри квадрата или вне него, допустим в левом нижнем углу поля. Алгоритмически и тот и другой вариант допустимы и более того они оба правильные. Естественно взглянув человеческим глазом мы безошибочно определим правильный вариант, а вот как это сделать программно я не знаю |
|||
|
||||
dvs |
|
|||
Владимир Драпалюк Профиль Группа: Участник Клуба Сообщений: 660 Регистрация: 25.8.2003 Где: Воронеж->Москв а Репутация: нет Всего: 19 |
Интересно, а если задумка автора другая? ИМХО, таких кроссвордов быть не должно. -------------------- Любите друг друга! |
|||
|
||||
AISIN |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 185 Регистрация: 27.1.2005 Где: Пушкино Репутация: нет Всего: 1 |
Akina Ты прав! Только если кроссворд большой по времени слишком долго будет работать!
--------------------
Внимание!!! Внимание!!!Запущена программа по завоеванию мира!!!Выполненно 0,000000000000000000000000000000000000000000000000000002% |
|||
|
||||
dvs |
|
|||
Владимир Драпалюк Профиль Группа: Участник Клуба Сообщений: 660 Регистрация: 25.8.2003 Где: Воронеж->Москв а Репутация: нет Всего: 19 |
Главное чтобы работал.
Очень давно, когда писали программу, тестировали для разных кроссвордов (больших тоже). Так вот, рекурсивный алгоритм какого-то дяди "умирал" для очень больших тестов (по понятным причинам). А наш работал дольше, но делал своё дело. -------------------- Любите друг друга! |
|||
|
||||
AISIN |
|
||||
Бывалый Профиль Группа: Участник Сообщений: 185 Регистрация: 27.1.2005 Где: Пушкино Репутация: нет Всего: 1 |
Ну вобщем тыкаем случайным образом в любую ячейку массива и закрашиваем её. Потом смотрим вокруг ячейки по вертикали и горизонтали (соседние ячейки)если больше ничего не надо красить то отмечаем крестик! Далее спускаемся по диагонали допустим вправо - вниз если вышли за границы масива то случайно тыкаем в любую другую незаполненую клетку и закрашиваем ее проверяя соседние (вдруг их тоже надо красить?) а если не вышли за пределы массива то смело красим текущуу ячейку проверяем все вокруг и спускаемся по диагонали! Хорошо бы вести .log файл, если возникнут проблемы можно откатить все назад до проблемной ячейки и проблемную ячейку пометить крестиком! Это сообщение отредактировал(а) AISIN - 12.5.2005, 23:04 --------------------
Внимание!!! Внимание!!!Запущена программа по завоеванию мира!!!Выполненно 0,000000000000000000000000000000000000000000000000000002% |
||||
|
|||||
dm9 |
|
|||
Дмитрий Копытин Профиль Группа: Vingrad developer Сообщений: 3876 Регистрация: 22.7.2002 Где: Москва Репутация: нет Всего: 137 |
AISIN, ну, собственно, это описал сначала я, а потом Акина.
Принципиально новые предложение ещё ни у кого не завалялись? |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |