Крадец

[dgs]

От дълго време полицията преследва крадец, който винаги се изплъзвал в последния момент.

Накрая задачата по залавянето била възложена на Шерлок Холмс и д-р Уотсън - в смисъл, да ръководят операцията по залавянето.

С помощтта на информатори, д-р Уотсън събрал следната информация:
1. Крадецът разполага с 20 квартири, номерирани от 1 до 20
2. Всеки ден крадецът сменя квартирата по следния начин - днешната квартира е или с един номер по-голям от вчерашната, или с два номера по-малка.

Д-р Уотсън съобщил получената информация на Шерлок Холмс. И накрая добавил:
- Лошо. Току-що проверих ресурсите на нашата оперативна група. Имаме възможности да правим засада и обиск най-много на две квартири на ден. Ще трябва да разчитаме на случайност. Дано един месец ни стигне за да го заловим.

Холмс се усмихнал и казал:
- Драги ми Уотсън, това е елементарно. Ще го хванем за по-малко от половин месец без никаква случайност.

Та това е задачата:
1. Да се намери алгоритъм който да гарантира залавянето без никаква случайност
2. Колко дни са достатъчни за гарантираното залавяне - колко е мининималния брой дни ?

Добавено:
Пропуснал съм да напиша, че информаторите са дали на д-р Уотсън адресите на всичките 20 квартири.

[Реклама]

[martosss]

ми аз се сещам за алгоритъм, при който го хващат за 19 дни :

1. 19 и 20
2. 18 и 19
3. 17 и 18
.
.
.
последно - 1 и 2

понеже крадецът може да се мести само с 1 квартира "нагоре", то все ще го хванем някъде
Сега да видим дали има по-кратък начин...

[marshal]

Трябва да го хванат за по-малко от 15 дни. Така казва Холмс..

[martosss]

Добре, ето така става по-бързо:
1. 18, 19
2. 17, 18
3. 16, 17
.
.
.
18. 1, 2
Станаха 18 дни.

За съжаление не се сещам за по-бърз вариант Ако ти имаш предложения може да ги споделиш

[dgs]

martosss,
първия ден в твоя подобрен алгоритъм май е излишен ?
(Направо да почваме от (17,18 ) и да спестим още един ден, а ?! )
Объркал съм се martosss, извинявай

---------------------------------------------------------------------------
Бях се притеснил вече, че задачата не предизвиква интерес.

Тази задача е усложнен вариант на една популярна "по-лека" задача, при която броя на квартирите е 17, а стъпката и напред и назад е 1 - днешната квартира е с един номер по-голям или по-малък от вчерашната.

Предлагам първо да решим "леката" задача, пък после да се прехвърлим на усложнения вариант. Както ще се види накрая, алгоритъма на "леката" задача може да се обобщава и върши работа дори и ако задачата се усложни доста повече - например брой на квартирите 47, при стъпка "3 напред, 4 назад". При такова усложнено условие, на пръв поглед дори е трудно да се предполага съществуването на алгоритъм, гарантиращ залавянето.

[martosss]

Измислих го с 14 :
14, 16
14, 16
12, 14
12, 14
10, 12
10, 12
8, 10
8, 10
6, 8
6, 8
4, 6
4, 6
2, 4
2, 4

Общо 14

Аналогично при нашата задача може да стане вероятно и по-бързо:
18, 19
16, 18
16, 18
14, 16
14, 16
12, 14
12, 14
10, 12
10, 12
8, 10
8, 10
6, 8
6, 8
5, 6
3, 5
3, 5
2, 3

17 опита Има напредък

Ама стъпка 3 напред 4 назад

[dgs]

Малко подсказване от мен по случая "17 квартири, 1 напред / 1 назад":

Ако крадецът първия ден е в нечетна квартира, то със следното търсене гарантирано ще го хванем най-много за шест дни:

Ден 1 - 1.3.......
Ден 2 - ...4.6......
Ден 3 - ......7.9....
Ден 4 - .........10.12...
Ден 5 - ............13.15..
Ден 6 - ................16. (на този ден е достатъчно да претърсим само една квартира)

Ако крадецът първия ден е в четна квартира, то той ще се измъкне през първите шест дена и на седмия ден той пак ще е в четна квартира. А на осмия ще е в нечетна. Бихме могли да пропуснем седмия ден и да повторим същото тъсене от осмия

Ден 7 - не търсим
Ден 8 - 1.3.......
Ден 9 - ...4.6......
Ден 10 - ......7.9....
Ден 11 - .........10.12...
Ден 12 - ............13.15..
Ден 13 - ................16. (и на този ден е достатъчно да претърсим само една квартира)

С този алгоритъм, си гарантираме залавяне най-късно на тринадесетия ден. Това обаче далеч не е най-добрия резултат.

Мисля повече да не подсказвам, докато не се появи оптималното решение за този случай.

Добавено:
martosss,
Алгоритъма който предлагаш от 17 стъпки не работи.
Например:
1-ви ден - крадецът е в квартира 6
2-ри ден - крадецът е в квартира 4
3-ри ден - крадецът е в квартира 2
...

[martosss]

[Elite]

20 17
17 14
16 13
15 12
14 11
13 10
12 9
11 8
10 7
9 6
8 5
7 4
6 3
5 2
4 1


Мисля че става така.
Edit:не е така

[martosss]

[dgs]

Браво martosss,
спипа го крадеца само за 10 дни, а д-р Уотсън е с широко отворени очи и се почесва по темето от твоята тактика.

Тая твоя тактика има едно доста добро визуализиране

На картинката ходовете от 6-тия до 10-тия ден повтарят тези от 1-вия до 5-тия, но това няма значение - алгоритъма е същия като твоя.
Ако крадецът първия ден е бил в "сива" квартира, то и в следващите дни винаги ще е в сива, съответно ако е в "бяла", то и следващите дни ще е в бяла. Съответно първите 5 дни обискираме сивите квартири, а вторите 5 дни обискираме белите.


Сега ще видим ли някакъв хубав твой резултат и за "20 квартири, 1 напред / 2 назад", дали и Шерлок Холмс ще го засърби темето ?

[martosss]

хехе ще трябва доста да се чеша по темето... пък и утре имам да уча и да хдоя по гостита... но ще видим, може и да извадя нещо, ама сигурно няма да е скоро че е късно вече Иначе благодаря Като гледам оптималните решения станаха 2 А даже може да са 4 - ако се почне вместо от 2 4 от 14 16 - стават още 2 варианта

[martosss]

Хм... дали така ще стане?

18 19 - 1-ви ход
16 18
15 18
14 17
13 16
12 15
11 14
10 13
9 12
8 11
7 10
6 9
5 8
4 7
3 6
2 5
1 4 - 17-ти ход

Опа.. май няма напредък.. пак 17... но ще е нещо такова...

[dgs]

Я да видим как ще изглежда на картинка това което предлагаш



Съгласем съм - ще успееш да го спипаш крадеца с тоя алгоритъм от 17 дни.

Но д-р Уотсън няма да се впечатли от тези 17 дни (много са).
Дори ще отбележи че си разточителен и харчиш безразборно ресурсите на оперативната група - при тоя алгоритъм първия ден няма нужда да проверяваме квартира 19

Възнамерявам да се въздържам от подсказване за известно време - поне докато не се появи решение за по-малко от половин месец.

[martosss]

да, честно казано и аз сега си направих една подобна табличка и ще видим какво ще успея да докарам Лошото е че на първата задача логиката е че крадецът сменя четността на квартирите, докато сега той може да с няколко хода да попадне в същата четност...

Сега обмислям да почна с

15 18
15 18
15 18
И за 3 дена изчиствам 5 клетки... тук има някакъв напредък... ако продължим примерно с

13 15
12 15
11 14
10 13
9 12
8 11
7 10
6 9
5 8
4 7
3 6
2 5
1 4
3

ето го истинският алгоритъм за 17 дни И тъй като последния ден проверявам само 3, то със сигурност има и решение за 16 дни !!!

леле.. миналата ми тактика има недостатък... ако на 16-ти ден крадецът е на 1-ва клетка и на 17-тия отиде на 2-ра не го хващам ! ! ! Трябва ми на 18-тия ден да посетя 3

[dgs]

[martosss]

ох, вярно.. много интересно
Да, сега като се позамислих открих и за 16 дни:
15 18
15 18
15 18
13 15
12 15
11 14
10 13
9 12
8 11
7 10
6 9
5 8
4 7
и тук идва новата част
2 6
4 5
2 3

Просто си оправих единичния ден

[martosss]

ОМГ Ето и за 15, то било толкоз лесно

15 18 1-ви ход
15 18
15 18
12 15
12 15
12 15
9 12
9 12
9 12
6 9
6 9
6 9
3 6
3 6
3 6 15-ти ход

ОМГ много тъпо... впрочем има нещо интересно, при този модел може примерно
3-ти и 4-ти ход да са
14 18
12 16, аналогично може да стане

11 15 -6-ти ход
9 13 -7-ми ход
или

8 12 - 9-ти ход
6 10 - 10-ти ход.

и последно

5 9 - 12-ти ход
3 7 - 13-ти ход

Така получаваме 16 аналогични тактики с изход 15 хода.

Почвам да мисля за 14

[martosss]

опа.. тук се получи лек скок, измислих за 11, да не повярва човек...

15 18 - 1-ви ход
10 13
5 8
3 19
14 17
9 12
4 7
2 18
13 16
8 11
3 6 - 11-ти ход

А сега Холмс ще се почеше ли по темето?

П.П. Този филм Али Баба се оказа доста градивен - докато го даваха се случиха чудеса Впрочем чак сега прочетох отново постовете ви с помощ и осъзнах какво сте имали предвид с цветовете То това е основното в задачата - да разделиш тези числа на групи, в които числата отиват в едни и същи клетки.. ама докато го усетя това ми трябваха няколко дни

[Elite]

Това за 20 дни ли е?
15 18 - 1-ви ход ако е в 19-та
10 13 тук идва в 20-та
5 8 връща се в 18-та
3 19 още 2 хода назад и е в 16-та
14 17 после в 14-та
9 12 сега 15-та
4 7 16-та
2 18 17-та
13 16 18-та
8 11 19-та
3 6 - 11-ти ход 20-та

бъркам ли се

[martosss]

[dgs]

Отличен скок martosss,
Мислех си, че ще успееш до 12, но ще позапънеш за 11, ама ти сериозно си се бил засилил. Браво от мен. И д-р Уотсън и Холмс те поздравяват.

А ето я и цветната картинката с решението ти:



Убеден съм, че вече нямаш проблеми с "3 напред / 4 назад"

[martosss]

Е ми аз наистина първо открих за 12, но после си викам "я дай да пробвам да почна с някой друг набор от числа" и то взе че стана по-кратко Наистина си нямах никаква представа че може тази на пръв поглед толкова трудна задача да стане толкова лесна