Задача о попсовой группе - решение

[atly]

Сама задачка №4 тут.

"Если много выпить, то блондинки и брюнетки подчиняются статистике Ферми - Дирака. Если ещё и они много выпьют - то статистике Бозе - Эйнштейна."
"Физики, сейчас дошутитесь!" - М.: Наукообразие, 2008 - т.3Во-первых, будем считать, что продюсер нумирует случайным образом своих подчинённых от 1 до 15 и запускает их в номерном

Comments

[atly]

а ты рекурсию вручную разворачивал? ;)

[atly]

ага, то есть методом Монте-Карло решал :) Понятно

[atly]

:))

[rexy_craxy]

Какие еще сутки? Ветки надо вовремя отсекать. Карандашом на большой бумажке дерево такой глубины строится за пол-часа.

[kouzdra]

Чему там подвешивать - порядок дам в группе не важен (он просто добавляет множитель) - а так - перебор минимален:

# include

int main () {
int N = 15;
int M = 5;
int sum = 0;
int all = 0;
for (int i = 0; i != 1 << N; ++ i)
{
bool ok = true;
int n = i;
int ones = 0;
for (int j = 0; j != N; ++ j, n >>= 1)
{
ones += (n & 1);
if (ones * 2 == j+1)
ok = false;
}
if (ones == M)
all ++, sum += ok;
}
printf ("Sum = %d, all=%d, %%=%g\n", sum, all, float (sum)/all);
return 0;
}

[atly]

о, ужос :)

[rexy_craxy]

А прокомментировать? Иногда я "олимпиадников" убивать готов: почему-то они уверены, что шевеление мозгой по поводу надуманных задачек доставляет удовольствие и нормальным людям.

[kouzdra]

Ну просто берем все двоичные числа до 2^15 (блондинок и брюнеток изображают нолики и единички) и проверяем совершенно в лоб насчет драки и того, что единичек ровно 5.

[atly]

это я понял :)

[rexy_craxy]

Выглядит компактно, но ПОЛНЫЙ перебор (без отсечений) это слишком.

просто отсечения при 32 000 вариантов

[sternenzaehler]

экзистенциального смысле в данном случае не имеют. по большому счету они не имели бы смысла и мри 32 000 000 и при 32 000 000 000 вариантов- все эти цифры 1.7 ггц машина (безнадежно устаревшая) обработает за микросекунды-секунды-минуты.
при 32 000 000 000 000 уже можно думать об оптимизации.

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

но это философия:):):):):):

просто над этим народ не особо задумывается.