在C ++中计算大阶乘 [英] Calculating large factorials in C++

问题描述

我理解这是一个经典的编程问题，因此我想明确我不是寻找代码作为解决方案，但将欣赏一个正确的方向推。我正在学习C ++，作为学习过程的一部分，我试图一些编程问题。我试图写一个程序，处理数字到1亿的阶乘。显然，这些将是巨大的数量和方式太大，无法处理使用正常的算术运算。

I understand this is a classic programming problem and therefore I want to be clear I'm not looking for code as a solution, but would appreciate a push in the right direction. I'm learning C++ and as part of the learning process I'm attempting some programming problems. I'm attempting to write a program which deals with numbers up to factorial of 1billion. Obviously these are going to be enormous numbers and way too big to be dealing with using normal arithmetic operations. Any indication as to what direction I should go in trying to solve this type of problem would be appreciated.

我想尝试解决这个问题，如果可能的话，不使用额外的库

I'd rather try to solve this without using additional libraries if possible

感谢

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

PS - the problem is here http://www.codechef.com/problems/FCTRL

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

Here's the method I used to solve the problem, this was achieved by reading the comments below:

解决方案 - 数字5是任何数字的一个主要因素结束于零。因此，将阶乘数除以5，递归，并加上商，你得到尾数结果中的尾数零。

Solution -- The number 5 is a prime factor of any number ending in zero. Therefore, dividing the factorial number by 5, recursively, and adding the quotients, you get the number of trailing zeros in the factorial result

E.G。 - 126中的尾随零数！ = 31

E.G. - Number of trailing zeros in 126! = 31

126/5 = 25剩余1

126/5 = 25 remainder 1

25/5 = 5其余0

25/5 = 5 remainder 0

5/5 = 1剩余0

5/5 = 1 remainder 0

25 + 5 + 1 = 31

25 + 5 + 1 = 31

这适用于任何值，只是保持除法直到商小于
比5

This works for any value, just keep dividing until the quotient is less than 5

推荐答案

撇开这个问题，不知道我是否真的正确，但这里是一个演绎的猜测：

Skimmed this question, not sure if I really got it right but here's a deductive guess:

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

First question - how do you get a zero on the end of the number? By multiplying by 10.

如何乘以10？通过乘以10或2×5 ...

How do you multiply by 10? either by multiplying by either a 10 or by 2 x 5...

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

So, for X! how many 10s and 2x5s do you have...?

（幸运的2和5是素数）

(luckily 2 & 5 are prime numbers)

编辑：这里有另一个提示 - 认为你需要做任何乘法。让我知道，如果你需要另一个提示。

edit: Here's another hint - I don't think you need to do any multiplication. Let me know if you need another hint.

这篇关于在C ++中计算大阶乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！