#1 01-12-2010 23:19

~AquaZ~
Registered: 01-03-2010
Posts: 726

Интересная задачка

Есть объект, например, жук. Лабиринт - матрица XxY ячеек. Жук стартует в точке (0;0), заканчивает движение в правой нижней точке. Алгоритм движения:

жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше. Следует заметить, что двигаясь по данному алгоритму жук всегда достигнет выхода в том случае, когда выход существует.

Каким должен быть лабиринт (за исключением закрытого), в котором жук проведёт больше всего времени?

Offline

#2 02-12-2010 11:25

3Doomer
From: КаZан
Registered: 14-05-2008
Posts: 659
Website

Re: Интересная задачка

не вижу простора для мысли...лабиринт всегда прямоугольный, и выход со входом всегда по углам. что менять-то можно? размер?
тогда проведённое время будет прямо пропорционально размеру лабиринта


GIMS developer

Offline

#3 02-12-2010 13:59

~AquaZ~
Registered: 01-03-2010
Posts: 726

Re: Интересная задачка

Забыл сказать, каждая ячейка матрицы может быть занятой (стенка, туда нельзя идти) или свободной.

Offline

#4 02-12-2010 16:25

3Doomer
From: КаZан
Registered: 14-05-2008
Posts: 659
Website

Re: Интересная задачка

хм...судя по алгоритму движения, он пройдёт от старта до упора вниз, потом направо - прямо к финишу

надо перегораживать дорогу...первым делом - на одну ниже старта, а потом - хз...


GIMS developer

Offline

#5 02-12-2010 19:20

Den_spb
From: Ленинград
Registered: 23-11-2008
Posts: 937
Website

Re: Интересная задачка

Ответа к задаче не знаю, но могу дать свою загадку:
519c10561d3bt.jpg
Что за предмет изображён на рисунке? Форма предмета доведена достаточно достоверно.

Offline

#6 02-12-2010 20:40

~AquaZ~
Registered: 01-03-2010
Posts: 726

Re: Интересная задачка

Круг и квадрат smile
...или...
круг, в котором высверлен квадрат smile)

Offline

#7 02-12-2010 22:42

Den_spb
From: Ленинград
Registered: 23-11-2008
Posts: 937
Website

Re: Интересная задачка

Круг и квадрат - геометрические фигуры, а тут изображён материальный предмет (кстати, знакомый всем).

Offline

#8 02-12-2010 23:33

~AquaZ~
Registered: 01-03-2010
Posts: 726

Re: Интересная задачка

Не знаю. Закончили оффтоп.
Как проверить, не отделён ли жук от выхода?

Offline

#9 08-12-2010 21:05

~AquaZ~
Registered: 01-03-2010
Posts: 726

Re: Интересная задачка

Есть тут кто?

Offline

Board footer

Powered by FluxBB