Поиск:

Ответ в темуСоздание новой темы Создание опроса
> японский кросворд 
:(
    Опции темы
dm9
Дата 11.5.2005, 00:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дмитрий Копытин
****


Профиль
Группа: Vingrad developer
Сообщений: 3876
Регистрация: 22.7.2002
Где: Москва

Репутация: нет
Всего: 137



AISIN, ну вот я тебе скажу, что таких кроссвордов очень много в газетах smile

На чисто-человеческой логике ты сделаешь, это не интересно. А вот такие задачки порешать программно - это уже требует неких затрат серого вещества smile) Я вот не знаю, как решать такие задачи. Подумаю на досуге. Подняли старый вопрос, самому захотелось додумать проблему smile

PM MAIL ICQ   Вверх
dvs
Дата 11.5.2005, 00:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Владимир Драпалюк
**


Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19



эх, рекурсия, рекурсия... бул там алгоритм, чей-то на рекурсии. Не помню из-за чего, но так и не осознал как работает....



--------------------
Любите друг друга!
PM MAIL WWW ICQ   Вверх
fess
Дата 11.5.2005, 11:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 125
Регистрация: 17.2.2005
Где: г. Мурманск, Росс ия

Репутация: нет
Всего: 3



Когда встречаются неоднозначные случаи, то необходимо использовать перебор и выводить все варианты решения.
--------------------
Компьютер не подчиняется законам физики. Только в нём глюки возникают из ничего, файлы исчезают в никуда, а объём измеряется в метрах и называется весом.
PM MAIL ICQ   Вверх
dm9
Дата 11.5.2005, 11:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дмитрий Копытин
****


Профиль
Группа: Vingrad developer
Сообщений: 3876
Регистрация: 22.7.2002
Где: Москва

Репутация: нет
Всего: 137



fess, перебор как? 2^S вариантов, где S - число клеточек? smile

PM MAIL ICQ   Вверх
dvs
Дата 11.5.2005, 12:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Владимир Драпалюк
**


Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19



dm9 ты меня пугаешь... Нет конечно, нужно учитывать значения количества закрашенных.


--------------------
Любите друг друга!
PM MAIL WWW ICQ   Вверх
dm9
Дата 11.5.2005, 12:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дмитрий Копытин
****


Профиль
Группа: Vingrad developer
Сообщений: 3876
Регистрация: 22.7.2002
Где: Москва

Репутация: нет
Всего: 137



Дык вот это и задача как раз... перебор, но умный.
Одну клеточку поставили, остальное довели логикой. Опять тупик - ещё клеточку поставили. Пришли к противоречию - идём на шаг назад. Только, мне кажется, долго получится всё равно. В общем, надо пробовать на практике, так оценить я затрудняюсь smile

PM MAIL ICQ   Вверх
~FoX~
Дата 11.5.2005, 13:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


НЕ рыжий!!!
****


Профиль
Группа: Участник Клуба
Сообщений: 2819
Регистрация: 8.10.2003
Где: Зеленоград

Репутация: 2
Всего: 68



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


--------------------
user posted image
…множественность никогда не следует полагать без необходимости…
PM MAIL WWW ICQ Jabber   Вверх
dvs
Дата 11.5.2005, 16:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Владимир Драпалюк
**


Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19



~FoX~ расскажи подробнее, как это ты представляешь? smile


--------------------
Любите друг друга!
PM MAIL WWW ICQ   Вверх
Akina
Дата 11.5.2005, 16:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Собсно алгоритм несложен.
Имеем по каждой вертикали и горизонтали количество закрашенных клеток. Просматриваем каждую. На каждом шаге.
Самый простой вариант - по одной из вертикалей или горизонталей имеется однозначное соответствие (с учетом на текущий момент известных клеток) - тогда клетки красятся и вновь возвращаемся к просмотру.
Более сложный вариант - однозначности нет. Тогда приходится делать предположения - т.е. ветвимся. Соответственно наиболее выгодное ветвление - на минимальное количество веток, причем каждая ветка рассматривается уже как окончательная (и она придет либо к решению, либо к противоречию/неоднозначности и будет отсечена). Т.е. приходим к обычному рекурсивному спуску с отсечениями - фактически полный перебор.
Несколько ускорить процесс могут генетические алгоритмы выбора ветви - но это гораздо более сложно в программной реализации. Хотя и возможно.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
~FoX~
Дата 12.5.2005, 10:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


НЕ рыжий!!!
****


Профиль
Группа: Участник Клуба
Сообщений: 2819
Регистрация: 8.10.2003
Где: Зеленоград

Репутация: 2
Всего: 68



dvs15
Я на самом деле себе это плохо представляю, но вот есть у нас кросворд в котормо более одного решения, на рисунке которого изображен допустим квадрат малевича вид под углом в 18 градусов. При решении возникает вероятная точка внутри квадрата или вне него, допустим в левом нижнем углу поля. Алгоритмически и тот и другой вариант допустимы и более того они оба правильные. Естественно взглянув человеческим глазом мы безошибочно определим правильный вариант, а вот как это сделать программно я не знаю smile


--------------------
user posted image
…множественность никогда не следует полагать без необходимости…
PM MAIL WWW ICQ Jabber   Вверх
dvs
Дата 12.5.2005, 18:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Владимир Драпалюк
**


Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19



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

Интересно, а если задумка автора другая? ИМХО, таких кроссвордов быть не должно.


--------------------
Любите друг друга!
PM MAIL WWW ICQ   Вверх
AISIN
Дата 12.5.2005, 21:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 185
Регистрация: 27.1.2005
Где: Пушкино

Репутация: нет
Всего: 1



Akina Ты прав! Только если кроссворд большой по времени слишком долго будет работать!
--------------------
Внимание!!! Внимание!!!Запущена программа по завоеванию мира!!!Выполненно 0,000000000000000000000000000000000000000000000000000002%
PM MAIL   Вверх
dvs
Дата 12.5.2005, 22:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Владимир Драпалюк
**


Профиль
Группа: Участник Клуба
Сообщений: 660
Регистрация: 25.8.2003
Где: Воронеж->Москв а

Репутация: нет
Всего: 19



Главное чтобы работал.
Очень давно, когда писали программу, тестировали для разных кроссвордов (больших тоже).
Так вот, рекурсивный алгоритм какого-то дяди "умирал" для очень больших тестов (по понятным причинам).
А наш работал дольше, но делал своё дело.


--------------------
Любите друг друга!
PM MAIL WWW ICQ   Вверх
AISIN
Дата 12.5.2005, 23:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 185
Регистрация: 27.1.2005
Где: Пушкино

Репутация: нет
Всего: 1



Цитата(dm9 @ 11.5.2005, 00:04)
AISIN, мы так и делали с dvs15. Чистая логика.
На таком кроссворде:

Код

  1    1    1  
1
1
1


этот алгоритм загнётся.

Ну вобщем тыкаем случайным образом в любую ячейку массива и закрашиваем её. Потом смотрим вокруг ячейки по вертикали и горизонтали (соседние ячейки)если больше ничего не надо красить то отмечаем крестик! Далее спускаемся по диагонали допустим вправо - вниз если вышли за границы масива то случайно тыкаем в любую другую незаполненую клетку и закрашиваем ее проверяя соседние (вдруг их тоже надо красить?) smile а если не вышли за пределы массива то смело красим текущуу ячейку проверяем все вокруг и спускаемся по диагонали!
Хорошо бы вести .log файл, если возникнут проблемы можно откатить все назад до проблемной ячейки и проблемную ячейку пометить крестиком!

Это сообщение отредактировал(а) AISIN - 12.5.2005, 23:04
--------------------
Внимание!!! Внимание!!!Запущена программа по завоеванию мира!!!Выполненно 0,000000000000000000000000000000000000000000000000000002%
PM MAIL   Вверх
dm9
Дата 12.5.2005, 23:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дмитрий Копытин
****


Профиль
Группа: Vingrad developer
Сообщений: 3876
Регистрация: 22.7.2002
Где: Москва

Репутация: нет
Всего: 137



AISIN, ну, собственно, это описал сначала я, а потом Акина.

Принципиально новые предложение ещё ни у кого не завалялись? smile

PM MAIL ICQ   Вверх
Страницы: (3) Все 1 [2] 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1542 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.