Факториал на положително цяло число е произведението на цяло число и всички цели числа под него, т.е. факториалът на число n (представено с n!) Ще бъде дадено от
н! = 1 * 2 * 3 * 4 *. . . . . *н
Факториалът на 0 е дефиниран като 1 и не е дефиниран за отрицателни цели числа. Има няколко начина да го намерите, които са изброени по-долу -
- Факторна програма в Cс помощта на цикъл 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
сливане в c ++
Обяснение -
Числото, чийто факториал трябва да бъде намерен, се приема като вход и се съхранява в променлива и се проверява дали е отрицателно или не. Ако въведеното цяло число е отрицателно, се показва подходящо съобщение. Стойността на факториал е предварително дефинирана на 1, тъй като най-малката му стойност е 1. Цикълът for се изпълнява за положителни цели числа (с изключение на 0, за които условието на теста е невярно и по този начин фактът остава нула). В цикъла for стойността на факториал се умножава с всяко цяло число и се съхранява последователно до достигане на входния номер. Например, за вход = 5, потокът отива към цикъл for и се извършват следните стъпки-
факт = 1, i = 1 -> факт = 1 * 1 = 1 -> i = 2
факт = 1, i = 2 -> факт = 1 * 2 = 2 -> i = 3
факт = 2, i = 3 -> факт = 2 * 3 = 6 -> i = 4
факт = 6, i = 4 -> факт = 6 * 4 = 24 -> i = 5
факт = 24, i = 5 -> факт = 24 * 5 = 120 -> i = 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 }
Изход - Факториал на 5 = 120
какво е има връзка в Java
Обяснение-
Логиката на програмата е една и съща, с изключение на това, че се използва различна функция за изчисляване на факториала и връщане на стойността към основния метод, откъдето започва изпълнението.
Факториално използване на рекурсия
Рекурсията е процес, при който дадена функция се извиква и съответната функция се нарича рекурсивна функция. Състои се от две части - основно условие и рекурсивен разговор. Решението за основното състояние се предоставя, докато решението за по-голямата стойност може да бъде решено чрез преобразуване в по-малки стойности, докато базовото решение бъде достигнато и използвано.
По-долу е даден кодът за намиране на факториал с помощта на рекурсия: -
#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). Сега за факт (5) num е 5, което не е равно на 0, следователно потокът отива към оператора else, където в резултат на оператор се прави рекурсивно повикване и се прави факт (4). Процесът се повтаря, докато се достигне основното състояние, т.е. достигне число = 0 и се върне 1. Сега потокът преминава към fact (1), откъдето се връща 1 (както за fact (1) num = 1) * 1 (стойност, върната от fact (0)). Този процес се повтаря, докато се получи необходимата стойност.
Сложност във времето и пространството - рекурсия V / S итерация
За рекурсия-
Относно сложност във времето , знаем, че факториал 0 е единственото сравнение. Следователно T (0) = 1. За факториал на всяко друго число процесът включва едно сравнение, едно умножение, едно изваждане и едно извикване на функция. Следователно
намери най-големия елемент в масива java
T (n) = T (n-1) +3
= T (n-2) +6
= T (n-3) +9
= & hellip.
= T (n-k) + 3k
Тъй като знаем T (0) = 1 и за k = n, (n-k) = 0
Следователно T (n) = T (0) + 3n
= 1 + 3n
Следователно времевата сложност на кода е O (n).
Относно сложност на пространството, за всеки разговор се създава стек, който ще се поддържа, докато стойността му бъдеизчислени и върнати. Например за n = 5 трябва да се поддържат следните стекове
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“ и нашият екип ще се радва да отговори.