15

我知道这是一个经典的编程问题，因此我想明确表示我不是在寻找代码作为解决方案，但希望能朝着正确的方向前进。我正在学习 C++，作为学习过程的一部分，我正在尝试一些编程问题。我正在尝试编写一个程序来处理高达 10 亿阶乘的数字。显然，这些将是巨大的数字并且太大而无法使用正常的算术运算来处理。任何关于我应该尝试解决此类问题的方向的任何指示都将不胜感激。

如果可能的话，我宁愿尝试在不使用其他库的情况下解决这个问题

谢谢

PS - 问题在这里http://www.codechef.com/problems/FCTRL

这是我用来解决问题的方法，这是通过阅读以下评论来实现的：

解决方案——数字 5 是任何以零结尾的数字的质因数。因此，将阶乘数除以 5，递归地加上商，您将得到阶乘结果中尾随零的数量

EG - 126 中尾随零的数量！= 31

126/5 = 25 余数 1

25/5 = 5 余数 0

5/5 = 1 余数 0

25 + 5 + 1 = 31

这适用于任何值，只需继续除法直到商小于 5

4

10 回答 10

7

略过这个问题，不确定我是否真的做对了，但这是一个演绎猜测：

第一个问题 - 你如何在数字的末尾得到一个零？乘以 10。

你怎么乘以10？通过乘以 10 或乘以 2 x 5...

所以，对于 X！你有多少个 10 和 2x5...？

（幸运的是 2 和 5 是素数）

编辑：这是另一个提示-我认为您不需要做任何乘法运算。如果您需要其他提示，请告诉我。

于 2010-01-20T01:14:52.063 回答
3

提示：您可能不需要计算 N！为了找到N末尾的零个数！

于 2010-01-20T00:51:40.200 回答
3

要解决这个问题，正如 Chris Johnson 所说，您必须查看 0 的数量。

10 的因数本身就是 1,2,5,10。因此，您可以遍历 N 的每个数字！并将它们写成 2^x * 5^y * 10^z。丢弃数字的其他因素。

现在答案将是greaterof(x,y)+z。

我从这个问题中学到的一件有趣的事情是，将一个数字的阶乘存储在素数方面总是更好，以便于比较。

实际上x^y，在RSA算法中有一个简单的方法，不记得了。如果我找到一个帖子，我会尝试更新。

于 2010-01-20T01:06:26.823 回答
1

这不是您问题的好答案，因为您已根据我最初阅读的内容对其进行了一些修改。但无论如何我都会把它留在这里，以证明实际尝试通过主要蛮力进行计算是不切实际的。

任何 bignum 库都将无法使用 10 亿阶乘。这样的数字将需要比几乎任何人在 RAM 中更多的空间来表示。在处理这些数字时，您将不得不开始从存储中分页。有办法做到这一点。最近计算 π 到 27000 亿个位置的人使用了这样一个库

于 2010-01-20T00:54:12.437 回答
1

不要使用幼稚的方法。如果需要计算阶乘，请使用快速算法：http ://www.luschny.de/math/factorial/FastFactorialFunctions.htm

于 2010-01-20T01:09:20.033 回答
1

我认为在你开始考虑 C++ 或任何其他语言之前，你应该想出一种用伪代码解决问题的方法。正如一些人所指出的，这个问题的性质更像是一个算法问题，而不是一个 C++ 问题。那些建议搜索一些不起眼的图书馆的人正在将你指向一个滑坡的方向，因为学习编程就是学习如何思考，对吧？找到一个好的算法分析文本，它会很好地为您服务。在我们部门，我们从CLRS文本中教学。

于 2010-01-20T02:58:06.447 回答
0

首先，您应该将数字存储在某种数组中，例如 std::vector （数组中每个位置的数字），并且您需要找到某种算法来计算阶乘（可能以某种形式专业课）。;)

于 2010-01-20T00:47:26.700 回答
0

你需要一个“大数字”包——要么是你使用的，要么是你自己写的。

我建议对“大量算法”进行一些研究。您需要实现 Java 的BigDecimal的 C++ 等价物。

另一种看待它的方法是使用gamma 函数。您无需将所有这些值相乘即可获得正确答案。

于 2010-01-20T00:50:23.210 回答
0

要计算大阶乘，您可以在 C++ 中使用此代码：

#include<iostream>
using namespace std;

long double factorial(int n);

int main()
{
    int n;

    cout << "Enter a positive integer: ";
    cin >> n;

    cout << "Factorial of " << n << " = " << factorial(n);

    return 0;
}

long double factorial(int n)
{
    if(n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

由于 long double 保存了大量数据1.7E +/- 308，所以这段代码确实可以很好地执行！

于 2017-09-24T15:22:39.263 回答
0 
    //SIMPLE FUNCTION TO COMPUTE THE FACTORIAL OF A NUMBER
    //THIS ONLY WORKS UPTO N = 65
    //CAN YOU SUGGEST HOW WE CAN IMPROVE IT TO COMPUTE FACTORIAL OF 400 PLEASE?     

    #include <iostream>
    #include <cmath>
    using namespace std;


    int factorial(int x);       //function to compute factorial described below

    int main()
        {
        int N; //= 150; //you can also get this as user input using cin.
        cout<<"Enter intenger\n";
        cin>>N;

        factorial(N);

        return 0;

        }//end of main




    int factorial(int x)        //function to compute the factorial
    {
     int i, n;
        long long unsigned results = 1;
        for (i = 1; i<=x; i++)
        {

        results = results * i;


        }

        cout<<"Factorial of "<<x<<" is "<<results<<endl;


        return results;
    }
于 2018-12-11T01:12:11.320 回答