階乗の多桁計算をしたいのですが、プログラムの仕方を教えてください。
具体的には、217!とかを計算したいです。普通にやると桁が溢れてしまいます。
できれば、CかPerlでお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

そういうライブラリがあればいいんですが、


私も知りません。

要は筆算の手順をプログラムに実装すればいいんじゃ
ないでしょうか。

たとえば、多桁×多桁の計算を筆算風にやってみます。

手元の環境では、unsigned shortが0~65535、unsigned
intがその2乗の桁を持ってるんで、unsigned shortの
配列s[KETA]、t[KETA]、r[KETA]を使って、(KETA:定数)
s[0]、t[0]、r[0]には千の位まで、s[1]等には千万の位まで
入ってる、という風に多桁の十進数を表現すると、

[初期値] unsigned int carry = 0, i = 0, j = 0;

[ステップ1]
unsigned int result
= (unsigned int)s[i] * (unsigned int)t[j] + carry;

[ステップ2]
r[i+j] += (unsigned short)(result % 10000);
carry = r[i+j] / 10000;

[ステップ3]
if( s[++i] > 0 )
  ステップ1へ
else if( t[++j] > 0 )
  if( carry > 0 )
    r[i+j-1] += carry;
  carry = i = 0;
  ステップ1へ
else
  ステップ4へ

[ステップ4]
rの要素を添え字の大きいものから順に横に並べて表示

多分どこか間違えてますが、こんな感じで多桁×多桁の
掛け算はできませんかね。217!に必要なのは多桁×少桁(?)
ですが、そっちはもう少しシンプルですね。

ところで、217!の厳密解が欲しいという状況が理解できないんですが…。
そんなものを眺めて何か分かるんでしょうか?整数論の最先端では
そういうことをやってるんでしょうか?暗号理論?

さもなくば浮動小数点で十分なんでは?
    • good
    • 0

UNIX の C なら、GNU の MP (または GMP)というライブラリがあります。


ソースは参考URLにあります。
Windows にも移植されているかもしれませんし、もしかするとコンパイル
すればそのまま動くかもしれません。

あと、Perl ではなく、Ruby なら、最初から多倍長精度演算が可能です。

参考URL:http://www.vector.co.jp/soft/solaris/sources/se0 …
    • good
    • 0

アルゴリズムは考えていますか?



ただ標準の数値を使うのではなく、パック形式でやるとか、自分で10進構造を作ってやれば桁あふれはおこりませんよ。
ライブラリでそういう関数があるかもしれません。
無ければ自分でそういう関数を作ればいいのです。
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q4桁の英字の3桁目を当てるプログラム

乱数でとってくる4ケタの英字の3桁目を入力して当てるプログラムを
組もうとしているのですが、コンパイラしてもいまいちうまくいきません。

特に下に書いたプログラムのこの部分が違っていると思い
どのように修正したらよいのか指摘していただきたいです。
human=getchar();

if(comp[2]!=human)
{
ero=1;
}
よろしくお願いします。

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

int sleep(unsigned long x)
{
clock_t c1=clock(),c2;

do{
if((c2=clock())==(clock_t)-1)
{
return 0;
}
}while(1000.0*(c2-c1)/CLOCKS_PER_SEC<x);
return 1;
}

int main(void)
{

int num,val,i,j;
char comp[21];
char human;
int ero=0;
int try_count=0;
int seikai=0;
clock_t start,end;
int num1;
char eiji[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

srand(time(NULL));
puts("英字記憶トレーニング");

do{
printf("挑戦するレベル(3~20):");
scanf("%d",&num1);
}while(num1<3 || num1>20);

printf("%d個の英字を記録しましょう。\n",num1);

start=clock();

do{

for(i=0;i<num1;i++)
{
comp[i]=eiji[rand()%strlen(eiji)];
}
comp[num1]='\0';

printf("%s",comp);
fflush(stdout);
sleep(125*num1);
printf("\r%*s\r3番目の英字を入力してください:",num1,"");
human=getchar();

if(comp[2]!=human)
{
ero=1;
}

if(ero==0)
{
printf("正解です。\n");
seikai++;
}
else
{
printf("\a間違いです。\n");
}
try_count++;

}while(try_count<2);

end=clock();

printf("%d回中%d回成功しました。\n",try_count,seikai);
printf("%.1f秒でした。\n",(double)(end-start)/CLOCKS_PER_SEC);

return 0;
}

乱数でとってくる4ケタの英字の3桁目を入力して当てるプログラムを
組もうとしているのですが、コンパイラしてもいまいちうまくいきません。

特に下に書いたプログラムのこの部分が違っていると思い
どのように修正したらよいのか指摘していただきたいです。
human=getchar();

if(comp[2]!=human)
{
ero=1;
}
よろしくお願いします。

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

int sleep(unsigned long x)
{
clock_t c1=clock(),c2;

do{
if((c2=clo...続きを読む

Aベストアンサー

>上記プログラムにhuman=getcharの上に下の文を入れるだけで
>動作するようになりました。
では、根本的な解決にはなってませんよ。

>「改行が入力になる」という意味がよくわからないので説明をしていただけると嬉しいです。
と関連しますが、
「リターンキー」もキーボードの入力の一つです。
そして、関数には
・リターンキーが押されるまでを取得する(リターンキーは入力バッファに残ったまま)
・「キー入力」ならなんでも取得する
という二種類が存在します。
scanf()は前者でありリターンキーはバッファに残ったままです。
次の入力関数を実行した際にその残ったリターンキーを読み込んでしまう為に起こる問題です。
No.2氏の回答は、キーバッファに残ったままのキー入力を読み飛ばす為の処理です。
(読み飛ばしはscanf( "%*[^\n]" ); の方がいいと思いますが)

ちなみに、ソース上の
>fflush(stdout);
は何を行っている化知ってますか?

Q階乗のプログラム

c言語初心者です。
13までの階乗の値を計算するプログラムを下のように書いたのですが、

#include <stdio.h>

main()
{
int N, fact;

fact=1;
for(N=1; N<=13; ++N){
fact=fact*N;
printf("%d!=%d\n",N, fact);
}
}

このプログラムを実行してみると、12!までは正しい値が出力されるのですが、13!の値が1932053504と出力され、計算機の値と違います。

どこが間違っているのでしょうか。どなたかご教授お願いします。

Aベストアンサー

fact を int 宣言しているので、 4byte 変数です。

12! = 479001600 = 0x1C8CFC00
13! = 6227020800 = 0x017328CC00

 このように、13! 以上は、4byte を超えてしまいます。

 従って、4byte を超えた分が無視されて、


13! = 6227020800 = 0x017328CC00
(4byte分のみ)==> 0x7328CC00 = 1932053504

 という結果です。

Q100の階乗のプログラムって

100の階乗を配列を利用してプログラムを組みたいのですが、どうやってすればいいのか分かりません。やりたい方法としては、数値を入力して、1から順番に入力して数値までかけて行きたいです。その中で、繰り上がり(agari)を利用して、人間が筆算をしているのと同じやり方をして計算したいです。掛けられる数は2桁でも一気にかけます。よろしくお願いします。

#include<stdio.h>
#define N 200
void main(void)
{
int a,agari,h,i,j;
int su[N];
printf("数値を入力してください");
scanf("%d",&a);
for(i=0;i<N;i++){
su[i] = 0;
}
su[N-1] = 1;
agari = 0;

  ここから先が分かりません。

Aベストアンサー

すみません。さっきのは間違えてました。

for(k=2;k<=a;k++){ //kをsu[]にかける
 su[0] *= k;
 for(i=1;i<N;i++){
  su[i]*=k;
  agari=su[i]/10;
  su[i]%=10;
  for(j=i-1;j>0;j--){
   agari+=su[j]
   su[j]=agari%10;
   agari/=10;
   if(agari==0)break;
  }
  su[0]=agari;
 }
}

Q階乗のプログラム!!

階乗を求めるプログラムを作りたいのですが、どうも上手くいきません・・・。下のプログラムを作ってみたのですが、エラーになってしまいます。どなたか教えてください、お願いします!!

#include <stdio.h>

void main(void)
{
int i,j;
long a=1;

for (i=1; i<=10; i++){
for(j=1 ;j <=i; j++){
a=a*j;
}

printf("%3d %ld \n",i,a);
}
}

Aベストアンサー

これって 1~10までの階乗を出力するってプログラムですよね?
実際に階乗の計算を行ってるのは2つ目のforループで行っていると
思いますが、その前にaを初期化してない為に前に計算した階乗の値が
残ってしまってるからじゃないかと思います。

for (i=1; i<=10; i++){
 a = 1; //←初期化
 for(j=1 ;j <=i; j++){
  a=a*j;
 }
 printf("%3d %ld \n",i,a);
}

もしくは...
int num = 10; //求める階乗数
int a,i;
for(i=1,a=1;i<=num;i++,a=a*i) printf("%3d %ld \n",i,a);

こんな感じになると思います。

Q複数桁10進数の*桁目だけを抽出したい

タイトルがすべてと言えてしまうのですが、
例えば、int宣言された"4287"(この値は変動します)という数値があったとして、1桁目の"7"だけを別の変数へ引き抜きたいのですが、その場合にはANDによるマスク処理による演算で処理可能なのでしょうか?
また、他に良い方法などありましたら教えていただけますでしょうか?

Aベストアンサー

★10進数ですので AND は使えませんね。
・簡単なサンプルを載せますので読み取って下さい。

サンプル1:
int value = 4287;
int a[ 4 ];

a[0] = (value % 10); value /= 10; // 1桁目を取り出す
a[1] = (value % 10); value /= 10; // 2桁目を取り出す
a[2] = (value % 10); value /= 10; // 3桁目を取り出す
a[3] = (value % 10); value /= 10; // 4桁目を取り出す

サンプル2:
int value = 4287;
int a;

a = (value % 10);
value -= a;

value → 4280
a → 7
になります。


このカテゴリの人気Q&Aランキング

おすすめ情報