Расчет больших факториалов в C ++

Question

Я понимаю, что это классическая проблема программирования, и поэтому я хочу пояснить, что не ищу код в качестве решения, но был бы признателен за продвижение в правильном направлении.Я изучаю C ++ и в процессе обучения пытаюсь решить некоторые проблемы программирования.Я пытаюсь написать программу, которая работает с числами до факториала в 1 миллиард.Очевидно, что они будут огромными числами и слишком большими, чтобы иметь дело с использованием обычных арифметических операций.Будем благодарны за любые указания относительно того, в каком направлении мне следует попытаться решить проблему такого типа.

Я бы лучше попытался решить эту проблему без использования дополнительных библиотек, если это возможно

Спасибо

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

Answer 1

Обдумал этот вопрос, не уверен, правильно ли я понял, но вот дедуктивное предположение:

Первый вопрос - как получить ноль в конце числа?Умножая на 10.

Как умножить на 10?либо умножением на 10, либо на 2 x 5 ...

Итак, для X!сколько у вас 10 и 2х5 ...?

(к счастью, 2 и 5 - простые числа)

edit: Вот еще один совет - я не думаю, что вам нужно умножить .Дайте мне знать, если вам нужен еще один намек.

Answer 2

Чтобы решить этот вопрос, как сказал Крис Джонсон, вам нужно взглянуть на число 0.

Коэффициенты 10 сами по себе будут равны 1,2,5,10.Итак, вы можете пройти через все числа N!и напишите их в терминах 2 ^ x * 5 ^ y * 10 ^ z.Откажитесь от других факторов чисел.

Теперь ответ будет больше из (x, y) + z.

Из этого вопроса я узнаю одну интересную вещь: всегда лучше хранить факториалчисло в терминах простых факторов для простых сравнений.

На самом деле x ^ y, в алгоритме RSA используется простой метод, который не запоминается.Я постараюсь обновить пост, если найду его.

Answer 3

Подсказка: вам может не понадобиться вычислять N!чтобы найти число нулей в конце N!

Answer 4

Я думаю, что вы должны найти способ решения проблемы в псевдокоде, прежде чем вы начнете думать о C ++ или любом другом языке в этом отношении.Природа вопроса, как отмечали некоторые, является скорее проблемой алгоритма, чем проблемой C ++.Те, кто предлагает поиск какой-то непонятной библиотеки, указывают вам в сторону скользкого спуска, потому что обучение программированию - это обучение мышлению, верно?Найдите хороший алгоритм анализа текста и он вам хорошо послужит.В нашем отделе мы преподаем текст CLRS .

Answer 5

Не используйте наивный метод.Если вам нужно рассчитать факториал, используйте быстрый алгоритм: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 6

Это не очень хороший ответ на ваш вопрос, поскольку вы немного изменили его по сравнению с тем, что я читал изначально.Но я все равно оставлю это здесь, чтобы продемонстрировать непрактичность реальных попыток выполнить вычисления с помощью основной грубой силы.

Один миллиард факториалов будет недоступен для любой библиотеки Бигнума.Такие числа потребуют больше места для представления, чем почти любой имеет в оперативной памяти.Вам придется начать разбивать номера на номера из хранилища, пока вы над ними работаете.Есть способы сделать это.Парень , который недавно подсчитал π до 2700 миллиардов мест , использовал такую ​​библиотеку

Answer 7

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

Answer 8

Чтобы вычислить большой факториал, вы можете использовать этот код в 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, этот код действительно может работать хорошо !!

Answer 9

Вам нужен пакет "большое число" - либо тот, который вы используете, либо тот, который вы пишете сами.

Я бы порекомендовал провести исследование "алгоритмов большого числа" . Вы захотите реализовать эквивалент C ++ Java BigDecimal .

Еще один способ взглянуть на это - использование гамма-функции . Вам не нужно умножать все эти значения, чтобы получить правильный ответ.

Answer 10

Для начала вам следует сохранить число в некотором массиве, например, std :: vector (цифра для каждой позиции в массиве), и вам нужно найти определенный алгоритм, который будет вычислять факториал (возможно какой-то специализированный класс). ;)