July 21st, 2013

nyaload

Ящики и шарики. Хеш-таблица и её корзинки.

Простая задача с простым красивым ответом:
В n ящиков случайно разложили n шариков, n - большое число. Чему примерно равна доля (т.е. матожидание доли) пустых ящиков?
Подсказка: http://pastebin.com/5irShtmy

------------------------------
Более сложная:
В n ящиков случайно разложили k шариков (в n корзин-списков хеш-таблицы положили k элементов). Какова вероятность того, что пустых ящиков не осталось?

У меня не получилось вывести понятную формулу, получилось что-то вроде:
Подберем ai такие, что a1⋅1^k + a2⋅2^k + ... + an⋅n^k равно 0 для k=1,2..n-1, и равно n!/n^n для k=n. То что получится - будет формулой и для остальных k.
Ход решения: выписываем рекурсивную формулу для f(i,k) - количество способов разложить k шариков в n ящиков так, чтобы было занято ровно i ящиков. Получаем f(i, k) = (n-i+1)*f(i-1,k-1)+i*f(i,k-1) . Рисуем на бумаге в клеточку значения f, видим что есть множитель n*(n-1)*...*(n-i+1) в столбцах с фиксированым i, и второй который от n не зависит и является суммой j^k, j в 1..i.

Такое решение совершенно не даёт мне представления, как ведёт себя формула для больших n.
update: нашёл ответ, как называется эта рекурсивная формула и её явный вид. Метод: интуиция подсказала название, а в вики оппа, и почти оно - "число разбиений k шариков на n непустых ящиков", только ящики у меня "нумерованные", так что ещё надо умножить на (n!)
nyaload

test-driven testing

Старая программистская банальность: то, что не протестировано - не работает.

Следствие: если тест не протестирован, то он не тестирует.

Более тонкое следствие: "запустил у себя на компьютере на двух случаях" - это тоже тестирование. В противном случае - придётся жить с осознанием ужаса, что нельзя создать все элементы цепочки "тест для тестирования теста для тестирования теста ...".