Рубрики

Факториал большого числа

Факториал неотрицательного целого числа — это умножение всех целых чисел, меньших или равных n. Например, факториал 6 равен 6 * 5 * 4 * 3 * 2 * 1, что равно 720.

Мы обсудили простую программу для факториала .

Как вычислить факториал из 100, используя программу на C / C ++?
Факториал 100 имеет 158 цифр. Невозможно сохранить эти много цифр, даже если мы используем long long int.

Примеры :

Input : 100
Output : 933262154439441526816992388562667004-
         907159682643816214685929638952175999-
         932299156089414639761565182862536979-
         208272237582511852109168640000000000-
         00000000000000

Input :50
Output : 3041409320171337804361260816606476884-
         4377641568960512000000000000

Ниже приводится простое решение, в котором мы используем массив для хранения отдельных цифр результата. Идея состоит в том, чтобы использовать базовую математику для умножения.

Ниже приведен подробный алгоритм поиска факториала.

факториала (п)
1) Создайте массив 'res []' размера MAX, где MAX — количество максимальных цифр в выводе.
2) Инициализируйте значение, сохраненное в 'res []' как 1, и инициализируйте 'res_size' (размер 'res []') как 1.
3) Выполните следующие действия для всех чисел от x = 2 до n.
…… а) Умножьте x на res [] и обновите res [] и res_size, чтобы сохранить результат умножения.

Как умножить число 'x' на число, сохраненное в res []?
Идея состоит в том, чтобы использовать простую школьную математику. Мы по одному умножаем x на каждую цифру res []. Здесь важно отметить, что цифры умножаются с крайней правой цифры на самую левую. Если мы храним цифры в том же порядке в res [], тогда становится трудно обновить res [] без лишнего пробела. Вот почему res [] поддерживается в обратном порядке, т. Е. Сохраняются цифры справа налево.

умножить (res [], x)
1) Инициализируйте перенос как 0.
2) Выполните следующие действия для i = 0 до res_size — 1
… .A) Найти значение res [i] * x + carry. Пусть это значение будет прод.
… .B) Обновите res [i], сохранив в нем последнюю цифру prod.
… .C) Обновите перенос, сохранив оставшиеся цифры в переносе.
3) Поместите все цифры переноса в res [] и увеличьте res_size на количество цифр в переносе.

Example to show working of multiply(res[], x)
A number 5189 is stored in res[] as following.
res[] = {9, 8, 1, 5}
x = 10

Initialize carry = 0;

i = 0, prod = res[0]*x + carry = 9*10 + 0 = 90.
res[0] = 0, carry = 9

i = 1, prod = res[1]*x + carry = 8*10 + 9 = 89
res[1] = 9, carry = 8

i = 2, prod = res[2]*x + carry = 1*10 + 8 = 18
res[2] = 8, carry = 1

i = 3, prod = res[3]*x + carry = 5*10 + 1 = 51
res[3] = 1, carry = 5

res[4] = carry = 5

res[] = {0, 9, 8, 1, 5} 

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для вычисления факториала больших чисел
#include<iostream>

using namespace std;

  
// Максимальное количество цифр в выводе
#define MAX 500

  

int multiply(int x, int res[], int res_size);

  
// Эта функция находит факториал больших чисел
// и печатает их

void factorial(int n)

{

    int res[MAX];

  

    // Инициализировать результат

    res[0] = 1;

    int res_size = 1;

  

    // Применяем простую факториальную формулу n! = 1 * 2 * 3 * 4 ... * n

    for (int x=2; x<=n; x++)

        res_size = multiply(x, res, res_size);

  

    cout << "Factorial of given number is \n";

    for (int i=res_size-1; i>=0; i--)

        cout << res[i];

}

  
// Эта функция умножает x на число
// представлен res [].
// res_size - это размер res [] или количество цифр в
// число, представленное res []. Эта функция использует простой
// Школьная математика для умножения.
// Эта функция может иметь значение res_size и возвращает
// новое значение res_size

int multiply(int x, int res[], int res_size)

{

    int carry = 0;  // Инициализируем перенос

  

    // умножаем n на отдельные цифры res []

    for (int i=0; i<res_size; i++)

    {

        int prod = res[i] * x + carry;

  

        // Сохранить последнюю цифру 'prod' в res []

        res[i] = prod % 10;  

  

        // Положи отдых в керри

        carry  = prod/10;    

    }

  

    // Помещаем перенос в res и увеличиваем размер результата

    while (carry)

    {

        res[res_size] = carry%10;

        carry = carry/10;

        res_size++;

    }

    return res_size;

}

  
// Драйвер программы

int main()

{

    factorial(100);

    return 0;

}

Джава

// JAVA-программа для вычисления факториала
// больших чисел

class GFG {

      

    // Эта функция находит факториал

    // большие числа и печатаем их

    static void factorial(int n)

    {

        int res[] = new int[500];

  

        // Инициализировать результат

        res[0] = 1;

        int res_size = 1;

  

        // Применяем простую факториальную формулу

        // n! = 1 * 2 * 3 * 4 ... * n

        for (int x = 2; x <= n; x++)

            res_size = multiply(x, res, res_size);

  

        System.out.println("Factorial of given number is ");

        for (int i = res_size - 1; i >= 0; i--)

            System.out.print(res[i]);

    }

      

    // Эта функция умножает x на число

    // представлен res []. res_size - это размер res [] или

    // количество цифр в числе, представленном res [].

    // Эта функция использует простую школьную математику для

    // умножение. Эта функция может иметь значение res_size

    // и возвращает новое значение res_size

    static int multiply(int x, int res[], int res_size)

    {

        int carry = 0; // Инициализируем перенос

  

        // умножаем n на единицу

        // цифры res []

        for (int i = 0; i < res_size; i++)

        {

            int prod = res[i] * x + carry;

            res[i] = prod % 10; // Сохранить последнюю цифру

                                // 'prod' в res []

            carry = prod/10; // Положи отдых в керри

        }

  

        // Помещаем перенос в res и увеличиваем размер результата

        while (carry!=0)

        {

            res[res_size] = carry % 10;

            carry = carry / 10;

            res_size++;

        }

        return res_size;

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        factorial(100);

    }

}
// Этот код предоставлен Никитой Тивари

питон

# Программа Python для вычисления факториала
# больших чисел

  

import sys

  
# Эта функция находит факториал большого
# номера и распечатывает их

def factorial( n) :

    res = [None]*500

    # Инициализировать результат

    res[0] = 1

    res_size = 1

  

    # Применить простую факториальную формулу

    # п! = 1 * 2 * 3 * 4 ... * n

    x = 2

    while x <= n :

        res_size = multiply(x, res, res_size)

        x = x + 1

      

    print ("Factorial of given number is")

    i = res_size-1

    while i >= 0 :

        sys.stdout.write(str(res[i]))

        sys.stdout.flush()

        i = i - 1

          

  
# Эта функция умножает х на число
# представлен res []. res_size - это размер res []
# или количество цифр в представленном номере
# by res []. Эта функция использует простую школу
# математика для умножения. Эта функция
# может принимать значение res_size и возвращает новое значение
# из res_size

def multiply(x, res,res_size) :

      

    carry = 0 # Инициализировать перенос

  

    # Один за другим умножить п с индивидуальным

    # цифры res []

    i = 0

    while i < res_size :

        prod = res[i] *x + carry

        res[i] = prod % 10; # Сохранить последнюю цифру

                            # 'prod' в res []

        carry = prod/10; # Положить отдых в керри

        i = i + 1

  

    # Поместите перенос в res и увеличьте размер результата

    while (carry) :

        res[res_size] = carry % 10

        carry = carry / 10

        res_size = res_size + 1

          

    return res_size

  
# Драйверная программа

factorial(100)

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для вычисления
// факториал больших чисел

using System;

  

class GFG

{

      

    // Эта функция находит факториал

    // больших чисел и печатает их

    static void factorial(int n)

    {

        int []res = new int[500];

  

        // Инициализировать результат

        res[0] = 1;

        int res_size = 1;

  

        // Применяем простую факториальную формулу

        // n! = 1 * 2 * 3 * 4 ... * n

        for (int x = 2; x <= n; x++)

            res_size = multiply(x, res, 

                                res_size);

  

        Console.WriteLine("Factorial of "

                       "given number is ");

        for (int i = res_size - 1; i >= 0; i--)

            Console.Write(res[i]);

    }

      

    // Эта функция умножает х

    // с указанным числом

    // по res []. res_size это размер

    // из res [] или количества цифр

    // в числе, представленном

    // res []. Эта функция использует

    // простая школьная математика для

    // умножение. Эта функция

    // может иметь значение res_size и

    // возвращает новое значение res_size

    static int multiply(int x, int []res, 

                        int res_size)

    {

        int carry = 0; // Инициализируем перенос

  

        // умножаем n на одно

        // отдельные цифры res []

        for (int i = 0; i < res_size; i++)

        {

            int prod = res[i] * x + carry;

            res[i] = prod % 10; // Сохранить последнюю цифру

                                // 'prod' в res []

            carry = prod / 10; // Положи отдых в керри

        }

  

        // Поместить перенос в Res и

        // увеличиваем размер результата

        while (carry != 0)

        {

            res[res_size] = carry % 10;

            carry = carry / 10;

            res_size++;

        }

        return res_size;

    }

  

    // Код драйвера

    static public void Main ()

    {

          

        factorial(100);

    }

}

  
// Этот код предоставлен ajit

PHP

<?php
// PHP-программа для вычисления факториала
// больших чисел

  
// Максимальное количество цифр в выводе

$MAX = 500;

  
// Эта функция находит факториал
// большие числа и печатаем их

function factorial($n)

{

    global $MAX;

    $res = array_fill(0, $MAX, 0);

  

    // Инициализировать результат

    $res[0] = 1;

    $res_size = 1;

  

    // Применяем простую факториальную формулу

    // n! = 1 * 2 * 3 * 4 ... * n

    for ($x = 2; $x <= $n; $x++)

        $res_size = multiply($x, $res, $res_size);

  

    echo "Factorial of given number is \n";

    for ($i = $res_size - 1; $i >= 0; $i--)

        echo $res[$i];

}

  
// Эта функция умножает x на число
// представлен res [].
// res_size - это размер res [] или количество
// цифры в номере, представленном res [].
// Эта функция использует простую школьную математику
// для умножения. Эта функция может иметь значение
// из res_size и возвращает новое значение res_size

function multiply($x, &$res, $res_size)

{

    $carry = 0; // Инициализируем перенос

  

    // умножаем n на единицу

    // цифры res []

    for ($i = 0; $i < $res_size; $i++)

    {

        $prod = $res[$i] * $x + $carry;

  

        // Сохранить последнюю цифру 'prod' в res []

        $res[$i] = $prod % 10; 

  

        // Положи отдых в керри

        $carry = (int)($prod / 10); 

    }

  

    // Поместить carry в res и увеличить

    // размер результата

    while ($carry)

    {

        $res[$res_size] = $carry % 10;

        $carry = (int)($carry / 10);

        $res_size++;

    }

    return $res_size;

}

  
// Код драйвера
factorial(100);

      
// Этот код приписан chandan_jnu
?>


Выход :

Factorial of given number is
9332621544394415268169923885626670049071596826438162146859296389
5217599993229915608941463976156518286253697920827223758251185210
916864000000000000000000000000

Вышеуказанный подход может быть оптимизирован многими способами. Мы скоро будем обсуждать оптимизированное решение для того же.

Эта статья предоставлена Харшитом Агравалом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Факториал большого числа

0.00 (0%) 0 votes