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

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

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

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

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

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

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

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

33e201349fd34b33ab6129ca24cfa6cc.png

Решение
Как нам кажется, основное затруднение у участников вызвали два, на первый взгляд, противоречащих друг другу утверждения: с одной стороны, Герман Оскарович и Стив договорились передавать байты по очереди, с другой — они могут говорить и слушать одновременно. Тонкость в том, что если каждый из участников может отличить слово от тишины за 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» в битах.

f2c1b390f5564a33aba18d519e262e27.png

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

$\max(T1,T3)+T2$


bb9f905e415d4989bcacb034062f1aff.png

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

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


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

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



0574013d30474ca1b681bdbb20cbc5e7.png
Решение
Иннокентий повстречается на сеновале с Кондратием в том случае, если за 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 на решение этих задачек. А таких было много, что не может не радовать!

Комментарии (0)

© Habrahabr.ru