eXtremal Posted December 25, 2004 Report Share Posted December 25, 2004 Нужен алгоритм задачке. Есть ряд из N людей у одного из них (при чем все знают у кого она)есть какая то вещь (которную нужно взять). Какие наводящие вопросы нужно задать группе людей, что бы получить вещицу за конечное время? Оценить верхную границу времени работы алгортма. :( Link to comment Share on other sites More sharing options...
Васильевич Posted December 25, 2004 Report Share Posted December 25, 2004 Вопрос только один - справа или слева находится человек с нужной вещью. Быстрее дихотомии в неранжированном ряду выборки вроде еще ничего не придумали... Link to comment Share on other sites More sharing options...
eXtremal Posted December 25, 2004 Author Report Share Posted December 25, 2004 тогда максимальное время будет n/2 или логорфм от чего то??? Link to comment Share on other sites More sharing options...
Васильевич Posted December 25, 2004 Report Share Posted December 25, 2004 Да, N/2+1 Link to comment Share on other sites More sharing options...
eXtremal Posted December 25, 2004 Author Report Share Posted December 25, 2004 ln(N+1/2) ??? :) Link to comment Share on other sites More sharing options...
Васильевич Posted December 25, 2004 Report Share Posted December 25, 2004 Почему обязательно логарифм? Вы каждый раз делите выборку пополам, значит N/2 и плюс сам правильный выбор. Link to comment Share on other sites More sharing options...
eXtremal Posted December 25, 2004 Author Report Share Posted December 25, 2004 Т.е если N= 50 то, время = 26 ??? :) не долговато?? :) Link to comment Share on other sites More sharing options...
mmap Posted December 25, 2004 Report Share Posted December 25, 2004 Ну если учесть, что компьютер может выполнять до 3000000000 и более микроопераций в секунду, то, я думаю, это очень мало :) Link to comment Share on other sites More sharing options...
Тролль Posted December 25, 2004 Report Share Posted December 25, 2004 Сейчас все окончательно запутаю... ½+1/4+...=1 Надо один раз поделить, зато с умом ;) Проверка: вопрос "У кого то, что мне нужно?" при достаточной мотивированности отвечающих достаточно задать один раз Если серьезно, то вопрос заключается в том, сколько раз можно будет делить на два. Два можно поделить на два один раз. Четыре – два раза. Восемь – три. Итого получаем 2^k=N, то есть k=двоичный логарифм N С округлением до целого в большую сторону. Link to comment Share on other sites More sharing options...
eXtremal Posted December 26, 2004 Author Report Share Posted December 26, 2004 т.е. logN (по основанию 2)? :) Link to comment Share on other sites More sharing options...
Тролль Posted December 26, 2004 Report Share Posted December 26, 2004 Ну, тут еще надо обозначить округление. В чисто традиционных обозначениях получается min k, где k ≥ log₂ N , k,N∈N, в книгах по информатике обычно используют обозначение ⌈log₂ N⌉ , можно записать также ⌈lb N⌉ , если препод знает, что lb – обозначение бинарного (двоичного) логарифма (как lg – десятичного, а ln – натурального). Кстати, задача – прямо на определение количества информации (в битах) по Шеннону. Основоположник теории информации Клод Шеннон так количество информации и определял – количество выборов из равновероятных возможностей, нужное для получения однозначного ответа. Link to comment Share on other sites More sharing options...
eXtremal Posted December 27, 2004 Author Report Share Posted December 27, 2004 Тролль Спасибо!!! Огромное!!! все именно так!!!! ;) Link to comment Share on other sites More sharing options...
Recommended Posts