c++ - 大階乗級数

Question

シリーズを印刷する必要があります:-

n*(n-1),n*(n-1)*(n-2),n*(n-1)*(n-2)*(n-3),n*(n-1)*(n-2)*(n-3)*(n-4)...,n!.

問題は n の値が大きいことです。最大 37 と n! 明らかに範囲外になりますか？始められません。助けてください。もしあなたが私の立場だったら、どのように状況に取り組みましたか?

Answer 1

使用している言語によって異なります。一部の言語は、数値がマシンのネイティブ整数表現に対して大きくなりすぎると、自動的に大きな整数パッケージに切り替わります。他の言語では、37 を処理する必要がある大きな整数ライブラリを使用してください! 簡単に。

ウィキペディアには、一部の言語用の任意精度の算術ライブラリのリストがあります。ウェブ上には他にもたくさんのリソースがあります。

Answer 2

3年問題は楽しそうでした。

factorで文字列を「乗算」するルーチンを簡単に作成します。非常に効率的ではありませんが、仕事を成し遂げます。

#include <stdlib.h>
#include <string.h>
void mult_array(char *x, unsigned factor) {
  unsigned accumulator = 0;
  size_t n = strlen(x);
  size_t i = n;
  while (i > 0) {
    i--;
    accumulator += (unsigned)(x[i]-'0')*factor;
    x[i] = (char) (accumulator%10 + '0');
    accumulator /= 10;
  }
  while (accumulator > 0) {
    memmove(x+1, x, ++n);
    x[i] = (char) (accumulator%10 + '0');
    accumulator /= 10;
  }
}

#include <stdio.h>
void AS_Factorial(unsigned n) {
  char buf[1000]; // Right-size buffer (problem for another day)
  sprintf(buf, "%u", n);
  fputs(buf, stdout);
  while (n>1) {
    n--;
    mult_array(buf, n);
    printf(",%s", buf);
  }
  puts("");
}

サンプルの使用法と出力

int main(void) {
  AS_Factorial(5);
  AS_Factorial(37);
  return 0;
}

5,20,60,120,120
37,1332,46620,1585080,52307640,1673844480,...,13763753091226345046315979581580902400000000

Answer 3

大きな整数を使用できますが、これにはまだいくつかの制限がありますが、それでも、このデータ型は非常に大きな値を処理できます。大整数が保持できる値は、符号付き大整数の
場合は -9223372036854775808 ～ 9223372036854775807
、符号なし大整数の場合は 0 ～ 18446744073709551615 です。

大きな整数データ型よりも大きな値の計算を本当に計画している場合は、GMP ライブラリを試してみませんか?

サイトの記述によると、「GMP は、符号付き整数、有理数、および浮動小数点数を操作する任意精度演算用の無料ライブラリです。マシンで使用可能なメモリによって暗示されるものを除いて、精度に実際的な制限はありません。 GMP は実行されます。GMP には豊富な機能セットがあり、機能には通常のインターフェイスがあります。」-gmplib.org

Answer 4

サードパーティ ライブラリの使用が許可されていない場合は、独自の big-integer 型を実装できます。あなたはそのようなことをすることができます:

    #include <iostream>
    #include <iomanip>
    #include <vector>
    using namespace std;

    const int base = 1000 * 1000 * 1000; // base value, should be the power of 10
    const int lbase = 9; // lg(base)

    void output_biginteger(vector<int>& a) {
      cout << a.back();
      for (int i = (int)a.size() - 2; i >= 0; --i)
        cout << setw(lbase) << setfill('0') << a[i];
      cout << endl;
    }

    void multiply_biginteger_by_integer(vector<int>& a, int b) {
      int carry = 0;
      for (int i = 0; i < (int)a.size(); ++i) {
        long long cur = (long long)a[i] * b + carry;
        carry = cur / base;
        a[i] = cur % base;
      }
      if (carry > 0) {
        a.push_back(carry);
      }
    }

    int main() {
      int n = 37; // input your n here
      vector<int> current(1, n);
      for (int i = n - 1; n >= 1; --n) {
        multiply_biginteger_by_integer(current, i);
        output_biginteger(current);
      }
      return 0;
    }

Answer 5

Java でBigIntegerを試したところ、うまくいきました。

デモンストレーション用の作業コード:

import java.math.BigInteger;

public class Factorial {
    public static int[] primes = {2,3,5,7,11,13,17,19,23,29,31,37};
    public static BigInteger computeFactorial(int n) {
        if (n==0) {
            return new BigInteger(String.valueOf(1));
        } else {
            return new BigInteger(String.valueOf(n)).multiply(computeFactorial(n-1));
        }
    }
    public static String getPowers(int n){
        BigInteger input = computeFactorial(n);
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i < primes.length && input.intValue() != 1;) {
            BigInteger[] result = input.divideAndRemainder(new BigInteger(String.valueOf(primes[i])));
            if (result[1].intValue() == 0) {
                input = input.divide(new BigInteger(String.valueOf(primes[i])));
                count++;
                if (input.intValue() == 1) {sb.append(primes[i] + "(" + count + ") ");}
            } else {
                if (count!=0)
                sb.append(primes[i] + "(" + count + ") ");
                count = 0;
                i++;
            }
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        System.out.println(getPowers(37));
    }
}

著作権を気にせず、ご自由にお使いください。

更新: 今まで C++ を使用していたことに気づきませんでした。その場合は、boost BigIntegerを試すことができます。