Pull to refresh
38.45
Rating

О нетривиальном соблазнении тестировщицы Клавдии: задачки из буклета GridGain c JBreak и JPoint

GridGain corporate blog Entertaining tasks Mathematics *
Очередные Java-конференции JBreak и JPoint прошли на «ура». Здешние доклады всегда имеют резонанс, но многим запомнилось и кое-что ещё.

Буклет GridGain. Задачки про Грефа и Балмера, белорусского программиста с ведром картошки и, конечно, нетривиальное соблазнение тестировщицы Клавдии продолжают публиковать на различных ресурсах на радость автору, и многие уже даже не знают, каков их источник.


Рассказываем. Задачки были специально сочинены главным архитектором core-команды GridGain Сергеем Владыкиным и после решены всеми остальными её участниками.

Мы знаем, что у большинства посетителей конференций, основную сложность вызвала задача №1. Не расстраивайтесь, так же было и среди сотрудников GridGain! Но, справедливости ради, надо отметить, что на московском JPoint нашлось 3 человека, которые решили правильно все 4 задачки и передали свои результаты нам.

Страна! Знай своих героев! Это:

  • Алексей Остриков
  • Анна Гусенцова
  • Иван Смольянинов

Сегодня мы публикуем решения задачек: для тех, кто хорошо их помнит, и для тех, кто видит их впервые. Развлекайтесь!



Решение
Как нам кажется, основное затруднение у участников вызвали два, на первый взгляд, противоречащих друг другу утверждения: с одной стороны, Герман Оскарович и Стив договорились передавать байты по очереди, с другой — они могут говорить и слушать одновременно. Тонкость в том, что если каждый из участников может отличить слово от тишины за 0.05 секунды, то последний бит в байте можно различить за 0.05 секунды (даже если это было слово, кодирующее “1”) и начать передавать очередной байт уже в другую сторону. Поэтому время передачи первых семи бит в байте зависит от значения байта, а последний бит всегда можно передать за 0.05 секунды.

Далее остается только подсчитать среднее время передачи одного байта в каждую сторону. Так как значения битов “1” и “0” равновероятны, то время передачи одного байта в одну сторону составляет

${1\over2}({1\over7}+{1\over20})\times7+{1\over20}$


секунд, время передачи одного байта в другую сторону составляет

${1\over2}({1\over11}+{1\over20})\times7+{1\over20}$


секунд. Общее время передачи двух байт в обе стороны составляет

${1\over2}({1\over7}+{1\over11}+{1\over10})\times7+{1\over10}$


секунд, и, соответственно, пропускная способность в битах составляет

${16\over{1\over2}({1\over7}+{1\over11}+{1\over10})\times7+{1\over10}}\approx12.62 \text{ бит/сек.}$



Также стоит отметить, что проводить аналогичные вычисления с частотами некорректно, так как усреднение частот нарушает предположение о равномерном распределении “1” и “0” в битах.




Решение
Понятно, что в передаче шприца участвуют оба наркомана, поэтому параллельно могут быть выполнены только первый и третий шаги, а время этого параллельного выполнения будет равным максимальному из T1 и T3, при этом при передаче шприца ни первый, ни второй наркоман не могут выполнять других действий, то есть передача шприца будет выполняться последовательно с другими шагами. Поэтому ответ:

$\max(T1,T3)+T2$






Решение
В этой задаче нам требуется оптимизировать среднее количество картошки, попадающее в ведро за единицу времени, которое равно произведению количества картошки, собранной за эту единицу времени на вероятность того, что эта картошка попадет в ведро. Если x — расстояние программиста от ведра, то среднее количество картошки вычисляется по формуле

$V(x)=(0.5+x)(1-0.25x)=-0.25x^{2}+0.875x+0.5$


Квадратичная функция достигает своего экстремума (в данном случае — максимума) в точке

$-{b\over2a}={0.875\over2\times0.25}=1.75$





Решение
Иннокентий повстречается на сеновале с Кондратием в том случае, если за 90 минут тестирования Клавдия не воспроизведет баг, а при контрольном прогоне тестов QA-lead его все же обнаружит. При этом понятно, что каждое из испытаний независимо от другого, поэтому конечная вероятность будет равна произведению вероятностей каждого из событий. Так как пикап-лайн выводится в конце прогона тестов, то нас интересует только количество полных прогонов тестов за 90 минут, что равно

$\text{floor}({90\over17})=5$


Вероятность того, что баг не воспроизведется за 5 прогонов тестов составляет

$(1-0.11)^{5}$


а значит вероятность того, что после 5 успешных прогонов тестов баг воспроизведется на контрольном прогоне, равна

$(1-0.11)^{5}\times0.11=0.0614$



P.S. Спасибо за старания всем тем, кто нашел время на конференциях JPoint и JBreak на решение этих задачек. А таких было много, что не может не радовать!
Tags:
Hubs:
Total votes 28: ↑26 and ↓2 +24
Views 15K
Comments Comments 15

Information

Founded
2007
Location
США
Website
gridgain.com
Employees
101–200 employees
Registered
Representative
Ксения Романова