Преглед за печат
Задача:
Осем скрити карти - с осем различни числа са разбъркани на масата.
Можете да поискате от приятел да подреди две от числата, като
посочите номерата им.
Например ако поискате да се подредят номера 2 и 5, той ще сложи
на второ място картата с по-малкото от двете числа, а на 5
място - картата с по-голямото. При това вие няма да разберете
разменял ли е карти или не.
Търси се минимален брой заявки, за който гарантирано
може да се твърди, че всички карти са подредени.
Да разбирам ли, че:
1. Аз избирам 2 карти които се наричат и "числа"?
2. От неподредените карти ли избирам или от всичките? ...щото в първия случай повече от 4 хода не виждам как ;)
3. Проятеля слага тези две карти на посочените от мен места във възходящ ред?
4. Ако съответно място е заето от предишно мое посочване може да не разбера сменял ли е предишната карта с нова или не?
Сори, ама малко трудно се разбира от така зададения въпрос кой какво прави и с кое... Или поне аз, де. :)
Аз доколкото разбирам от задачата търси се метод за сортиране. Веднага се сещам за метода на мехурчетата,но той е много неефективен.
На първо четене 7+6+5+4+3+2+1=28
Sent from my phone using Tapatalk
Точно толкова се получава при метода на мехурчетата.Аксиома за всеки програмист.Цитат:
Първоначално публикувано от spiritch
Решението се приема "на първо четене".
Гарантирано числата се подреждат, но дали
броят на ходовете е минимален?
@kamenf:
1. Избираш 2 карти с техните номера
2. От всичките
3. Приятелят слага картите на същите места, откъдето ги е взел,
или разменя местата им (ако трябва) или не
Мисля, че 23 пъти стигат.
(1-4) 1-5
(2-5) 2-6
(3-6) 3-7
(4-7) 4-8
1-3
2-4
1-2
3-4
2-3
5-7
6-8
5-6
7-8
6-7
(2-5)2-5
(2-6)4-7
(2-7)3-5
(3-5)4-6
(3-6)3-4
(3-7)5-6
(4-5)4-5
(4-6)
(4-7)
Май не става както си го показал.
Ако на-малката стойност е на 8-ма позиция в началото, то
- на 11-тия ход отива на 6-та
- на 12-тия отива на 5-та
- на 15-тия отива на 2-ра и там си остава
Общо взето "метода на мехурчето" затова е метод - защото хваща всички възможни начални състояния.
Може да се оптимизира само ако знаем, че в началните състояния има предварително известни изключения. В конкретната задача няма такива изключения.
Мога за 24 хода.
1. сортираме по двойки: 1-2, 3-4, 5-6, 7-8
2, сортираме първата и последната четворка с по 4 хода: 1-3, 2-3, 3-4, 2-3 и 5-7, 6-7, 7-8, 6-7
3. сортираме средната четворка (позиции от 3 до 6): 3-5, 4-5, 5-6, 4-5
4. пак сортираме първта и последната четворки с по 4 хода: 1-3, 2-3, 3-4, 2-3 и 5-7, 6-7, 7-8, 6-7
ПП: втория ход от сортиране на четворките винаги е смяна - следва от подредените вече двойки.
ПП2: глупости говоря... не става така, трябват още 4 с този подход.
Така както си го посочил, след втория ход е възможно да се стигне до:
5
6
7
8
1
2
3
4
При което накрая ще има
1
2
5
6
3
4
7
8
ПП
Не съм си рифрешнал страницата, междувременно си се редактирал.
Да, малко бях объркал сортирането на четворките, но става с 22 хода:
1. Сортираме по двойки: 1-2, 3-4, 5-6, 7-8
2. Сортираме първата и последната 4-ки с по 3 хода: 1-3, 2-4, 2-3 и 5-7, 6-8, 6-7
3. Сортираме средната четворка: 3-5, 4-6, 4-5
4. Сортираме първата и последната 4-ки с по 3 хода: 1-3, 2-4, 2-3 и 5-7, 6-8, 6-7
5. Сортираме средната четворка: 3-5, 4-6, 4-5
- - - - - - - - - -
Предишното може да се извтрши и така:
1. соттират се двойки
2. сортират се първа, средна и последна 4-ки
3. сорртират се първа и средна
4. сортира се пак първа
И така се вижда, че стъпките скед ппървата приличат на бъбълсорт, но с възползване от предварителното сортиране по двоки
Айй, забавих се и аз.
Ще напиша и моя код.
12,34,56,78
13,24,57,68
15,48
вече имаме 1 на първа и 8 на осма позиция.
23,45,67
24,37
26,57
вече имаме и 2 и 7 на местата си.
34,56
35,46
сега 3 и 6 са на местата си.
45
И 4 и 5 са на място.
22 хода общо.
Грешка при въвеждането, първите 4 саЦитат:
Първоначално публикувано от MitkoS
1-5
2-6
3-7
4-8
Sent from my phone using Tapatalk
- - - - - - - - - -
21
1-5
2-6
3-7
4-8 1 е в първата четворка, а 8 последната
1-3
2-4
1-2
3-4
2-3 Подреждане на първа четворка (1 е на първо място)
5-7
6-8
5-6
7-8
6-7 Подреждане на втора четворка (8 е на осмо място)
2-5 2 отива на второ място
4-7 7 отива на седмо място
3-5
4-6
3-4
5-6
4-5 Подреждане на карти от 3 до 6
Става и с 19.
Не, в грешка съм засега.
Аз смятам, че spiritch се справи повече от добре!
Но, предположението за 19 също е перспективно!
Мисля че, на финала могат да се спестят червените редове:
...
3-5
4-6
(3-4)
(5-6)
4-5 Подреждане на карти от 3 до 6
Според мен 3-4 и 5-6 са вече сортирани преди тези 5 хода.