22

私は最近、あるインタビューで、任意の大きな数の階乗を計算する方法について説明するよう求められました。答えのすべての桁を取得する方法。

私はさまざまな場所を検索し、いくつかのフォーラムで質問しました。しかし、GMP などのライブラリを使用せずにこれを達成する方法があるかどうかを知りたいです。

ありがとうございました。

4

11 に答える 11

31

GNU Multiprecision ライブラリは優れたライブラリです。しかし、外部ライブラリの使用は許可されていないとおっしゃっているので、可能だと思う唯一の方法は、int の配列を取り、紙にペンで行うように数値を乗算することです!

ここに私がしばらく前に書いたコードがあります..

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}


void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :\n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

'arr' は単なる整数配列であり、factorial は指定された数を '大きな数' に乗算する単純な関数です。

これでクエリが解決することを願っています..

于 2009-12-27T14:39:14.780 に答える
5

Srivatsan Iyer による素敵な解決策と私の提案は次のとおりです。

  1. int 配列を使用して数字を格納するのではなく、unsigned char 配列を使用することで、メモリ効率をさらに高めることができます。int配列に必要なメモリの25％しかかかりません。

  2. 最適なメモリ最適化のために、1 バイトを使用して 2 桁を表すこともできます。0 から 9 までの任意の数字を表すには 4 ビットだけで十分なので、ビット演算を使用して 2 つの数字を 1 バイトに詰め込むことができます。int 配列に必要なメモリの 12.5% を使用します。

于 2009-12-27T18:13:11.747 に答える
3

そうですね、配列を使用して独自の数学ルーチンを作成する必要があります。加算は非常に簡単です。乗算は少し難しくなりますが、それでも可能です。

編集：例を投稿したかったのですが、Srivatsan Iyerの例は問題ありません。

于 2009-12-27T14:39:04.250 に答える
3

BigInteger クラスは問題を解決します。上記の C 実装は、コードが速度のために最適化され、階乗のみを計算するように調整されていることを除いて、BigInt がどのように実装されるかについてのアイデアを提供します。

于 2009-12-27T14:45:56.827 に答える
2 
#include <iostream>
using namespace std;
int main ()
{
    int i,n,p=1;
    cout<<"Enter a number: ";
    cin>>n;
    cout<<endl;

    for (i=1;i<=n; i++)
    {
        cout<<i<<" X "; 
        p=p*i;
    }
    cout<<endl<<endl<<p<<" factorial of "<<n;

    return 0;
}
于 2016-02-08T17:29:09.383 に答える
-3

誰もが Srivatsan に投票したので、私はこの問題に関連して疑問を持っています。すべての数字を保存する必要がありますか? はいの場合、Srivatsan のソリューションは問題ありません。そうでない場合は、階乗を計算するときに数値を表示しないのはなぜですか? 出力を適切にフォーマットしていませんが、これで目的は果たせます。

int factorial(int num)
{
   if (num <= 0)
      return 1;
   else
   {
      std::cout << num << std::endl;
      return num * factorial(num - 1);
   }
}

更新 この 5 年前の投稿と、 factorial(3);

3
2
1
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation.

私はこれが尋ねたことだと思いました。

于 2009-12-28T07:54:45.033 に答える