カタラン数をC言語で求めたい。

Question

実現したいこと
与えられた n に対するカタラン数 C_n を出力するプログラムを作りたいです。
n はコマンドライン引数として与えられます。
(n = 0, 1) C_n = 1　　　　　　　　　
(n>=2) C_n = Σ_{i=0}^{n-1} (C[i] * C[n-i-1])

コード

#include <stdio.h>
#include <stdlib.h>

int ni(int x) {
  int a, result = 1;
  for(a = 1; a < 2*x + 1; ++a) { result *= a; }
  return result;
   }
int kai(int y) {
  int b, result = 1;
  for(b = 1; b < y + 2; ++b) { result *= b; }
  return result;
    }
int fact(int z) {
  int c, result = 1;
  for(c = 1; c < z + 1; ++c) { result *= c; }
  return result;
    }
int main(int argc, char *argv[]) {
  int n;
  n = atoi(argv[1]);
if (n == 0) {
  printf("%d\n", 1);
    } else {
  printf("%d\n", ni(n)/kai(n)/fact(n));
    }
return 0 ;
}

カタラン数C_n = (2n)!/(n+1)!n!で求めることができるので、初めに一つ一つの値を求めて、最後に式に当てはめるようにしました。
発生した問題
n = 6までは正しく求められていますが、 n = 7以降から違う値が出るようになりました。どこが原因なのかどうか教えてください。

 ./a.out 1
1
 ./a.out 2
2
 ./a.out 3
5
 ./a.out 4
14
 ./a.out 5
42
 ./a.out 6
132
 ./a.out 7
6
 ./a.out 8
0
 ./a.out 9
0

Comments

[y_waiwai]

具体的に、出る値と出るべき値を提示しましょう

[y_waiwai]

そして、そのそれぞれにおいての各関数の戻り値を出力するようにして、それも提示してください

Answer 1

n = 7 のとき (2n)! = 14! = 87,178,291,200 となる。
この値は、符号付き32bit整数の上限値 2^31 - 1 = 2,147,483,647 よりも大きい。

よって、関数 int ni(int x) は引数xが7以上のときはオーバーフローとなり、正しい演算結果を返さない。

---

カタラン数は漸化式で
C[0] = 1
C[1] = 1
C[n + 1] = (2(2n + 1) / (n + 2))・C[n]
と表すことができますので、再帰関数として記述すると良いように思われます。

【参考】カタラン数 - Wikipedia

Comments

[hika2O21]

コードの間違いではなかったのですね。なぜ正しい値が出ない理由を丁寧に解説していただいてありがとうございます。教えていただいた方法で記述してみようと思います。

Answer 2

「カラタン数」というものについては初耳なので知りません。
またネットでちょっと検索してみましたが、全然違うものばかり出てきたのですぐ断念しました。

(n>=2) C_n = Σ_{i=0}^{n-1} (C[i] * C[n-i-1])

この定義の意味もちょっと理解できていません ({i=0}のあたり)。

以上前提での回答なので、見当はずれかもしれませんが...

おそらく、べき乗とか出てくるので、オーバーフローと思われます。
変数がすべてintで定義されているので32ビットと思われますが、
これを64ビットとかに修正して改善されれば、ビンゴです。

C言語の場合、64ビット変数の定義はお使いのコンパイラによって異なるので、調べてください。

64ビット変数に修正しても、べき乗を使っていることから、nの値を大きくするとまたすぐにオーバーフローする可能性があります。

Comments

[hika2O21]

教えていただきありがとうございました。64ビットとかに修正して、試してみようとおもいます。