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

в 9:42, , рубрики: jbreak, jpoint, JUG, Блог компании GridGain, задачи для программистов, задачки, занимательные задачи, Занимательные задачки, математика

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

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

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

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

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

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

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

Решение

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

$max(T1,T3)+T2$

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

Решение

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

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

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

$$display$$-{bover2a}={0.875over2times0.25}=1.75$$display$$

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

Решение

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

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

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

$(1-0.11)^{5}$

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

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

P.S. Спасибо за старания всем тем, кто нашел время на конференциях JPoint и JBreak на решение этих задачек. А таких было много, что не может не радовать!

Автор: artemshitov

Источник

Поделиться

* - обязательные к заполнению поля