计算一个任意大数的阶乘，显示所有的数字
最近我在一次采访中被要求描述一种计算任意大数的阶乘的方法; 我们获得答案的所有数字的方法。
我search了不同的地方，并在几个论坛上询问。 但是我想知道是否有什么办法可以在不使用GMP等库的情况下完成这个任务。
谢谢。
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是一个简单的函数，它将给定的数字乘以“大数”。
希望这可以解决您的查询..
接受的答案是好的，但这是C ++; 我们可以做得更好。 让我们开始我们自己的Bignum类，完全没有数字的数字。
为了获得最高的效率，我们将使用纯二进制数字，使用尽可能多的位数打包每个数组元素，这是我们可以高效处理的。 更简单的方法是在每个元素中存储一个十进制数字。 在这里，我已经做出妥协，在每个uint32_t元素中存储9个十进制数字。
数据存储为小端，因为当我们需要更高阶的元素时，最后扩展vector要容易得多。
一旦我们有这个类，阶乘函数本身就是简单的。
#include <assert.h> #include <iomanip> #include <iostream> #include <stdint.h> #include <vector> class Bignum { public: Bignum(int value) { assert(value >= 0 && value <= 999999999); parts.push_back(value); } Bignum& operator*=(int rhs) { assert(rhs >= 0 && rhs <= 999999999); uint32_t carry = 0; for (size_t i = 0; i < parts.size(); i++) { uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry; parts[i] = (uint32_t)(product % 1000000000LL); carry = (uint32_t)(product / 1000000000LL); } if (carry != 0) parts.push_back(carry); return *this; } friend std::ostream & operator<<(std::ostream& stream, const Bignum& num); private: std::vector<uint32_t> parts; }; inline std::ostream& operator<<(std::ostream& stream, const Bignum& num) { char oldfill = stream.fill('0'); for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++) stream << *it << std::setw(9); stream.fill(oldfill); stream.width(0); return stream; } Bignum factorial(int n) { Bignum fac = 1; for (int i = 2; i <= n; i++) fac *= i; return fac; } int main(int argc, char* argv[]) { for (int n = 0; n <= 52; n++) std::cout << factorial(n) << std::endl; return 0; }
Srivatsan Iyer的好的解决scheme和我的build议是：
-
通过使用unsigned char数组，而不是使用int数组来存储数字，仍然可以提高内存的效率。 对于int数组，只需要25％的内存需求。
-
为了获得最佳的内存优化，我们也可以使用单个字节来表示一个2位数字。 由于只有4位足以表示从0到9的任何数字，因此我们可以使用按位操作在一个字节中打包两位数字。 这将需要内存数组的12.5％的内存。
一个BigInteger类可以解决你的问题，上面的C实现给你一个关于如何实现BigInt的想法，除了代码是针对速度进行了优化的，并且只是为了计算阶乘而定制的。
那么，你必须用数组写你自己的math例程。 这很容易加法，乘法有点困难，但仍然有可能。
编辑：想要张贴一个例子，但Srivatsan艾尔的例子就好了。
我有一个计算阶乘的解决scheme，它至less工作n <= 15000。 10000的因子可以在1秒内计算出来，计算阶乘的时间less于2秒。 （当然你的问题没有提到时间限制，这些时间完全取决于机器）。 无论如何，这个概念很简单。 我使用了一个char数组。 数组的第一个字符是“1”。 LSB从0开始存储。一个variables（根据我的程序，m）跟踪阶乘长度。 m的最终值是factorial中的位数，char数组的第（m-1）个元素是阶乘的MSB。 循环迭代时，字符被添加到数组的右侧。 variables“c”logging进位。
使用数组的缺点留在了未使用字节的块上。 而且超出某个特定点，则不能为数组预留空间。而且，数组往往会变慢。
你可以查看我的ideone的程序： http ://ideone.com/K410n7
我相信我的解决scheme仍然可以优化。 请build议如何。
include<stdio.h> char res[200000]; inline int fact(int n) { int i,j; register int m,c; m=1; res[0]='1'; for(i=2;i<=n;i++) { c=0; for(j=0; j< m; j++){ c =((res[j]-48)*i)+c; res[j]=(c%10)+48; c=c/10; } while(c>0){ res[m]=(c%10)+48; c=c/10; m++; } } return m; } int main() { int n,i,d; scanf("%d",&n); d=fact(n); for(i=d-1;i>=0;i--) printf("%c",res[i]); return 0; }
这其实很简单 这里有两种方法。 一个是确切的，一个是近似值。 对于确切的数字，超过10,000的任何数字将需要几秒钟来计算。 接近它将需要几微秒，直到你进入数百万。 如果有人感兴趣，那就是斯特林的近似值。
10,000,000的因子是aprox 1.2024234127436e + 65657059这花了5.9秒find确切的金额将需要34天。
<?php $test= 3579; echo 'Factorial of '.$test.'<br><br>'; $tm= microtime( true); echo 'Exact '.( $f= factorialexact( $test)).' e+'.(strlen( $f)-1).' missing decimal place after first digit<br>'; echo ( microtime( true) - $tm). ' seconds<br><br>'; $tm= microtime( true); echo 'Aprox '.factorialapprox( $test).'<br>'; echo ( microtime( true) - $tm). ' seconds<br><br>'; function factorialexact( $n){ $f= '1'; for ( $i=$n; $i>1; $i--){ $f= JL_bcmul( $f, (''.$i)); } return $f; } function factorialapprox( $n){ // Stirling's factorial approximation // aprox factorial n = sqrt( 2 * pi * n) * n^n / e^n // store in t the easy part, calc the first term easily $t= sqrt( 2 * 3.14159265358979 * $n); // things get tough from here because for large n // n^n can blow away floating point pachages // declare exponent of the number $e= 0; // the remaining terms are n^n / e^n // both n and e (natural log) are raised to the same power // that is n, just negative of each other for ( $i=0; $i<$n; $i++){ // loop to // mulitply by n and divide by e for each iteration $t= $t * $n / 2.71828182845904; // exponents are going to get away from us // so reduce or increase t while ( $t>1000){ $t= $t/1000; $e= $e+3; } while ( $t<0.001){ $t= $t*1000; $e= $e-3; } } // garentee the base number is between 1 and 10 while ( $t>=10){ $t= $t/10; $e= $e+1; } while ( $t<1){ $t= $t*10; $e= $e-1; } // return at a floating string. // do not use parseFloat() or floatval() // $v= explode( 'e', $result); $floatvalue= $v[0] * pow( 10, $v[1]); // won't work either. $v[1] is way too large // the exponent can easily be in the tens of thousands $p= '-'; if ( $e>=0){ $p= '+'; } return $t.'e'.$p.$e; } function JL_bcmul( $a, $b){ if ( function_exists( 'bcmul')){ return bcmul( ( ''.$a), (''.$b)); } $s= array(); for ($i=0; $i < count( $a) + count( $b); $i++){ $s[$i]= '0'; } $t= 0; for ($i=0; $i < strlen( $b); $i++){ for ($j=0; $j < strlen( $a); $j++){ $t= $s[$i+$j] + intval( $a[strlen( $a) - $j - 1]) * intval( $b[ strlen( $b) - $i - 1]); $s[$i+$j]= $t % 10; $s[$i+$j+1]= $s[$i+$j+1] + floor( $t / 10); } } $s= array_reverse( $s); return trim( trim(( implode( '', $s).'_'), '0'), '_'); }
#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; }
既然大家投票赞成Srivatsan，我只是怀疑这个问题。 你需要储存所有的数字吗？ 如果是，那么Srivatsan的解决scheme是好的。 如果没有，为什么不显示数字，因为你计算阶乘？ 我没有正确格式化输出，但这可以达到目的。
int factorial(int num) { if (num <= 0) return 1; else { std::cout << num << std::endl; return num * factorial(num - 1); } }
更新对于所有的downvoters，虽然这个5岁的职位，和factorial(3);的产出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.
我以为这是问什么。
