Перейти к содержанию
СофтФорум - всё о компьютерах и не только

алгоритм


Рекомендуемые сообщения

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

Ссылка на комментарий
Поделиться на другие сайты

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

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

Ссылка на комментарий
Поделиться на другие сайты

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

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

Ссылка на комментарий
Поделиться на другие сайты

Гость
Эта тема закрыта для публикации ответов.
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...