Биномиальный коэффициент в объяснении программы C

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

    #include<stdio.h>

int binomialCoeff(int n, int k)
{
    if(k == 0)return 1;
    if(n <= k) return 0;

    return (n*binomialCoeff(n-1,k-1))/k;
}

int main()
{
    int k;
    for(k=10;k>=0;k-=1)
    {
          printf("%d\n", binomialCoeff(10, k));
    }

Я понимаю, почему работает основная часть int, я просто не понимаю, как производится вычисление binomialCoeff. Я относительно новичок во всем этом программировании, поэтому спасибо за помощь!


c binomial-coefficients
person Rick    schedule 01.02.2016    source источник
comment
Чего вы не понимаете: математической формулы, рекурсии или синтаксиса Си?   -  person Jeff Hammond    schedule 01.02.2016
comment
Я не понимаю, как (n*binomialCoeff(n-1,k-1))/k соответствует формуле n!/((n-k)!k!)   -  person Rick    schedule 01.02.2016
comment
Первый использует рекурсию. Выведите рекурсивную версию последней формулы, и я думаю, вы увидите связь.   -  person Jeff Hammond    schedule 01.02.2016
comment
@Nick Напишите формулу для биномиального коэффициента с n-1 и k-1, а затем посмотрите, что произойдет, если вы умножите ее на n и разделите на k. Отличается ли она от формулы для биномиального коэффициента с n и k?   -  person bames53    schedule 01.02.2016
comment
Я поддерживаю ваш вопрос не потому, что он хорош, а потому, что я кое-что узнал из кода, который вы опубликовали.   -  person Mad Physicist    schedule 01.02.2016
comment
@MadPhysicist Вы имеете в виду en.wikipedia.org/wiki/Tail_call?   -  person Jeff Hammond    schedule 01.02.2016

Ответы (1)


arrow_upward
4
arrow_downward

Это на самом деле довольно элегантно.

Функция binomialCoeff является рекурсивной функцией с двумя базовыми условиями. Если k == 0, вы возвращаете только 1. Если n<=k, вы возвращаете 0. Итак, если это не так, вы вызываете ту же функцию, вычитая единицу из n и k. Это повторяется, что приводит к

n * (биномиальныйCoeff(n-1,k-1))/k

Скажем, N равно 10, а K равно 7.

ты получаешь

 10*(binomialCoeff(9,6)/7)

Просто для простоты давайте вызовем первый раз, когда binomialCoeff называется res1. Что упрощает:

10*(res1/6)

но res1 сам звонит binomialCoeff

в результате чего

 9*(binomialCoeff(8,5)/6)

который мы можем назвать res2

так что мы получаем

10*(res2/6)

и так далее, пока не будут выполнены базовые условия; в результате получается серия из n, умноженных вместе.

person Cripto    schedule 01.02.2016
comment
Спасибо за подробное объяснение, теперь понял! - person Rick; 01.02.2016