質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

5回答

26735閲覧

組み合わせnCrの効率的な計算方法、募集!

RyuSA

総合スコア131

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2017/04/16 14:57

nCr(組み合わせ/コンビネーション)の高速な計算をしたい!

今、諸事情でnCrの高速な計算方法を探索しています。
以下のコードは、ありきたりなnCrの求め方ですが、もしもっと高速に計算することができるアルゴリズム/コードがあれば教えてほしいです。(キャッシュ併用するものでも可)

cpp

1long nCr(int n, int r) { 2 long ans = 1; 3 for (int i = n; i > n - r; --i) { 4 ans = ans*i; 5 } 6 for (int i = 1 ; i < r + 1; ++i) { 7 ans = ans / i; 8 } 9 return ans; 10}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

ベストアンサー

時間計算量はO(n)なので劇的に速くはならんけど、for-loopいっこで済むからちっとはマシかと。

C++

1#include <cstdint> 2 3uintmax_t combination(unsigned int n, unsigned int r) { 4 if ( r * 2 > n ) r = n - r; 5 uintmax_t dividend = 1; 6 uintmax_t divisor = 1; 7 for ( unsigned int i = 1; i <= r; ++i ) { 8 dividend *= (n-i+1); 9 divisor *= i; 10 } 11 return dividend / divisor; 12} 13 14#include <iostream> 15int main() { 16 std::cout << combination(10,5); // expected: 252 17}

投稿2017/04/16 23:10

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

回答でなくて恐縮ですが・・・

n回以下の計算で求められる方法があるかどうか自分は知らないのですが、longで結果を得るとしてもnを大きくしていくとnCrはすぐにオーバーフローするので、事実上それほど高速な計算法が必要ないようにも思えました。

もしメモリーが許すなら必要な範囲分だけあらかじめ配列に記憶しておくといった方法でも実は間に合うのではないか・・・そんな風な発想の転換もありかなと思いました。
20!あたりでlongの範囲の限界までいっちゃうのでnCrをそこまで全部計算しておいてもそれほどメモリーを食わないのではないかと思ったわけです。

投稿2017/04/16 15:22

編集2017/04/16 22:40
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

1回の呼出しでボトルネックになってるとは思えないので、次回以降のためにメモしておくといいかと。

long dp[max][max]; long nCr(int n, int r) { if(n==r) return dp[n][r] = 1; if(r==0) return dp[n][r] = 1; if(r==1) return dp[n][r] = n; if(dp[n][r]) return dp[n][r]; return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1); }

投稿2017/04/17 02:47

nullbot

総合スコア910

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2017/04/17 02:54

ただの表引きになるのでめちゃ速かろうけど、問題は配列のサイズですよね。 n,r が 最大1万だと表のサイズは一億すなわち400GBってことに。
nullbot

2017/04/17 04:27

確かに現実的では無いですね。
episteme

2017/04/17 05:00

それと、n,rが大きいと再帰時にスタックが破裂する恐れが。
guest

0

小さな数では速くなるかどうかわかりませんが、大きな数の場合は 組合せの数 の方法で高速化できるようです。

高速化したい理由は、ループの中で何度も計算するからではないかと思いますが、その場合はここをチューニングするより、同じ計算を二度としないよう、一度求めた解をキャッシュすることで劇的に高速化できる場合があります。

投稿2017/04/16 22:42

編集2017/04/16 22:51
Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

投稿2017/04/17 08:50

PineMatsu

総合スコア3579

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問