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！容易地。

Wikipedia列出了一些语言的任意精度算术库。网络上还有很多其他资源。

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

如果不允许使用任何第三方库，您可以实现自己的大整数类型。你可以这样做：

    #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 4

您可以使用大整数，但这仍然有一些限制，但即使这种数据类型可以处理非常大的值。大整数可以容纳的值，范围从
-9223372036854775808 到 9223372036854775807 为有符号大整数，
0 到 18446744073709551615 为无符号大整数。

如果你真的打算做一些比大整数数据类型更大的值计算，为什么不试试GMP 库呢？

正如该网站所说，“GMP 是一个用于任意精度算术的免费库，对有符号整数、有理数和浮点数进行操作。除了机器中可用内存所暗示的精度外，对精度没有实际限制GMP运行。GMP有丰富的功能集，功能有一个规则的接口。- gmplib.org

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 。