nCrを求める関数combination(n,r)をC言語で作りたいのですが、どうすればよいか教えてください。また、参考となるようなサイトを教えてください。僕の作った関数だと、すぐに桁あふれになってしまいます。そのことを考慮して、桁あふれにになりにくい関数もつくりました。これは パスカルの三角形の関係を使ったnCr=n-1Cr +n-1Cr-1の関係を使っての再帰関数です。しかし、これだと結果を出すのに時間がかかってしまいます。僕がつくった関数をいくつか出しておきますのでいい考えがあれば教えてください。64C32が高速に正確に出れれば最高です。
long combination(int n,int r)
{
int i, a, b;
long c;
if(r>n/2) r=n-r;
a= n;
b= 1;
c= 1L;
for(i=0 ;i< r ;i++){
c= c* a/ b;
a--;
b++;
}
return c;
}
これはすぐに桁あふれになってしまう。
long combination(int n,int r)
{
int i, a, b;
double c;
if(r>n/2) r=n-r;
a= n;
b= 1;
c= 1.0;
for(i=0 ;i< r ;i++){
c= c/b*a;
a--;
b++;
}
return (long)c;
}
これはcをdoubleにして計算する分、丸めこみが生じ誤差がでる。
long combination(int n,int r)
{
long c;
if(r> n-r) r=n-r;
if(r==0) return 1;
else if(r==1) return n;
else{
c= combination(n-1,r-1)+ combination(n-1,r);
return c;
}
}
これは誤差は出ず正確であるがいかんせん遅い!
No.9ベストアンサー
- 回答日時:
お詫びに:
#include <cstdio>
__int64 combination(int n, int r) {
__int64* work = new __int64[n+1]; /* n は 64 まで */
for (int i = 0; i <= n; i++) {
for (int j = i - 1; j > 0; j--) {
work[j] += work[j - 1];
}
work[i] = 1;
}
__int64 result = work[r];
delete[] work;
return result;
}
namespace std {}
using namespace std;
int main() {
for ( int i = 0; i < 33; ++i )
printf("64C%d = %I64d\n", i, combination(64,i));
return 0;
}
----- 結果 -------
.....
64C25 = 401038568751465792
64C26 = 601557853127198688
64C27 = 846636978475316672
64C28 = 1118770292985239888
64C29 = 1388818294740297792
64C30 = 1620288010530347424
64C31 = 1777090076065542336
64C32 = 1832624140942590534
だそうです。# VC6でコンパイル/実行
なんどもお返事ありがとうございます。大変感謝しております。64C32 = 1832624140942590534 と分かっただけでも大変参考になりました。これから自分がつくらないといけないものは1024C512なのでガンバってみます。これからも何かあればよろしくお願いします。
No.7
- 回答日時:
>しくしく、吹っ飛びます。
>
>> for (i = 0; i <= n; i++) {
>> for (j = i - 1; j > 0; j--) {
>
>ココで j が -1 になるので、
>work[-1] += work[-2]; // ぶっとびー
for の条件式 j > 0 によって、負のインデックスでのアクセスはありえません。
No.6
- 回答日時:
> それを以下のようにコーディングします。
しくしく、吹っ飛びます。
> for (i = 0; i <= n; i++) {
> for (j = i - 1; j > 0; j--) {
ココで j が -1 になるので、
work[-1] += work[-2]; // ぶっとびー
No.5
- 回答日時:
パスカルの三角形の再帰を展開してみたらどうでしょうか?
配列内の値がどのように変化するかを 7Cr まで書きます。
0Cr: 1
1Cr: 1 1
2Cr: 1 2 1
3Cr: 1 3 3 1
4Cr: 1 4 6 4 1
5Cr: 1 5 10 10 5 1
6Cr: 1 6 15 20 15 6 1
7Cr: 1 7 21 35 35 21 7 1
それを以下のようにコーディングします。
ただし、64C32 だと 32bit の long ではオーバーフローするので、n の範囲を制限するか、より大きな型を使用してください。
long combination(int n, int r)
{
long work[65]; /* n は 64 まで */
int i, j;
for (i = 0; i <= n; i++) {
for (j = i - 1; j > 0; j--) {
work[j] += work[j - 1];
}
work[i] = 1;
}
return work[r];
}
大変ありがとうございます。やはり、誤差がでないのはパスカルの三角形ですね。ほかにいろいろかんがえてみます。大変参考になります。また、何かあればよろしくお願いします。
No.4
- 回答日時:
約分だけでなく#3で言われているように素因数分解もつけてみました。
しかしやはり桁あふれをおこします。除算を複数回行うとどうしても誤差が生じてしまうので、誤差なしで求めるには無限桁計算のルーチンが必要になりますね。ということで乗算部分までは作ってみました。あとは無限桁の除算ルーチンを加えれば完成(?)です。
ただ無限桁の除算ルーチンは今まで作れたことがないので私にはできません。
voidSoinsuu(int nData,CDWordArray& adwElement)
{
inti;
intj;
intn;
boolb;
if(nData == 1)
return;
b = false;
n = int(sqrt(nData) + 1);
for(i = 2; i <= n; i += 2)
{
if(i == 4)//2で1回、次からは2n+1で処理を
i--;//行なうように4のときに1を減算
j = 0;
while(1)
{
if(nData % i == 0)
{
j++;
nData /= i;
adwElement.Add(i);
b = true;
}
else
{
break;
}
}
}
if(b == false)
adwElement.Add(nData);
return;
}
voidexee(CDWordArray& adwData1,CDWordArray& adwData2)
{
inti;
intj;
for(i = 0; i < adwData1.GetSize(); i++)
{
for(j = 0; j < adwData2.GetSize(); j++)
{
if((adwData2[j] % adwData1[i]) == 0)
{
adwData2[j] /= adwData1[i];
adwData1[i] = 1;
break;
}
}
}
}
//adwData は0~9999まで!
voidMul(CDWordArray& adwResult,CDWordArray& adwData)
{
inti;
intj;
DWORDdwUp;
adwResult.RemoveAll();
adwResult.Add(1);
dwUp = 0;
for(i = 0; i < adwData.GetSize(); i++)
{
if(adwData[i] != 1)
{
for(j = 0; j < adwResult.GetSize(); j++)
{
adwResult[j] *= adwData[i];
adwResult[j] += dwUp;
dwUp = 0;
if(adwResult[j] >= 10000)
{
dwUp = adwResult[j] / 10000;
adwResult[j] %= 10000;
}
}
if(dwUp > 0)
{
adwResult.Add(dwUp);
dwUp = 0;
}
}
}
for(i = adwResult.GetSize() - 1; i >= 0; i--)
{
TRACE("%d ",adwResult[i]);
}
TRACE("\n");
}
void main()
{
inti;
intn;
intr;
DWORDdwResult;
DWORDdwBuff;
CDWordArrayadwUp;
CDWordArrayadwDown;
CDWordArrayadwUp2;
CDWordArrayadwDown2;
n = 64;
r = 32;
for(i = n - r + 1; i <= n; i++)
adwUp.Add(i);// n(n-1)(n-2)...(n-r+1)
for(i = 1; i <= r; i++)
adwDown.Add(i);// r!
exee(adwUp,adwDown);//素因数分解する前に簡単な約分
for(i = 0; i < adwUp.GetSize(); i++)
Soinsuu(adwUp[i],adwUp2);//分子の素因数分解
for(i = 0; i < adwDown.GetSize(); i++)
Soinsuu(adwDown[i],adwDown2);//分母の素因数分解
exee(adwUp2,adwDown2);//素因数分解してから約分
dwResult = 1;
for(i = 0; i < adwUp2.GetSize(); i++)
{
if(adwUp2[i] != 1)
{
dwResult *= adwUp2[i];
TRACE("%d * ",adwUp2[i]);
}
}
TRACE("\n");
dwBuff = 1;
for(i = 0; i < adwDown2.GetSize(); i++)
{
if(adwDown2[i] != 1)
{
dwBuff *= adwDown2[i];
TRACE("%d * ",adwDown2[i]);
}
}
TRACE("\n");
dwResult /= dwBuff;//求め終わり...but、桁あふれあり
TRACE("%dC%d = %d\n",n,r,dwResult);
adwUp.RemoveAll();
Mul(adwUp,adwUp2);//分子の無限桁計算(桁あふれなし)
adwDown.RemoveAll();
Mul(adwDown,adwDown2);//分母の無限桁計算(桁あふれなし)
//多桁でadwUp/adwDownの計算ができれば誤差なしで求められる
}
No.2
- 回答日時:
一つの方法は、tera242さんのdoubleを使うルーチンで、最後に丸め処理( c + 0.5 してから整数化する=四捨五入)方法です。
それだと丸め誤差は出てこないと予想されます。
ただ、計算の方法として、
a = n;
b = r;
c = 1.0;
for(i=0 ;i< r ;i++){
c= c/b*a;
a--;
b--;
}
return (long)(c + 0.5);
としたほうが賢明かもしれません。(小数部を有効に使うことにより、cの数が大きくなりすぎるのを防ぐ)
(ただ返す数字はlongでdoubleを考えると多分こんなことはしなくても大丈夫と思いますが)
他の方法は、ln(n!) を計算する、factln(n) (精度double)を用意して、
c = factln(n) - factln(n-r) - factln(r)
return (long)(c + 0.5);
とするやり方も考えられます。
参考になりそうな数学的な話は、
http://mathworld.wolfram.com/BinomialCoefficient …
http://mathworld.wolfram.com/Factorial.html
で、あとは上記の参考文献などを見ればもっと効率の良い方法はありそうです。
が、、、詳細は見たことが無いので分かりません_o_
どれも確かめたわけではありませんので、自信なしとしておきます。
ご参考になれば。
No.1
- 回答日時:
CDWordArrayはDWORD型の自由に配列サイズを変えられる配列です。
そこにどんどん乗算すべき値を代入しています。dwUpは分子、dwDownは分母としています。数値が大きくなりすぎないように約分してから最後に一回だけ除算を行っています。あとTRACEはテスト用に入れたものでメッセージを表示するのに使いました。意味はありません。適当に作ったので非常に効率は悪いですが、こういう人間的なアルゴリズムもあるという参考程度にどうでしょうか?&もしかしたらnCrの定義を間違えて計算しているかもしれません。
inti;
intj;
intn;
intr;
DWORDdwResult;
DWORDdwBuff;
CDWordArraydwUp;
CDWordArraydwDown;
n = 64;
r = 32;
for(i = n - r + 1; i <= n; i++)
{
dwUp.Add(i);// n(n-1)(n-2)...(n-r+1)
}
for(i = 1; i <= r; i++)
{
dwDown.Add(i);// r!
}
for(i = 0; i < dwDown.GetSize(); i++)
{
for(j = 0; j < dwUp.GetSize(); j++)
{
if((dwUp[j] % dwDown[i]) == 0)
{
dwUp[j] /= dwDown[i];
dwDown[i] = 1;
break;
}
}
}
dwResult = 1;
for(i = 0; i < dwUp.GetSize(); i++)
{
dwResult *= dwUp[i];
TRACE("%d * ",dwUp[i]);
}
TRACE("\n");
dwBuff = 1;
for(i = 0; i < dwDown.GetSize(); i++)
{
dwBuff *= dwDown[i];
TRACE("%d * ",dwDown[i]);
}
TRACE("\n");
dwResult /= dwBuff;
TRACE("%dC%d = %d\n",n,r,dwResult);
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# C言語 3 2022/11/09 13:27
- C言語・C++・C# プログラミングの授業の課題です 1 2023/01/17 22:15
- C言語・C++・C# C言語 3 2022/10/04 15:07
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「指定されたキャストは有効で...
-
複数桁10進数の*桁目だけを抽出...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語での引数の省略方法
-
【C++】関数ポインタの使い方
-
比較回数と交換回数表示について
-
C言語で三目並べをするプログラ...
-
if と配列の組み合わせ
-
商と剰余を同時に求める(C言語)
-
C言語での奇数の和
-
ラップ関数とはどんなものですか?
-
Arduinoのプログラムにエラーが...
-
C言語
-
並列プログラミングのπ計算につ...
-
C言語 エラーの原因がわからな...
-
インライン展開されているか確...
-
GlobalAllocの変数を関数に引き...
-
HANDLEて何ですか?
-
read関数をノンブロッキングで...
-
C++でvectorにテキストファイル...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報