18

計算するための非再帰的アルゴリズムをどのように記述しますn!か？

4

22 に答える 22

31

Int32 は 12 より大きいものでオーバーフローするためです! とにかく、次のようにします。

public int factorial(int n) {
  int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  return fact[n];
}
于 2008-10-23T20:20:21.493 に答える
19

擬似コードで

ans = 1
for i = n down to 2
  ans = ans * i
next
于 2008-10-23T20:04:47.420 に答える
6

科学の利益のために、階乗を計算するためのアルゴリズムのさまざまな実装についてプロファイリングを実行しました。C＃とC ++で、それぞれの反復、ルックアップテーブル、および再帰的な実装を作成しました。13なので、最大入力値を12以下に制限しました。2 ^ 32（32ビット整数で保持できる最大値）より大きい。次に、各関数を1,000万回実行し、可能な入力値を循環しました（つまり、入力パラメーターとして13を法としてiを使用して、iを0から1,000万にインクリメントします）。

反復C++の数値に正規化されたさまざまな実装の相対的な実行時間は次のとおりです。

            C++    C#
---------------------
Iterative   1.0   1.6
Lookup      .28   1.1
Recursive   2.4   2.6

また、完全を期すために、64ビット整数を使用し、最大20の入力値を許可する実装の相対的な実行時間は次のとおりです。

            C++    C#
---------------------
Iterative   1.0   2.9
Lookup      .16   .53
Recursive   1.9   3.9
于 2008-10-24T00:15:55.993 に答える
6 
public double factorial(int n) {
    double result = 1;
    for(double i = 2; i<=n; ++i) {
        result *= i;
    }
    return result;
}
于 2008-10-23T20:02:57.207 に答える
5

再帰的解をループとして書き直します。

于 2008-10-23T20:02:43.103 に答える
5

Python のように任意の長さの整数がない限り、factorial() の事前計算値を約 20 の長さの配列に格納し、引数 n をインデックスとして使用します。nの成長率！はかなり高く、計算すると 20! または21！いずれにしても、64 ビット マシンでもオーバーフローが発生します。

于 2008-10-23T20:11:01.807 に答える
3

実際に正しいことを除いて、これは事前計算された関数です。おっしゃる通り13です！オーバーフローするため、このような狭い範囲の値を計算しても意味がありません。64ビットの方が大きいですが、範囲はまだかなり妥当だと思います.

int factorial(int i) {
    static int factorials[] = {1, 1, 2, 6, 24, 120, 720, 
            5040, 40320, 362880, 3628800, 39916800, 479001600};
    if (i<0 || i>12) {
        fprintf(stderr, "Factorial input out of range\n");
        exit(EXIT_FAILURE); // You could also return an error code here
    }
    return factorials[i];
}

出典: http://ctips.pbwiki.com/Factorial

于 2008-10-23T21:17:00.397 に答える
2 
long fact(int n) {
    long x = 1;
    for(int i = 1; i <= n; i++) {
        x *= i;
    }
    return x;
}
于 2008-10-23T20:03:55.457 に答える
2 
int total = 1
loop while n > 1
    total = total * n
    n--
end while
于 2008-10-23T20:04:46.343 に答える
2

私はこれに対するPythonicソリューションが大好きです:

def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
于 2009-01-26T22:57:27.673 に答える
1 
fac = 1 ; 
for( i = 1 ; i <= n ; i++){
   fac = fac * i ;
}
于 2008-10-23T20:04:39.857 に答える
1 
public int factorialNonRecurse(int n) {
    int product = 1;

    for (int i = 2; i <= n; i++) {
        product *= i;
    }

    return product;
}
于 2008-10-23T20:05:34.330 に答える
1

実行時には、これは再帰的ではありません。コンパイル時には再帰的です。実行時のパフォーマンスは O(1) である必要があります。

//Note: many compilers have an upper limit on the number of recursive templates allowed.

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}
于 2009-01-26T14:48:07.583 に答える
0

非常に大きな数を処理できるようにしたいと仮定すると、次のようにコーディングします。この実装は、一般的なケース（数値が小さい）に対して適切な速度が必要であるが、非常に大量の計算を処理できるようにしたい場合に使用します。私はこれを理論上最も完全な答えだと思います。実際には、宿題以外の問題について、このような大きな階乗を計算する必要があるとは思えません。

#define int MAX_PRECALCFACTORIAL = 13;

public double factorial(int n) {
  ASSERT(n>0);
  int[MAX_PRECALCFACTORIAL] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
                362880, 3628800, 39916800, 479001600};
  if(n < MAX_PRECALCFACTORIAL)
    return (double)fact[n];

  //else we are at least n big
  double total = (float)fact[MAX_PRECALCFACTORIAL-1]
  for(int i = MAX_PRECALCFACTORIAL; i <= n; i++)
  {
    total *= (double)i;  //cost of incrimenting a double often equal or more than casting
  }
  return total;

}
于 2008-10-23T20:49:39.513 に答える
0

擬似コード

total = 1
For i = 1 To n
    total *= i
Next
于 2008-10-23T20:04:23.617 に答える
0 
long fact(int n)
{
    long fact=1;
    while(n>1)
      fact*=n--;
    return fact;
}

long fact(int n)
{
   for(long fact=1;n>1;n--)
      fact*=n;
   return fact;
}
于 2008-11-18T05:12:25.010 に答える
0

私はメモ化を使用します。そうすれば、メソッドを再帰呼び出しとして記述しても、線形実装のほとんどの利点を得ることができます。

于 2008-10-25T19:48:08.680 に答える
0

反復:

int answer = 1;
for (int i = 1; i <= n; i++){
    answer *= i;
}

または... Haskellで末尾再帰を使用する:

factorial x =
    tailFact x 1
    where tailFact 0 a = a
        tailFact n a = tailFact (n - 1) (n * a)

この場合、末尾再帰が行うことは、アキュムレータを使用して、スタック呼び出しの積み重ねを回避することです。

参考：Haskellの末尾再帰

于 2012-08-09T16:18:34.493 に答える
-1 
int fact(int n){
    int r = 1;
    for(int i = 1; i <= n; i++) r *= i;
    return r;
}
于 2008-10-23T20:03:57.783 に答える
-2

キャッシング付きの JavaScript を再帰的に使用します。

var fc = []
function factorial( n ) {
   return fc[ n ] || ( ( n - 1 && n != 0 ) && 
          ( fc[ n ] = n * factorial( n - 1 ) ) ) || 1;
}
于 2012-10-23T16:16:15.767 に答える