алгоритм

[eXtremal]

Нужен алгоритм задачке. Есть ряд из N людей у одного из них (при чем все знают у кого она)есть какая то вещь (которную нужно взять). Какие наводящие вопросы нужно задать группе людей, что бы получить вещицу за конечное время? Оценить верхную границу времени работы алгортма. :(

[Васильевич]

Вопрос только один - справа или слева находится человек с нужной вещью. Быстрее дихотомии в неранжированном ряду выборки вроде еще ничего не придумали...

[eXtremal]

тогда максимальное время будет n/2 или логорфм от чего то???

[Васильевич]

Да, N/2+1

[eXtremal]

ln(N+1/2) ??? :)

[Васильевич]

Почему обязательно логарифм?

Вы каждый раз делите выборку пополам, значит N/2 и плюс сам правильный выбор.

[eXtremal]

Т.е если N= 50 то, время = 26 ??? :) не долговато?? :)

[mmap]

Ну если учесть, что компьютер может выполнять до 3000000000 и более микроопераций в секунду, то, я думаю, это очень мало :)

[Тролль]

Сейчас все окончательно запутаю... ½+1/4+...=1 Надо один раз поделить, зато с умом ;) Проверка: вопрос "У кого то, что мне нужно?" при достаточной мотивированности отвечающих достаточно задать один раз

Если серьезно, то вопрос заключается в том, сколько раз можно будет делить на два. Два можно поделить на два один раз. Четыре – два раза. Восемь – три. Итого получаем 2^k=N, то есть k=двоичный логарифм N

С округлением до целого в большую сторону.

[eXtremal]

т.е. logN (по основанию 2)? :)

[Тролль]

Ну, тут еще надо обозначить округление. В чисто традиционных обозначениях получается min k, где k ≥ log₂ N , k,N∈N, в книгах по информатике обычно используют обозначение ⌈log₂ N⌉ , можно записать также ⌈lb N⌉ , если препод знает, что lb – обозначение бинарного (двоичного) логарифма (как lg – десятичного, а ln – натурального).

Кстати, задача – прямо на определение количества информации (в битах) по Шеннону. Основоположник теории информации Клод Шеннон так количество информации и определял – количество выборов из равновероятных возможностей, нужное для получения однозначного ответа.

[eXtremal]

Тролль

Спасибо!!! Огромное!!! все именно так!!!! ;)