Задачка 2.

[pinmix]

Мне нужна помощь в решении некоторой задачки, вернее задачка уже решена, ее нужно доказать.

Наверняка кто-нибудь сталкивался с детской "задачкой о фальшивой манете":

Это когда нужно путем взвешивания найти из предложенного числа монет - фальшивую.

Точнее:

"Дано N монет, среди них либо есть одна фальшивая, либо нет вообще.

Есть весы которые могут показать какая чаша тяжелее.

фальшивая монета может быть как тяжелее настоящей, так и легче - но она обязательно отличается!!!"

На моем фак-те мы разобрали эту задачку, но заданием является определение сложности алгоритма, если кто не знает что это и как - поясню:

Сложность алгоритма - время затрачиваемое машиной для выполнеия его.

например: Сумма членов от "1" до "N" - сложность: N, т.к. нужно произвести N операций: 1+2+3+...+N;

В данной задаче: Сложность оптимального алгоритма: L>=Log(3) (2n+1), поясняю при взвешивании может быть три исхода: правый > левого, правый < левого, правый = левому: нарисуем блок схему: в начале все множество вариантов: фальшивой монетой может быть любая из N - поэтому в начале: N,

монеты могут быть как легкими, так и тяжелыми - поэтому в начале: 2N,

и еще возможен вариант, когда фальшивой - нет - поэтому в начале: 2N+1.

Далее из начала выходит три ветви (т.к. три исхода), значит ((2N+1)/3)вариантов, далее из каждой еще по три: ((2N+1)/9)вариантов, и так пока к-во вариантов не станет <=1.

Например: если N=4:

                                >                    <                                           

                                  ---[1,2 : 3,4]---         

                                  |          |          |         

                                  |          |          |   

                  (1т,2т,3л,4л)      (G)        (1л,2л,3т,4т)     

                              |                                    |               

                              |                                    ... 

                      >      |    <     

                      ---[1 : 2]---       

                      |      |      |   

                    (1т)    |    (2т)     

                      >      |    <       

                      ---[3 : 4]---       

                      |              |       

                  (4л)          (3л)

Поясняю: "[1,2 : 3,4]" это монеты под номерами 1,2,3,4 на весах: 1,2 на левой чаше, 3,4 - на правой.

если левая чаша перевешивает: (1 и 2) тяжелее чем (3 и 4) - значит либо одна из монет 1,2 тяжелые (т), либо одна из монет 3,4 легкие (л).

Если (1 и 2) = (3 и 4) - значит фальшивых монет нет (G),

Ну и с перевесом правой чаши аналогично левой.

И так далее пока не останется одна монета...

НО: сложность "L>=Log(3) (2n+1)" выводилась для общего случая: с помощью "триарного дерева", а на весах сложность чуть больше: L>Log(3) (2n+1);

Однако, если бы у нас была "эталонная монета" все было бы гораздо проще.

(эталонная монета - монета которая не фальшивая по условию)

Тогда сложность будет как у "триарного дерева" со знаком равенства (только со знаком равенства): "L=Log(3) (2n+1)", т.к. в таком случае деление будет на три равные части:

на примере с 4мя монетами:

                                            >                  <

                                            ---[0,1 : 2,3]---

                                          |          |          |

                                          |          |          |

                              (1т,2л,3л)  (4т,4л,G)  (1л,2т,3т)

Теперь задание для вас: Докажите что сложность для алгоритма с эталоном будет именно "L=Log(3) (2n+1)", и не как иначе.

И откда вообще ее взять?..

[Max]

Задачку прочитал, но думаю, что не понял.

Особенно не понял следующее:

НО: сложность "L>=Log(3) (2n+1)" выводилась для общего случая: с помощью "триарного дерева", а на весах сложность чуть больше: L>Log(3) (2n+1);

Меня смущает это "чуть": откуда это?

А в последнем объяснении (цитате-рисунке) не понятно, что такое 4т, 4л. Надо бы ещё поподробнее.

[pinmix]

Задачку прочитал, но думаю, что не понял.

Особенно не понял следующее:

Меня смущает это "чуть": откуда это?

А в последнем объяснении (цитате-рисунке) не понятно, что такое 4т, 4л. Надо бы ещё поподробнее.

210983[/snapback]

"чуть": это что не равно! т.е. не ">=", а ">"!

а выходит это из того, что в триарном дереве мы делим к-во монет ровно на три части(ведь это теория), а на весах это сделать не возможно(практика).

"4т,4л":

это значит что если чаша с монетами (0,1) равна чаше (2,3) значит либо фальшивых нет, либо фальшивая - 4я и она своевременно может быть как тяжелой, так и легкой...