рекурсия — непонимание с ++ рекурсивной функции биномиального коэффициента
код:
#include<stdio.h>
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;
else
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
int main()
{
int n = 5, k = 2;
printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
return 0;
}
Я думаю, что могу понять базовый случай. Когда мы используем 0 для n и k = n, результат равен 0! / 0! который = 1. Таким образом, мы возвращаем 1. формула
Но я не могу понять эту часть кода:
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
При значениях 5 для n и 2 для k я получаю результат 10. (При замене в формуле).формула
Но почему мы используем дополнение?
И еще кое-что. Почему программа не работает, когда я установил «n» и «k» с клавиатуры?
Как это:
int main()
{
int n,k;
cin>>n;
cin>>k;
printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
return 0;
}
Решение
Одним из свойств биномиальных коэффициентов является то, что:
C (n, k) может быть записано как C (n-1, k-1) + C (n-1, k) для всех 1 <= к <= n-1.
Итак, C (3,2) = C (2,1) + C (2,2)
Или 3 = 2 + 1
Это то, что используется в простом примере рекурсии, которым вы поделились.
Что касается вашей второй проблемы, не уверен, почему у вас должны быть какие-либо проблемы.
Другие решения
Но почему мы используем дополнение?
Это скорее вопрос математики, чем программирования, это хорошо известно рекурсивная формула для расчета биномиального коэффициента. И именно эта формула используется в вашей программе.
Почему программа не работает, когда я установил «n» и «k» с клавиатуры
Код выглядит правильно, за исключением того, что вы используете std :: istream для ввода и printf для вывода. Что именно не работает? Вы вводите n> = k?
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
Помните Паскаль Треугольник? Он использует именно эту формулу повторения с дополнением.
Однако я вижу, что вы не строите этот треугольник, а просто рекурсивно пытаетесь вычислять некоторые из биномиальных коэффициентов снова и снова, используя рекурсию. Запоминание уже рассчитанного результата может значительно улучшить производительность вашей программы. Это может быть случай для вашего второго вопроса:
Почему программа не работает, когда я установил «n» и «k» с клавиатуры. как это:
Это должно работать, но ваша программа может закончиться долго, если вы введете довольно большой n а также k, Время выполнения сложность O (n2). С n > 30 Вы можете заметить, что время выполнения долго.