Обзор книги «Теоретический минимум по Computer Science. Всё, что нужно программисту и разработчику»

[sunnybear]

67,23%

[eastig]

double calc_prob(int i, double p) {
   if (i == 1)
     return p;
   return p*(calc_prob(i-1, p) + calc_prob(i-1, 1-p));
}

double prob_kill = calc_prob(5, 0.2) + calc_prob(5, 0.8) - pow(0.8, 5);

[eastig]

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

[vedenin1980]

67,23%

Если быть точным, то 67,232%

[abbb03]

Хорошая книженция, щас как раз читаю

[klvov]

У вас там описочка: Наглядно показано, как различаются алгоритмы с единичной, линейной, логарифмической, квадратичной и экспоненциальной сложностью. Рассказано, почему первые — самые лучшие, а вторые — самые худшие алгоритмы.

Имелось в виду, не "вторые", а "последние" - с экспоненциальной сложностью. Да, я программист и зануда, придирающийся к деталям. Ну а как, не скомпилируется же )

Ну и упоминание Кнута в конце выглядит как некоторый снобизм. Ни разу в жизни не встречал лично разработчика, который бы этот талмуд прочёл и проработал, а в интернете видел только какие-то комментарии, один был вроде от разработчика memcached, что мол, да, теоретически работа очень основательная и академическая, но сейчас её использовать для обучения компьютерщине уже поздно, потому что далеко ушла вперёд железячная часть. Что обращение к ячейке памяти во времена Кнута было всегда O(1), а сейчас обращение к L1, L2, L3, RAM, диску или сети - это шесть совсем разных вещей, что во времена Кнута были актуальны алгоритмы сортировок для данных, которые в одну сторону прочитывались с магнитных лент, а сейчас везде используются SSD, где рандомный доступ к ячейкам не представляет проблемы, и те старые алгоритмы уже не всегда актуальны; что гипотетический компьютер MIX - это, конечно, такой прообраз понятия "виртуальная машина", но что настоящая виртуальная машина вроде JVM состоит на 80% не из интерпретатора байт-кода, а из Memory Model, GC и JIT, и поэтому обосновано хвастаться "вот я читал Кнута и понял" могут, не знаю, 20 человек из Академии.

[sunnybear]

Ещё диски разные бывают... и сеть...

[funca]

Ну во-первых книжки у Кнута сами по себе красивые и с правильной типографикой (TeX довольно удачное его изобретение). А во-вторых, обрабатывать гигабайты с AWS S3 примерно то же самое, что 40 лет тому назад мегабайты с лент.

"Искусство программирования" конечно не справочник или stackoverflow, поэтому утащить фрагменты кода сразу в продакшн не получится. Это что-то среднее между энциклопедией и учебником.

[eimrine]

Жук-олень на обложке неправильно прорисован, а точнее все его конечности. На лапах должны быть крючки, без них он смотрится нелепо, и антенки тоже не такие. Не биолог, просто живу где есть вероятность их встретить, крайне дружелюбные создания как для жуков.

[AlexeyK77]

ну вот, жук с обложки не прошел даже проверку типов ;)
Потому что это не жук, а баг!!! ;)

[CrocoCat]

баг-олень!

[oji]

Баг-стекг!

[Vasile4ek]

Если башен пять, а шанс попасть до того, как враг достигнет ворот 20%, значит когда попадает 1 башня, 4 других не стреляют => 20%. И так будет всегда, и тут больше 20 нет, значит башни попадают всегда)

[1Tiger1]

Ну а расположение башен? Сектора и дальность обстрела? Скорость перезарядки? Путь движения захватчика и его скорость?

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

[pavel-karaganda]

Поражение каждой башней противника это события:
- происходящие одновременно
- не взаимозависимые
- не взаимоисключающие

0,2*5 - 0,2^5 = 0,99968

[vedenin1980]

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

По теории вероятности мы хотим найти верочтность, что хотя бы одна башня попадет, проще найти вероятность ни одна башня не попадет, а потом отнять ее от единицы.

Вероятность ни одна башня не попалет это (1-p)^n, где p — вероятность попадания, а n — количество башнн, итого итоговая вероятность хотя бы одного попадания 1 — (1-p) ^ n. При данных p и n ответ 67,232%.