Стажировка аналитиком в Яндексе: разбор тестовых задач

[yrustt]

В задаче 1, по-моему, можно просто посчитать P(в какой-то из 90-х дней) = 1 — P(не в какой из 90 дней) = 1 — произведение P(не в i день) = 1 — произведение (1 — P(в i день)). Можно вывести в аналитическом виде.

В задаче 4, вроде бы, можно посчитать вероятность P(количество просмотренных подарков <= k) = C_100^k * k^100 / 100^100. Тогда можно высчитать P(количество просмотренных подарков = k) = P(количество просмотренных подарков <= k) — P(количество просмотренных подарков <= k — 1). И в этом случае тоже можно вывести аналитическую формулу.

В задаче 5 можно воспользоваться выводом аналитического вида для чисел Каталана.

[AAbrosov]

задача 1

prob1 = 1
prob2 = 1
for i in range(1, n+1): # Для каждого дня
    prob1 *= 1 - (1 / (i + 1))
    prob2 *= 1 - (1 / (i + 1) ** 2)
print(1 - prob1)
print(1 - prob2)

[nice_one]

Действительно, так намного проще и логичнее, спасибо

[charypopper]

Задача для аналитика — скрыть решение в спойлер. Для тех людей кто хочет сам подумать, а не краем глаза из-за скорочтения что-то подмечать

[Sergey_Kovalenko]

Задачу с елкой можно решить очень просто, если вспомнить о замечательном пределе.
Смотрите: в каждой конкретной попытке вероятность не взять конкретного оловянного солдатика равно 1 — 1/100. Вероятность того, что этот конкретный оловянный солдатик так и останется нетронутым за 100 попыток есть (1 — 1/100)¹⁰⁰ = 1/e. Свяжем с каждым подарком случайную величину, которая равна 1, если подарок за 100 попыток так и не тронули и 0 — в обратном случае. Матожидание суммы равно сумме матожиданий, даже если величины зависимы. Матожидание числа нетронутых подарков будет равно 100/e.

Задача с мостами имеет очень простое решение (вычислительно простое и идейно простое), если использовать метод «конденсации вершин»: начинаем с любой вершины строить путь без повторений ребер (по пройденым ребрам ходить нельзя), до тех пор пока не обнаружим цикл (вернемся в вершину, которую уже посещали) или не упремся в край (вершину, которая соеденина с графом единственным ребром). Если нашли цикл, то производим «конденсацию» всех его вершин в одну: все внешние ребра цикла заменяются на ребра, ведущие к новой вершине, а все внутренние удаляются. Если пришли к крайней вершине, то отрезаем ее от графа. Алгоритм конденсации завершит свою работу когда граф будет состоять из отдельных не связанных друг с другом финальных конденсированных вершин. Каждая компонента циклической связности графа (искомый субъект государства) будет состоять в точности из исходных вершин, которые сконденсировались в одну из финальных.

[Sergey_Kovalenko]

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

Неплохое знакомство с теорий алгоритмов: Ахо и соавторы «Алгоритмы, построение и анализ».

Теория вероятности: Феллер «Теория вероятности и ее применения» — там очень много на тему случайного блуждания

Теория графов: Кристофидес «Теория графов. Алгоритмический подход» — тут азы, алгоритмы немного примитивны, поэтому перед тем как применять их на практике погуглите современные статьи.

[nice_one]

Большое спасибо, обязательно почитаю

[lightln2]

В первой задаче про аналитика дроби же сокращаются:
1) P = 1 — ( 1/2 * 2/3 * 3/4 *… * 89/90 * 90/91 ) = 1 — 1/91 = 90/91 ~ 0.989
2) P = 1 — ( (1*3)/(2*2) * (2*4)/(3*3) * (3*5)/(4*4) *… * (89*91)/(90*90) * (90*92)/(91*91) ) = 1 — 1/2 * 92/91 = 45/91 ~ 0.495

[baskins]

а это точно задачи для аналитика?

[Sergey_Kovalenko]

Даже для стажеров аналитиков нужен какой-то минимальный тест на интеллект. Была бы способность — остальному научат, я думаю.