Начало обсуждения вот тут — http://rsdn.ru/forum/job/4321303.1.aspx

Автор: Young
Дата: 27.06.11

Хочется понять, насколько некоторые вещи кажущиеся мне очевидными — могут быть не очевидны. Ибо я тоже спрашивал такие задачи на собеседования.

Хочу обсудить сейчас более узкую часть, а именно разновидность задач на взвешивание монеток.
Не берем сейчас "сложные" случаи, возмем простую задачу в вобщем виде.

Опять же не будем сосредотачиваться на чисто логических решениях данной задачи типа полного перебора и индукции — не программисткое это дело.
Попробуем понять как ее может решить чистый программист(инженер).

И так, есть N монеток, известно что одна фальшивая и что она _легче_. За сколько взвешиваний на "бинарных" весах можно определить ее.

И так, есть три утверждения

1. Для описания состояния N монет из описанной задачи нам нужно не менее ln(N) бит информации.
2. Каждое взвешивание нам дает не менее ln(3) бит информации
3. Общее количество необходимых взвешиваний не больше чем ln(N)/ln(3)

Собственно вопрос — является ли каждое утверждение очевидным для хорошего программиста? Или требовать понимания таких вещей это не так.

Разобью чуть на подпункты

1.1 Каждая монета имет два состоянии — фальшивая или нет
1.2 Состояние монеты равновероятны

Вопрос 1а — очевидны эти утверждения?
Вопрос 1б — очевидно что из этих утверждений следует утверждение 1?

2.1 Каждое взвешивание может иметь три исхода — левая чаша тяжелее, правая тяжелее, равны
2.2 Каждый исход для любой монетки равновероятен

Вопрос 2а — очевидны эти утверждения?
Вопрос 2б — очевидно что из этих утверждений следует утверждение 2?

Вопрос 3 — очевидно ли что из пунктов 1 и 2 следует пункт 3?

Ну и вопрос, возникший в процессе написания — должен ли хороший программист понимать что такое "равновероятный исход события"?

P.S. Вопросы для статистики.

P1 — знаете ли вы теорему Котельникова (она же теорема Найквиста — Шеннона или теорема отсчётов) — т.е. не доказательсов, а самое утверждение, пускай без имен — сам принцип
P2 — проходили ли ее в школе/институте?
P3 — если вы об этом услышали в первый раз, понятно ли вам интуитивно определение энтропии по Шеннону, и сама теорема Котельника