На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Сочетания рекурсией
    Знаю, существует рекурсивный алгоритм определния числа сочетаний.
    ExpandedWrap disabled
      C(n,m)=n!/[m!(n-m)!]


    Это функция, она возвращает 1 или 0 + результат рекурсии.
    Типа:
    ExpandedWrap disabled
      long c(n,m)<br>{<br>   if(.............)return c(n_,m_)+0  else<br>   if(.............)return c(n_,m_)+1<br>}
    Точно не помню.

    Вопрос: помогите вспомнить рекурсивный алгоритм вычисления количества сочетаний
    Сообщение отредактировано: Tishaishii -
      не могу, честно говоря, понять, откуда там 0 и 1 :)

      вот рекуррентное соотношение: C(k, n) = C(k-1, n-1)+C(k, n-1)
      Доопределены C(0,n) = C(n,n) = 1, С(k<0,n) = C(k>n,n) = 0 для любого n

      тогда

      ExpandedWrap disabled
        unsigned long C(int k, int n)<br>{<br>    if((0 > k) || (n < k))<br>        return 0;<br>    if((1 == n) || (0 == k) || (n+0 == k))<br>        return 1;<br>    return C(k-1, n-1) + C(k, n-1);<br>}


      --

      Кстати, при той струкутуре рекурсивной функции, которая у тебя приведена, вычисление C(16,32) потребует глубины рекурсии примерно в 600 млн вызовов :)
      Сообщение отредактировано: Visitor -
        да, надо заводить дополнительный массив для  уже вычеслиных сочетаний, и на каждой глубине рекусрии проверять, не вычислено ли уже, если да, то возвращаться и брать из массива. так быстрее будет! ;D
          Благодарю.
            yo! пожалуйста! ;D
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0279 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:39 GMT ]