Загадки

[Просто Вова]

узкая часть широкая часть узкая часть пластиковая часть глубокая часть и часть с прорезью 5 мм.

О, ну теперь всё понятно. Это кака-то фигня с прорезью в узкой части.

[Местный]

Начинать давать подсказки?

[Местный]

Что-то очень специфичное :-(

Вещь для применения в обычном быту.

[Йота]

Да, мы приблизились к отгадке. Пластмассовая фигня с прорезью и тупичком для применения в быту. Интересно...

[Вал]

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

[Местный]

Нет, у него другое применение. Еще подсказку давать?

[Йота]

Конечно! Мы же в тупике.

[Lexa]

Это какая-то деталь от мясорубки?

[Местный]

Нет. Подсказка. Чаще всего эту штуковину можно было встретить в ванной комнате.

[Йота]

Че, чистилка для дырки от раковины?
Только чем же так можно загадить дырку от раковины??? Нет, я снова в просаке

[Lexa]

Эта штука как-то связана с леской?

[Просто Вова]

Да, я тоже рыбу в ванной ловлю.

[Местный]

Эта штука как-то связана с леской?

Нет. Но мыслите в правильном направлении.

[octavia]

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

Надо было обойти шахматную доску конем



Вот и ответ:

Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

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

Эвристика всегда работает на досках от 5x5 до 76x76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

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

[tiresome]

Для чего использовался этот предмет?

Ответ