对不起,我觉得问这个问题很愚蠢,我准备失去我一半的分数,但为什么这个算法不工作?它工作到一个点。在数字13之后的阶乘有点偏离。例如,数字不完全匹配在几十万位和以后。
#include <stdio.h>
float factorial(unsigned int i) {
if (i <= 1) {
return 1;
}
return i * factorial(i - 1);
}
int main() {
int i = 13;
printf("Factorial of %d is %f\n", i, factorial(i));
return 0;
}
下面是输出:
Factorial of 13 is 6227020800.000000
以下是不准确输出的示例:
Factorial of 14 is 87178289152.000000
数字14的输出实际上应该是这样的(来自mathisfun.com)
14 87,178,291,200
我将返回类型更改为float以获得更精确的输出,但我主要是从这里获得以下代码的:https://www.tutorialspoint.com/cprogramming/c_recursion.htm
**编辑:**如果将返回类型更改为double,则输出的精度最高可达21。我在 printf 函数中使用 %Lf 字符串格式化程序作为输出。
5条答案
按热度按时间gijlo24d1#
Simple.
float
无法在不损失精度的情况下准确存储大于16777216的整数。int
比float更好。但是尝试long long
,这样你就可以正确地存储19位数。svmlkihl2#
float
可以表示比int
更宽的数字“范围”,但它不能表示该范围内的所有值--当你接近范围的边缘时(即,随着值的大小增加),可表示值之间差距会变大。例如,如果不能表示0.123到0.124之间的值,那么也不能表示123.0到124.0、1230.0到1240.0、12300.0到12400.0等之间的值(当然,IEEE-754单精度
float
比 that 提供的精度要高一些)。话虽如此,
float
应该能够精确地表示所有最大为224的整数值,所以我敢打赌问题出在printf
调用中-float
参数被“提升”为double
,因此涉及到表示法的更改,这可能是精度损失的原因。尝试将
factorial
的返回类型更改为double
,看看是否有帮助。〈无端的咆哮〉
每当我看到递归阶乘函数时,我都想大叫一声,在这个特定的例子中,递归在代码清晰度和性能方面都没有比迭代解法更好的地方:
并且实际上由于如此多的函数调用的开销而导致“更差”的性能。
是的,阶乘的 * 定义 * 是递归的,但是阶乘函数的 * 实现 * 不一定是递归的。斐波那契数列也是如此。甚至斐波那契数也有一个 * 封闭形式 * 的解
一开始就不需要任何循环。
递归对于将数据划分为相对较少的、大小相等的子集的算法(快速排序、树遍历等)来说是很好的。对于这样的算法,如果划分是1个元素的N-1个子集,那么递归就不那么好了。
〈/无端的咆哮〉
rhfm7lfc3#
OP遇到
float
的精度限制。对于typicalfloat
,大于16777216.0f
的整数值并非全部都可精确表示。* 高于此点的某些 * 阶乘结果可精确表示。让我们用不同的类型来试试这个。
在
11!
处,float
结果超过16777216.0f
,并且完全正确。在
14!
中,float
结果不精确,因为 * 精度 * 有限。在
23!
中,double
结果不精确,因为 * 精度 * 有限。在
22!
,答案超出了我的uintmax_t
* 范围 *。(64位)在
35!
,答案超出了我的float
* 范围 *。在
171!
,答案超出了我的double
* 范围 *。产出
uurity8g4#
正如其他答复中所解释的那样,这与可用的不同类型数字的范围和精度有关。
可以使用字符数组(字符串)来表示数字并获得精确值。例如:
hvvq6cgz5#
为什么这个阶乘算法不准确
algorithm
本身并没有什么问题。只是您使用的数据类型对它们可以存储的最大数量有限制。无论您选择哪种算法,这都会是一个问题。您可以将数据类型从float
更改为类似long double
的数据类型,以存储更大的数据。但最终,一旦阶乘值超过了该数据类型的容量,它仍然会开始失败。在我看来,你应该在阶乘函数中放置一个a条件,如果传入的参数大于你选择的数据类型所能支持的值,则不进行任何计算而返回。