c言語

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
koro12

c言語

#1

投稿記事 by koro12 » 2年前

c言語のmまたはnが13以上となる場合に正しい解を求めることができない、なぜなら、13の階乗は6,227,020,800であり、この値はint型変数で扱うことのできる範囲をこえてしまっているからである。以下のプログラムを改良しなるべく大きなmやnの値でも正しく解を求めることができるプログラムをおしえてください。しかし、変数はあくまでint型を用い、floatやdouble型は使用しない方法でお願いします
int add( int a, int b )
{
int i;
int d = ( b>0 ? 1 : -1 );
int n = ( b>0 ? b : -b );
for( i=0; i<n; ++i )
{ a += d; }

return a;
}

int mul( int a, int b )
{
int i;
int r = 0;
int n = ( b>0 ? b : -b );
for( i=0; i<n; ++i )
{ r = add( r, a ); }

return ( b>0 ? r : -r );
}

int fn( int kitten )
{
return ( kitten>1 ? mul( kitten, fn(kitten-1) ) : 1 );
}

かずま

Re: c言語

#2

投稿記事 by かずま » 2年前

c言語 by koro12
初心者なんですが by mook
初心者なんですが by mook
adj by c言語
c言語 by ajd
c言語 by au
関数fc by mook
calc関数 by acaa
c言語 by mgwtp
c言語 by dgmip

フォーラムルールに
「なるべくオリジナルな名前を決め、以後同じ名前を使い続けてください。」
とあります。

フォーラムルールを熟読してみてください。
ソースプログラムは codeタグを付けて貼り付けてください。
エラーメッセージをそのまま載せて下さい。

フォーラムルール違反がひどすぎると、誰もまともに相手しなくなりますよ。

グレイス ビューチャーズ

Re: c言語

#3

投稿記事 by グレイス ビューチャーズ » 2年前

mまたはnからどの様な結果を得たいのかを示した方が良いと思います。

アバター
Dixq (管理人)
管理人
記事: 1659
登録日時: 8年前
住所: 北海道札幌市
連絡を取る:

Re: c言語

#4

投稿記事 by Dixq (管理人) » 2年前

規約違反トピックが乱立すると削除せざるをえません。
フォーラムルールを守った投稿をお願いします。

かずま

Re: c言語

#5

投稿記事 by かずま » 2年前

問題が意味不明なので、次のように改変します。

コード:

異なる m個の中から異なる n個を選ぶ場合の数(組み合わせ) mCn は、
以下の式で計算することができる(ただし、m≧n)

              m!
    mCn = ----------
           n!(m-n)!

しかし、C言語では、m または n が 13以上となる場合に正しい解を求める
ことができない。なぜなら、13の階乗は 6,227,020,800であり、この値は
int型変数で扱うことのできる範囲を超えてしまっているからである。

なるべく大きな m や nの値でも正しく解を求めることができるプログラム
を作成せよ。ただし、変数はあくまで int型を用い、float や double型
は使用しないこと。
m = 33 まで OK のプログラムです。

コード:

#include <stdio.h>

#define N 33

int comb(int n, int r)
{
    static int c[N+1][N+1];
    if (c[n][r]) return c[n][r];
    return c[n][r] = (r == 0 || r == n) ? 1 : comb(n-1, r-1) + comb(n-1, r);
}

int main(void)
{
    for (int m = 0; m <= N; m++, putchar('\n'))
        for (int n = 0; n <= m; n++)
            printf("%2dC%-2d = %d\n", m, n, comb(m, n));
    return 0;
}
実行結果

コード:

 0C0  = 1

 1C0  = 1
 1C1  = 1

 2C0  = 1
 2C1  = 2
 2C2  = 1

 3C0  = 1
 3C1  = 3
 3C2  = 3
 3C3  = 1

 4C0  = 1
 4C1  = 4
 4C2  = 6
 4C3  = 4
 4C4  = 1

 5C0  = 1
 5C1  = 5
 5C2  = 10
 5C3  = 10
 5C4  = 5
 5C5  = 1

 ...

32C0  = 1
32C1  = 32
32C2  = 496
32C3  = 4960
32C4  = 35960
32C5  = 201376
32C6  = 906192
32C7  = 3365856
32C8  = 10518300
32C9  = 28048800
32C10 = 64512240
32C11 = 129024480
32C12 = 225792840
32C13 = 347373600
32C14 = 471435600
32C15 = 565722720
32C16 = 601080390
32C17 = 565722720
32C18 = 471435600
32C19 = 347373600
32C20 = 225792840
32C21 = 129024480
32C22 = 64512240
32C23 = 28048800
32C24 = 10518300
32C25 = 3365856
32C26 = 906192
32C27 = 201376
32C28 = 35960
32C29 = 4960
32C30 = 496
32C31 = 32
32C32 = 1

33C0  = 1
33C1  = 33
33C2  = 528
33C3  = 5456
33C4  = 40920
33C5  = 237336
33C6  = 1107568
33C7  = 4272048
33C8  = 13884156
33C9  = 38567100
33C10 = 92561040
33C11 = 193536720
33C12 = 354817320
33C13 = 573166440
33C14 = 818809200
33C15 = 1037158320
33C16 = 1166803110
33C17 = 1166803110
33C18 = 1037158320
33C19 = 818809200
33C20 = 573166440
33C21 = 354817320
33C22 = 193536720
33C23 = 92561040
33C24 = 38567100
33C25 = 13884156
33C26 = 4272048
33C27 = 1107568
33C28 = 237336
33C29 = 40920
33C30 = 5456
33C31 = 528
33C32 = 33
33C33 = 1

34C16 = 2203961430, 34C17 = 2333606220, 34C18 = 2203961430 で
あり、これらは int が 4バイトの場合の最大値 2147483647 を超える
ので、int を使う限り、求めることができません。
unsigned int を使ってもいいのなら m = 34 でも大丈夫です。
もっと大きくしたければ unsigned long long を使うといいのでしょ
うが、問題に int型を使うことが指定されているのでダメです。
あとは、int の配列を使って多倍長計算をすればもっと大きな値でも
できるでしょう。

問題を改変しているので、これは質問への回答ではありません。

かずま

Re: c言語

#6

投稿記事 by かずま » 2年前

最初に考えたのは、m = 29 まで OK のプログラムでした。

コード:

#include <stdio.h>

#define N 29

int comb(int n, int r)
{
    int c = 1, i;
    if ((n -= r) < r) i = n, n = r, r = i;
    for (i = 0; i < r; c = ++n * c / ++i) ;
    return c;
}

int main(void)
{
    for (int n = 0; n <= N; n++, putchar('\n'))
        for (int r = 0; r <= n; r++)
            printf(" %2dC%-2d = %d\n", n, r, comb(n, r));
}

返信

“C言語何でも質問掲示板” へ戻る