Здравствуйте, Pushkin, Вы писали:

P>Я напишу своё решение. Оно основано на неком трюке и в этом смысле, конечно, проигрывает, зато простое, забавное, и ответ сам получается, без угадывания.

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

#include <stdio.h>
#define MAX_SIZE 20

double G(long M,long N)
{
    static double dCache[MAX_SIZE+1][MAX_SIZE+1];
    if (dCache[M][N]<=0)
    {
        if (N==1) dCache[M][N] = 1;
        else if (M==N) dCache[M][N] = G(M,N-1);
        else dCache[M][N] = G(M-1,N) + G(M,N-1);
    }
    return dCache[M][N];
}

double F(long M,long N)
{
    static double dCache[MAX_SIZE+1][MAX_SIZE+1];
    if (dCache[M][N]<=0)
    {
        if (M==1 || N==1) dCache[M][N] = 1;
        else dCache[M][N] = F(M-1,N) + F(M,N-1);
    }
    return dCache[M][N];
}

void main(void)
{
    for (long l=2;l<MAX_SIZE;l++)
        printf("%.0f/%.0f\n",G(l,l),F(l,l));
}

Здравствуйте, Pushkin, Вы писали:

P>Итак "плохих" раскладов C(2N,N-1)
P>Их вероятность C(2N,N-1)/C(2N,N) = N/(N+1)
P>Вероятность "хорошего" расклада 1-N/(N+1) = 1/(N+1)

Все много проще:
число хороших раскладов (число Каталана — колл. правильных скобочных структур)= С(2N,N)/(N+1)
всего раскладов — С(2N,N)
итого вероятность равна 1/(N+1)

Для начала попроще:
Пусть есть по N "человеков" с 1,2,...K рублевыми монетами. Найти вероятность того, что не будет проблем со здачей.

И посложнее:
Колл. "челов" соотв. = N1,N2,...NK

Здравствуйте, IO, Вы писали:

IO>Здравствуйте, Pushkin, Вы писали:

P>>Итак "плохих" раскладов C(2N,N-1)
P>>Их вероятность C(2N,N-1)/C(2N,N) = N/(N+1)
P>>Вероятность "хорошего" расклада 1-N/(N+1) = 1/(N+1)

IO>Все много проще:
IO>число хороших раскладов (число Каталана — колл. правильных скобочных структур)= С(2N,N)/(N+1)

А ты без Каталана можешь это получить?
Мне как раз наоборот кажется, что приведённый вывод попутно даёт и такую замечательную вещь, как число правильных скобочных структур.

Здравствуйте, Pushkin, Вы писали:

P>А ты без Каталана можешь это получить?
P>Мне как раз наоборот кажется, что приведённый вывод попутно даёт и такую замечательную вещь, как число правильных скобочных структур.

А почему не воспользоваться готовой формулой, коль уж она есть и как раз подходит для данной задачи? Открывающая скобка — это человек с 1 руб., закрывающая — с 2руб.
Пользуемся ж мы напр. числом комбинаций C(M,N) и многими другими формулами.
Можно и без Каталана, но тогда надо его выводить .

Здравствуйте, IO, Вы писали:

IO>А почему не воспользоваться готовой формулой, коль уж она есть и как раз подходит для данной задачи? Открывающая скобка — это человек с 1 руб., закрывающая — с 2руб.
IO>Пользуемся ж мы напр. числом комбинаций C(M,N) и многими другими формулами.

Да нет, я не призываю всё время от печки танцевать.
Но всё-таки когда мы пользуемся C(N,M) мы ясно представляем, откуда оно берётся —
переставить всех вместе, а потом в каждой группе по отдельности.
С Каталаном хуже — там приходится на слово верить, искать...
Да и знать надо, наконец, что это такое — я вот только здесь это определение
(про скобочные выражения) услышал.

А может быть кто-нибудь знает еще интересные задачи по теорверу?..
Со своей стороны могу гарантировать плюсики за оригинальную задачу, интересное решение и то, что эта задача попадется с вероятностью 1 (почти наверное) по крайней мере одному студенту 3-го курса физфака МГУ на контрольной работе по subj.

Здравствуйте, Atilla, Вы писали:

A>А может быть кто-нибудь знает еще интересные задачи по теорверу?..

А как насчет моего поста "Re[6]: А теперь обобщим задачу"?

Здравствуйте, IO, Вы писали:

IO>А как насчет моего поста "Re[6]: А теперь обобщим задачу"?

хм... я ее пока еще не решил И вообще, задача должна решаться по крайней мере за 1 пару Мы ж не садисты!

Здравствуйте, Atilla, Вы писали:

A>А может быть кто-нибудь знает еще интересные задачи по теорверу?..
A>Со своей стороны могу гарантировать плюсики за оригинальную задачу, интересное решение и то, что эта задача попадется с вероятностью 1 (почти наверное) по крайней мере одному студенту 3-го курса физфака МГУ на контрольной работе по subj.

Можно из классической комбинаторной задачи размена рубля разными монетами сделать задачу по теорверу. Головная боль студентам, которые ее не видели раньше, гарантирована.