Про грин-карты. Когда мне гугл подсунул эту новость (о том, что американцы отменили результаты лотереи с грин-картами из-за того, что 90% выигравших заявок были поданы в первые два дня приёма), я подумал — это что за алгоритм такой?
Думал долго, придумал два алгоритма. Первый я назвал «алгоритмом Единой России» (пример на перле)
my @winners = ();
MAIN: while (@requests) {
foreach $req (@requests) {
if ( int(rand(2)) ) {
print "winner is $req\n";
push @winners, $req;
@requests = grep { $_ != $req } @requests;
next MAIN;
}
}
}
Для тех, кто не знаком с перлом: берём заявки по очереди и для каждой бросаем монетку: орёл — выиграла, решка — не выиграла. Потом повторяем для остальных. Какая из заявок первой получила орла — та и победила. Почему это называется методом «Единой России» — потому что она получает первое место в бюллетенях как раз в половине случаев. По тексту на ленте сильно похоже, что там использовался именно такой алгоритм.
Тут я решил, что должны быть другие кривые алгоритмы, подумал-подумал, придумал совершенно убогий алгоритм: разбить пул заявок на несколько частей (прямо по порядку, первые 100, вторые 100), выбрать наугад одну часть и набрать из неё победителей. Но это надо быть круто упоротым, чтобы такой алгоритм использовать.
Дальше моя инженерная мысль не пошла. Помогите придумать ещё алгоритмов.
