knop: (qr)
[personal profile] knop
Очередное моё творчество для "Элементов".
http://elementy.ru/problems/1093
На сей раз в качестве задачи выбран сюжет 10.8 из Всероса этого года (авторы - Илья Богданов и Сергей Берлов), хотя доказательство оптимальности я написал по-другому. В "Послесловии" показаны еще две задачки, в которых оптимальность алгоритма доказывается тем же методом - рассмотрением Соперника, который играет против произвольного алгоритма.

Если вы знаете еще какие-нибудь нетривиальные задачи, в решении которых появляется Adversary/Соперник, - напишите, пожалуйста.

Date: 2015-07-01 06:55 am (UTC)
From: [identity profile] 173175973.livejournal.com
Придерусь к фразе "Обязательно обратите внимание, что все фальшивые монеты имеют разные массы. Без этого условия задача не решается."
Это две разные задачи: когда массы разные, и когда известно только то, что фальшивые тяжелее. А решение есть в обоих случаях (минимальное число взвешиваний, конечно, разное в большинстве случаев)

Date: 2015-07-01 07:11 am (UTC)
From: [identity profile] knop.livejournal.com
Да, это результат недоредактиврования условия.
Изначально в нем стоял ответ (70). И тогда, безусловно, без условия о различных массах задача не решается
From: [identity profile] eropgch.livejournal.com
Если перепрограммировать компьютер так, что бы он выбирал вершину А не заранее, а как одну из вершин ребра, про которое человек спросил первым запросом, то можно гарантировать не менее 11 запросов... :xz:

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 25th, 2017 06:30 am
Powered by Dreamwidth Studios