用C++计算大数的阶乘
用C++计算大数的阶乘
提问于 2009-09-05 20:14:37
在我的C代码中，我想要计算1到100范围内的数字的阶乘。对于较小的数字，该函数有效，但对于较大的数字(例如100!)它返回错误的结果。有没有办法在C中处理大数的阶乘？
我使用的编译器是gcc v4.3.3。我的代码如下：
#include <stdio.h>
#include <math.h>
double print_solution(int);
int main(void)
{
int no_of_inputs, n;
int ctr = 1;
scanf("%d",&no_of_inputs); //Read no of inputs
do
{
scanf("%d",&n); //Read the input
printf("%.0f\n", print_solution(n));
ctr++;
} while(ctr <= no_of_inputs);
return 0;
}
double print_solution(int n)
{
if(n == 0 || n == 1)
return 1;
else
return n*print_solution(n-1);
}回答 14
Stack Overflow用户
发布于 2009-09-05 20:20:34
00000000000000000000阶乘是很大的，准确地说是93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 100。
也许你应该使用像GMP这样的bignum库。它有很好的文档，非常一致的界面，速度，如果你在Linux上，你的发行版可能有一个包(我想我的默认会安装它)
Stack Overflow用户
发布于 2009-09-05 20:28:32
如果您不想使用bigint库，那么使用stdlib的最佳方法是使用math.h中的long double和tgammal()
long double fact(unsigned n)
{
return tgammal(n + 1);
}这将在x86 (即80位long double)上获得18位小数精度的100!。
确切的实现也不是那么复杂：
#include <math.h>
#include <stdio.h>
#include <string.h>
void multd(char * s, size_t len, unsigned n)
{
unsigned values[len];
memset(values, 0, sizeof(unsigned) * len);
for(size_t i = len; i--; )
{
unsigned x = values[i] + (s[i] - '0') * n;
s[i] = '0' + x % 10;
if(i) values[i - 1] += x / 10;
}
}
void factd(char * s, size_t len, unsigned n)
{
memset(s, '0', len - 1);
s[len - 1] = '1';
for(; n > 1; --n) multd(s, len, n);
}
int main(void)
{
unsigned n = 100;
size_t len = ceill(log10l(tgammal(n + 1)));
char dstr[len + 1];
dstr[len] = 0;
factd(dstr, len, n);
puts(dstr);
}Stack Overflow用户
发布于 2009-09-05 21:53:42
每个人都在告诉你正确的答案，但是还有几点。
- 您最初使用double来获取更大范围的想法并不起作用，因为double不能精确地存储此数据。它可以进行计算，但需要进行大量的舍入。这就是bigint库存在的原因。
，
- ，我知道这可能是教程或示例网站上的一个例子，但是做无界递归在某一时刻会咬你一口。对于本质上是迭代过程的问题，您有一个递归解决方案。当您尝试运行具有较大值的程序时(请尝试10000)，您将理解为什么此站点的名称是这样的。
一个简单的迭代方法如下所示
int answer, idx;
for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
answer = answer * idx;
}
printf("Factorial of %3d = %d\n", no_of_inputs, answer);页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1384160
复制相关文章
相似问题
腾讯云开发者
