1

コード：

#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;
}

基本的なケースは理解できると思います。n に 0 を使用し、k=n の場合、結果は 0!/0! になります。これは = 1 です。したがって、1 を返します。

しかし、私はコードのこの部分を理解できません:

 return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

n の値が 5 で k の値が 2 の場合、結果は 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;
}
4

3 に答える 3

0

二項係数の特性の 1 つは次のとおりです。 C(n, k) は、すべての 1 <= k <= n-1 に対して C(n-1,k-1) + C(n-1,k) として記述できます。 .

したがって、C(3,2) = C(2,1) + C(2,2) または 3 = 2 + 1

これは、共有した単純な再帰の例で使用されているものです。

2番目の問題については、なぜ問題が発生するのかわかりません。

于 2016-03-20T12:21:47.230 に答える
0

しかし、なぜ足し算を使うのでしょうか?

プログラミングというより数学の問題ですが、よく知られている二項係数計算の再帰的な公式があります。そして、まさにこの式があなたのプログラムで使用されています。

キーボードから「n」と「k」を設定するとプログラムが動作しないのはなぜですか

入力に ​​std::istream を使用し、出力に printf を使用することを除いて、コードは正しいように見えます。正確に何が機能しないのですか？n >= k と入力しますか?

于 2016-03-20T12:04:20.560 に答える
0

return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

パスカルの三角形を覚えていますか? まさにこの漸化式を加算で使用します。

ただし、この三角形を作成していないことがわかりますが、再帰を使用しながら、再帰的に二項係数の一部を何度も計算しようとしています。すでに計算された結果を記憶すると、プログラムのパフォーマンスが大幅に向上する場合があります。2番目の質問に当てはまるかもしれません：

キーボードから「n」と「k」を設定すると、プログラムが動作しないのはなぜですか。このような：

n動作するはずですが、かなり大きなとを入力すると、プログラムが終了するまでに時間がかかる場合がありkます。実行時間の複雑さは O(n 2 ) です。n > 30実行時間が長いことに気付くかもしれません。

于 2016-03-20T12:20:11.677 に答える