組み合わせと剰余算について

Question

初学者です。先生からいただいた問題です。
組み合わせの計算をし、その値を１００で割ったときの余りを出すプログラムを作りたいのですが、再帰を使うって入力値を大きくすると、再帰処理の回数が非常に大きくなってしまうのとてつもなく遅くなってしまいます。
またループ処理を使ってみても、調べてみたらオーバーフロー？を起こしてしまいマイナスの値※が出たり、０がでたりしてしまいます。
剰余算をしながら？計算をすると値がオーバーフローを起こさずに表現できると思うのですが,（ex (a+b)% d = a%d + b%dのような感じ）いまいちコードへの表現の仕方わかりません。どのように工夫する必要があるのかご回答いただけたら幸いです。

※
./a.out
123123 12332
-1

#include <stdio.h>

int com(int n, int k){

  if(k==0 || k==n){
    return (1);
  }else if (k==1){
    return (n);
  }else{
  return (com(n-1, k-1) + com(n-1, k));
  }
}
  


int main(void){
  int n, k;

  scanf("%d %d", &n, &k);
  printf("%d\n", com(n, k)%100);

  return 0;

}

#include <stdio.h>

int combi(int n, int r)
{
    int i;
    int k=1;

    for(i=1; i<=r; i++){
        k = k*(n-i+1)/i;
    }

    return k;
}
int main()
{
    int n, r;
    scanf("%d %d", &n, &r);
  
    printf("%d\n", combi(n, r)%100);
}

Comments

[mjk]

何の練習問題かを明記した方が良いと思います。
見てる人にはそれが何の練習問題なのか分かりません。
学校の宿題なのか、友達に出された問題なのか、オンライン上の問題なのか、著書の問題なのか・・・

[mjk]

>>先生からいただいた問題です。
先生に聞きましょう。

[mjk]

https://teratail.com/help/avoid-asking
推奨していない質問
学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。

[akira-]

学校の課題というより先生からいただいた大量の練習問題のうちの１つです。先生にはヒントはいただきましたが、ここまでが限界でした。

[Bull]

練習問題ということなのでヒントだけですが、「剰余を求めながら計算する」という考え方は間違っていないです。
ただし、途中に除算が入ると正しく答えが求まらないです。
加算だけで組み合わせの数を求める方法を考える必要があります。

最初のソースコードはおそらく、答えが求まるような気がします。
しかし、質問にも書かれている通り再帰呼び出しが、かなり深くなるので時間がかかりますね。

[mjk]

もしかすれば回答つくかもしれませんが・・・
長い目で見た場合に本人の為にならないという考え方があるのか、テラテイルでは課題の質問には回答がつきにくかったり、そういう質問に回答すると低評価されたりする慣習？のようなものがあるのかもしれません。
いきなり低評価されて驚かれないように質問する時は気をつけた方が良いと思いました。
（テラテイルを利用するのに慣れているようなので余計なお節介だったかもしれませんね）

[akira-]

みなさまありがとうございました。すこし時間をかけて考えてみます。

Answer 1

パスカルの三角形を利用しましょう。

C(0,0) = 1
C(1,0) = 1, C(1,1) = 1
C(2,0) = 1, C(2,1) = 2, C(2,2) = 1
C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3) = 1

C(n,k) = (C(n-1, k-1) + C(n-1,k)) % 100 を使って、
C(123123,0), C(123123,1), ... まで求めます。

2次元配列は要りません。
static int c[1000000] = { 1 }; を用意し、
n が 1 の時、c[1] = 1
n が 2 の時、c[2] = 1, c[1] = (c[0] + c[1]) % 100
n が 3 の時、c[3] = 1, c[2] = (c[1] + c[2]) % 100, c[1] = (c[0] + c[1]) % 100

Comments

[akira-]

#include <stdio.h>

static int c[1000000] = {1};

int main(void){

int n, r, i, j, l;
scanf("%d %d", &n, &r);

for(l=1; l<=n; l++){
c[l]=1;
}

for(i=1; i<=n; i++){
for(j=i-1; j>0; j--){
c[j] = (c[j-1] + c[j]) % 100;
}
}

printf("%d\n", c[r]);

return 0;

}

コード書くことができました。ありがとうございました。