Обчислення факторіала великих чисел

В математиці факторіал числа — це добуток всіх натуральних чисел, менших або рівних даному числу. Іншими словами це результат множення всіх чисел від одного до заданого числа. Наприклад, факторіал числа 7 обчислюється як . Факторіал має багато застосувань, особливо в комбінаториці або в задачах підрахунку, тому для написання математичних програм може знадобитися спосіб його обчислення. Якщо Ви працюєте з мовою програмування Java, то матеріал даного параграфу може бути для Вас корисним. Адже сьогодні нами, використовуючи клас BigInteger, буде розроблена Java-програма для обчислення факторіала будь-якого розміру.

Отже, для початку створимо «Java Project», потім в ньому створимо «Java Class» і назвемо його, наприклад, Large_numbers_factorial. На наступному кроці, виходячи з того, що для обчислення факторіала, від користувача, нам знадобляться ціле число, то для його введення скористаємось класом Scanner з бібліотеки пакетів Java.

// Програма для обчислення факторіалу будь-якого розміру
import java.util.Scanner;
import java.math.BigInteger;
class Large_numbers_factorial { ­­­
    public static void main (String args[]) {
        Scanner scann = new Scanner(System.in);
        // Введення числа, факторіал якаого необхідно отримати
        System.out.print("Enter a number: ");
        int num = scann.nextInt();

Далі виконуємо перевірку: введене користувачем число має бути більшим або дорівнювати нулю. Якщо умова виконується, то обчислюємо факторіал і виводимо його значення в консоль. Якщо умова не виконується, то, виходячи з того, що факторіали визначені тільки для невід'ємних цілих чисел, генеруємо виключення яке інформує про те, що число num занадто мале.

Зауваження: виходячи з того, що BigInteger — це об'єкт, а не примітивний тип даних, то для множення об'єктів BigInteger не можна застосовувати оператор «*». Замість цього використовується метод multiply().

        if (num < 0)
            throw new IllegalArgumentException("The number you enter should not be less than zero!");
        // Обчислюємо та повертаємо факторіал числа num
        BigInteger res = Factorial(num);
        // Вивід результатів роботи програми
        System.out.println("The factorial of " + num + " : " + res);
    }
    // Обчислюємо факторіал заданого числа
    public static BigInteger Factorial(int number) {
        BigInteger factorial = BigInteger.valueOf(1);
        for (int i = number; i > 0; i--) {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }
        return factorial;
    }
}

Скомпілювавши, запустивши та задавши в якості числа для якого обчислюється факторіал, наприклад, значення 100, на екрані відобразиться наступний результат:

Факторіал числа Java

Факторіал числа 100

Тобто, як і очікувалось, програма знайде і поверне факторіал числа 100. Все це добре, але давайте тепер припустимо, що нам необхідно, за допомогою даної програми, знайти факторіали чисел від 1 до 100 (де 100 — задане користувачем число).

// Програма для обчислення факторіалу будь-якого розміру
import java.util.Scanner;
import java.math.BigInteger;
class Large_numbers_factorial { ­­­
    public static void main (String args[]) {
        Scanner scann = new Scanner(System.in);
        // Введення числа, факторіал якаого необхідно отримати
        System.out.print("Enter a number: ");
        int num = scann.nextInt();
        if (num < 0)
            throw new IllegalArgumentException("The number you enter should not be less than zero!");
        // Обчислюємо та повертаємо факторіали чисел від 1 до num
        for (int i = 1; i<= num; i++) {
            BigInteger res = Factorial(i);
            // Вивід результатів роботи програми
            System.out.println("The factorial of " + i + " : " + res);
        }
    }
    // Обчислюємо факторіал заданого числа
    public static BigInteger Factorial(int number) {
        BigInteger factorial = BigInteger.valueOf(1);
        for (int i = number; i > 0; i--) {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }
        return factorial;
    }
}

Комп'ютер виконає обчислення, і ми, знову-таки, отримаємо необхідний результата.

Факторіали чисел від 1 до 100

Однак, можна помітити, що, при повторному виклику, метод Factorial() виконує масу обчислень, які вже були виконані раніше. Тобто, добре було б, якби даний метод вмів запам'ятовувати результати обчислень, виконаних при його попередніх викликах і використовувати їх при наступних викликах для прискорення продуктивності. Зазначимо, що один із способів зробити це — скористатись ідеєю кешування.

Наступна версія Java-програми обчислює факторіали і кешує результати в таблиці для подальшого використання. Для кешування обчислених значень в ній застосовується ArrayList — службовий клас, який реалізує структуру даних, подібну до масивів і здатну розростатися до будь-якого потрібного розміру. Оскільки ArrayList — це об'єкт, а не масив, при роботі з ним доводиться застосовувати методи, такі як size(), add() і get().

// Програма для обчислення факторіалу будь-якого розміру використовучи ідею кешування
import java.util.Scanner;
import java.math.BigInteger;
import java.util.*;
class Large_numbers_factorial_caching {
    public static void main (String args[]) {
        // Перший елемент кешу ініціалізується значенням 0! = 1
        factorial_table.add(BigInteger.valueOf(1));
        Scanner scann = new Scanner(System.in);
        // Введення числа, факторіал якаого необхідно отримати
        System.out.print("Enter a number: ");
        int num = scann.nextInt();
        if (num < 0)
            throw new IllegalArgumentException("The number you enter should not be less than zero!");
        // Обчислюємо та повертаємо факторіали чисел від 1 до num
        for (int i = 1; i<= num; i++) {
            BigInteger res = Factorial(i);
            // Вивід результатів роботи програми
            System.out.println("The factorial of " + i + " : " + res);
        }
    }
    // Кеш таблиця
    protected static ArrayList<BigInteger> factorial_table = new ArrayList<BigInteger>();
    // Перший елемент кешу ініціалізується значенням 0! = 1
    static {
        factorial_table.add(BigInteger.valueOf(1));
    }
    // Обчислюємо факторіал заданого числа
    public static BigInteger Factorial(int number) {
        for (int i = factorial_table.size(); i <= number; i++) {
            BigInteger last = (BigInteger)factorial_table.get(i - 1);
            BigInteger next = last.multiply(BigInteger.valueOf(i));
            factorial_table.add(next);
        }
        return (BigInteger)factorial_table.get(number);
    }
}

Зазначимо, що вдосконалена версія Java-програми повертає аналогічний результат, проте, виходячи з того, що в методі Factorial() використовується ідея кешування, програма працює набагато швидше.

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар