Факториал положительного целого числа - это произведение целого числа и всех целых чисел под ним, то есть факториал числа n (представленного n!) Будет иметь вид
п! = 1 * 2 * 3 * 4 *. . . . . * п
Факториал 0 определяется как 1 и не определен для отрицательных целых чисел. Есть несколько способов найти его, которые перечислены ниже:
- Факториальная программа на Cиспользуя цикл For
- Факториальная программа с использованиемФункции
- Факториальная программаиспользуя рекурсию
Давайте начнем.
Факториал с использованием цикла for
Это самый простой и легкий способ найти факториал числа. Давайте сначала посетим код -
#include int main () {int I, num, fact = 1 // определение факториала как 1, поскольку наименьшее значение равно 1 printf («Введите число для вычисления его факториала») scanf («% d», & num) if (num<0) //if the input is a negative integer { printf (“Factorial is not defined for negative numbers.”) } else { for(i=1i0, therefore fact value remains 1 { fact = fact * i // keeps on multiplying and storing in the value of factorial till the input integer is reached } printf(“Factorial of %d = %dn”, num, fact) } return 0 //since we have defined the main() method with a return value of integer type }Вывод-
Факториал 5 = 120
Объяснение -
Число, факториал которого должен быть найден, принимается в качестве входных и сохраняется в переменной, и проверяется, отрицательное оно или нет. Если введенное целое число отрицательное, отображается соответствующее сообщение. Значение факториала предопределено равным 1, поскольку его наименьшее значение равно 1. Цикл for выполняется для положительных целых чисел (за исключением 0, для которого условие проверки ложно и, таким образом, факт остается нулевым). В цикле for значение факториала умножается на каждое целое число и сохраняется до тех пор, пока не будет достигнуто входное число. Например, для input = 5 поток переходит в цикл for и выполняются следующие шаги:
факт = 1, я = 1 -> факт = 1 * 1 = 1 -> я = 2
факт = 1, я = 2 -> факт = 1 * 2 = 2 -> я = 3
факт = 2, я = 3 -> факт = 2 * 3 = 6 -> я = 4
факт = 6, я = 4 -> факт = 6 * 4 = 24 -> я = 5
факт = 24, я = 5 -> факт = 24 * 5 = 120 -> я = 6
Теперь 6> 5, поэтому условие проверки становится ложным, и цикл завершается. Отображается значение факториала.
Факториал с использованием функций
Этот подход известен как модульный подход, и его следует использовать при программировании, поскольку он достаточно эффективен. Одно из его преимуществ состоит в том, что, когда нам нужно внести изменения в код, вместо изменения всего кода мы можем просто изменить соответствующую функцию. Код для нахождения факториала числа с использованием этого подхода показан ниже.
#include long factorial (int num) // функция для вычисления факториала, которая принимает целочисленное значение в качестве параметра и возвращает значение типа int {int i long fact = 1 for (i = 1 i<= num i++) fact = fact * i return fact //returns to function call } int main() //execution begins from main() method { int num printf('Enter a number to calculate its factorialn') scanf('%d', &num) if(num<0) //if the input is a negative integer { printf('Factorial is not defined for negative numbers.') } printf('Factorial of %d = %dn', num, factorial(num)) //call to factorial function passing the input as parameter return 0 }
установка пути к классам Java в Linux
Вывод - Факториал 5 = 120
Объяснение-
Логика программы такая же, за исключением того, что для вычисления факториала и возврата значения в основной метод используется другая функция, с которой начинается выполнение.
Факториал с использованием рекурсии
Рекурсия - это процесс, в котором функция вызывает себя, а соответствующая функция называется рекурсивной функцией. Он состоит из двух частей - базового условия и рекурсивного вызова. Предоставляется решение базового условия, в то время как решение для большего значения может быть решено путем преобразования в меньшие значения до тех пор, пока базовое решение не будет достигнуто и использовано.
Ниже приведен код для поиска факториала с использованием рекурсии: -
#include int fact (int) // прототип функции int main () {int num printf ('Введите число, факториал которого должен быть найден:') scanf ('% d', & num) if (num<0) { printf('ERROR. Factorial is not defined for negative integers') } printf('Factorial of %d is %d', num, fact(num)) //first call is made return 0 } int fact(int num) { if(num==0) //base condition { return 1 } else{ return(num*fact(num-1)) //recursive call } } Вывод - Факториал 5 = 120
Объяснение -Предположим, пользователь вводит 5 в качестве входных данных, тогда в методе main () значение num равно 5. По мере прохождения потока в операторе printf (строка 12) выполняется вызов функции fact (5). Теперь для fact (5) num равно 5, что не равно 0, поэтому поток переходит к оператору else, где в операторе return выполняется рекурсивный вызов и выполняется fact (4). Процесс повторяется до тех пор, пока не будет достигнуто базовое условие, т.е. num = 0 и не будет возвращено 1. Теперь поток переходит к fact (1), откуда возвращается 1 (как для fact (1) num = 1) * 1 (значение, возвращаемое из fact (0)). Этот процесс повторяется до тех пор, пока не будет получено необходимое значение.
Сложность во времени и пространстве - итерация V / S с рекурсией
Для рекурсии-
Что касается временная сложность , мы знаем, что факториал 0 - единственное сравнение. Следовательно, T (0) = 1. Для факториала любого другого числа процесс включает одно сравнение, одно умножение, одно вычитание и один вызов функции. Следовательно
Т (п) = Т (п-1) +3
= Т (п-2) +6
= Т (п-3) +9
= & hellip.
= Т (п-к) + 3к
Поскольку мы знаем, что T (0) = 1 и для k = n, (n-k) = 0
Следовательно, T (n) = T (0) + 3n
= 1 + 3n
Следовательно, временная сложность кода O (n).
Что касается космическая сложность, для каждого вызова создается стек, который будет поддерживаться до тех пор, пока его значение не станетвычислено и возвращено. Например, для n = 5 необходимо поддерживать следующие стеки
установить путь к классу для java
f (5) -> f (4) -> f (3) -> f (2) -> f (1) -> f (0)
Как мы видим, необходимо поддерживать 5 стеков до тех пор, пока не будет достигнут вызов функции f (0), значение которой равноизвестно и возвращается. Следовательно, для n факториала необходимо поддерживать n стеков. Таким образом, космическая сложностьравно O (n). Из приведенных выше рисунков также видно, что для n = 5 потребуется 5 стопок.поддерживается. Следовательно, для n факториала необходимо поддерживать n стеков. Таким образом, сложность пространства O (n).
Для итерации-
Что касается временная сложность, внутри цикла n итераций, поэтому временная сложность O (n).
Что касается космическая сложность, для итеративного решения необходимо поддерживать только один стек и используется целочисленная переменная. Таким образом, сложность пространства O (1).
Это все для этой статьи. Я надеюсь, что вы поняли концепцию факторной программы в C вместе с временными сложностями.
Если у вас возникнут какие-либо вопросы, не стесняйтесь задавать все свои вопросы в разделе комментариев «факторной программы на C», и наша команда будет рада ответить.