大階乘系列

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

對於某些語言，維基百科有一個list of arbitrary-precision arithmetic libraries。網上還有很多其他資源。

Answer 2

我剛剛在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。

Answer 3

您可以使用大整數，但是這仍然有一些限制，但即使此數據類型可以處理非常大的值。大整數可容納的值，範圍從
-9223372036854775808到9223372036854775807爲有符號大整數，而
0到18446744073709551615爲無符號大整數。

如果你真的打算做一些比大整數數據類型更大的值計算，爲什麼不試試GMP library？

正如網站所說的那樣，「GMP是一個免費的庫，用於任意精度算術，對有符號整數，有理數和浮點數進行操作。除了可用的精度外，精度沒有實際的限制GMP運行的機器中的內存GMP具有豐富的功能，並且功能具有常規的界面。「 - gmplib.org

Answer 4

如果不允許使用任何第三方庫，則可以實現自己的大整數類型。你可以這樣做：

#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

3歲的問題看起來很有趣。

簡單地創建一個例程來「乘」一個字符串因子。效率不高，但完成工作。

#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