在 C++ 中计算大阶乘；

发布于 2024-08-18 14:56:20 字数 640 浏览 4 评论 0原文

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

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

谢谢

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

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

解决方案 -- 数字 5 是任何以零结尾的数字的质因数。因此，递归地将阶乘数除以 5，然后将商相加，就可以得到阶乘结果中尾随零的数量

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

126/5 = 25 余数 1

25/5 = 5 余数 0

5/5 = 1 余数 0

25 + 5 + 1 = 31

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

剧终人散尽 2024-08-25 14:56:20

浏览了这个问题，不确定我是否真的答对了，但这是一个演绎性的猜测：

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

如何乘以 10？要么乘以 10，要么乘以 2 x 5...

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

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

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

回复收藏 0 原文

剪不断理还乱 2024-08-25 14:56:20

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

回复收藏 0 原文

一刻暧昧 2024-08-25 14:56:20

要解决这个问题，正如克里斯·约翰逊所说，你必须查看 0 的数量。

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

现在答案将大于(x,y)+z。

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

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

回复收藏 0 原文

尴尬癌患者 2024-08-25 14:56:20

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

任何 bignum 库都无法计算 10 亿阶乘。表示这些数字需要的空间比几乎任何人在 RAM 中所拥有的空间都多。当您处理这些数字时，您将必须开始从存储中调入这些数字。有一些方法可以做到这一点。最近计算出 π 到 27000 亿个位置的人使用了这样一个库

回复收藏 0 原文

诠释孤独 2024-08-25 14:56:20

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

回复收藏 0 原文

半城柳色半声笛 2024-08-25 14:56:20

我认为在开始考虑 C++ 或任何其他语言之前，您应该想出一种用伪代码解决问题的方法。正如一些人指出的那样，这个问题的本质更像是一个算法问题，而不是一个 C++ 问题。那些建议搜索一些不起眼的图书馆的人正在把你引向滑坡的方向，因为学习编程就是学习如何思考，对吗？找到一本好的算法分析文本，它会对你很有帮助。在我们系，我们根据 CLRS 文本进行教学。

回复收藏 0 原文

柳若烟 2024-08-25 14:56:20

你需要一个"big number"包 - 无论是你使用的还是一个你自己写的。

我建议对 “大量算法”。您需要实现 Java 的 BigDecimal。

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

回复收藏 0 原文

隱形的亼 2024-08-25 14:56:20

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

回复收藏 0 原文

灼痛 2024-08-25 14:56:20

    //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;
    }

    //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;
    }

回复收藏 0 原文

~没有更多了~