Это головоломка Interviewstreet:
У нас есть страна, в которой есть N городов. Каждый день мы выбираем 2 города, чтобы между ними не было дороги и строили дорогу между ними. Выбираем каждую пару несмежных городов с равной вероятностью. Пусть X - число дней, прежде чем мы получим связанную страну. Каково ожидаемое значение X? Выведите целочисленную часть ответа.
То, что они действительно задают, - это то, какое число ребер m необходимо (в среднем) для случайного графа G (n, m), чтобы подключиться.
После написания программы, которая фактически выполнила эксперимент, я придумал это "решение", которое проходит 9/10 тестов
$f = fopen('php://stdin', 'r');
$n = intval(fgets($f));
echo round(1.25 * $n * log($n, 10));
Так может ли это быть разрешено с помощью одной формулы? Каков правильный способ нахождения вероятности связности случайного графа?