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