n! Факториал
Написать программу на C++ для вычисления(нахождения или решения) факториала — это очень популярное задание в сборниках по обучению программированию. Решение этой задачи и многих других размещено в разделе с решениями задач по программированию на C++. В данной статье мы разберем как реализовать решение на языке программирования C++.
Для начала — что такое факториал?
Факториал — это произведение всех натуральных чисел от 1 до N включительно. То есть, если N = 5, то значение факториала
F = 1*2*3*4*5 = 120.
Решить данную задачу можно несколькими способами, мы рассмотрим рекурсивное вычисление факториала и циклическое.
До начала вычислений необходимо узнать N. N может быть больше или равно единице (N>=0). Поэтому для начала напишем каркас приложения, которое будет получать значение N и проверять его. Если N не соответствует, то программа выдаст ошибку «Error: N < 0.«. Листинг программы следующий:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; int main() { int N; // Объявляем переменную N целочисленного типа cout << "N = "; cin >> N; // Присваиваем введенное значение в переменную if(N >= 0) { // Здесь будет код, вычислящий факториал } else { cout << "Error: N < 0."; // Выводим ошибку, т.к. N < 0 } return 0; } |
Проверим ее.
Компилируем, запускаем и вводим любую N, которая меньше 0.
Значение N = -5
Получили ошибку, программа сообщила, что N < 0.
Запускаем и вводим любую N, которая больше или равно 0.
Значение N = 5
Программа ничего не вывела после, значит выполнился участок кода, где написано «Здесь будет код…«.
Теперь нам достаточно вставить в место, где написано «Здесь будет код…» нужную реализацию алгоритма по нахождению факториала.
Нахождение факториала с помощью цикла
Для нахождения факториала напишем свою функцию, которая будет принимать значение N и возвращать результат.
Реализовать алгоритм нахождения факториала очень просто:
|
5 6 7 8 9 10 11 12 13 14 |
int factorial(int N) { int F = 1; for(int i=1; i<=N; ++i) { F *= i; // Эквивалент F = F*i; } return F; // Возвращаем ответ } |
Что делает функция? Принимает значение N, после чего определяется переменная F, она будет хранить в себе ответ. Запускается цикл for от 1 до N, то есть переменная i будет иметь значения от 1 до N, эти значения мы используем для перемножения переменной F.
Для N=0 значение факториала равно 1. Цикл не будет вообще выполняться, т.к. i должна быть меньшей или равной N, в данном случае первое значение i=1, а N=0. Функция просто возвратит F, которая равно 1.
Для N=1 значение факториала равно 1. Цикл выполнится 1 раз, произойдет умножение F на i, а так как первое значение i = 1, то F так и останется равна 1.
Для остальных значений N цикл будет выполняться N раз, с каждой итерацией i будет увеличиваться на 1 и умножать на себя F.
(F = F*i).
Вставляем функцию в нашу программу:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; //Начало функции нахождения факториала int factorial(int N) { int F = 1; for(int i=1; i<=N; ++i) { F *= i; } return F; } //Конец функции нахождения факториала int main() { int N; cout << "N = "; cin >> N; if(N >= 0) { cout << factorial(N); // Тут мы передаем нашей функции N и выводим ответ } else { cout << "Error: N < 0."; } return 0; } |
Теперь проверим работу программы, для этого скомпилируем, запустим и попробуем ввести различные значения.
Пусть найдет факториал от 0
Факториал от 0
Получили значение 1. Мы знаем, что факториал от 0 равен единице, здесь программа работает верно.
Пусть найдет факториал от 1
Факториал от 1
Получили значение 1. Мы знаем, что факториал от 1 равен единице, здесь программа тоже работает верно.
Пусть найдет факториал от 5
Факториал от 5
Получили значение 120. Проверим: F = 1*2*3*4*5 = 120. Программа верно вычислила факториал.
Рекурсивное нахождение факториала
Для такого способа мы тоже напишем функцию, но она не будет содержать цикла. Рекурсивная функция — это функция, которая вызывает сама себя.
Наша функция factorial() будет принимать значение N и возвращать N*factorial(N-1). То есть будет возвращать значение N умноженное на саму себя, но только с N-1.
Код реализации рекурсивной функции нахождения факториала
|
5 6 7 8 9 10 |
int factorial(int N) { if(N==0) return 1; // Если factorial(0), то возвращаем 1 if(N==1) return 1; // Если factorial(1), то возвращаем 1 return N*factorial(N-1); // А если нет, то возвращаем значение N*factorial(N-1) } |
Как это работает?
Допустим, N = 3. Мы передаем значение функции factorial(3), а она возвращает значение 3 * factorial(2), в свою очередь factorial(2) возвращает 2 * factorial(1), а factorial(1) возвращает 1. И теперь мы идем в обратном порядке:
factorial(1) = 1;
factorial(2) = 2 * factorial(1) = 2 * 1 = 2;
factorial(3) = 3 * factorial(2) = 3 * 2 = 6;
Вызванная функция factorial(3) возвратит нам 6.
А factorial(0) и factorial(1) сразу вернут 1.
Вставим рекурсивную функцию в программу для нахождения факториала:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> using namespace std; // Начало рекурсивной функции нахождения факториала int factorial(int N) { if(N==0) return 1; if(N==1) return 1; return N*factorial(N-1); } // Конец функции int main() { int N; cout << "N = "; cin >> N; if(N >= 0) { cout << factorial(N); // Передаем функции N и выводим результат } else { cout << "Error: N < 0."; } return 0; } |
Компилируем, запускаем и проверяем.
Значение факториала для 0
Факториал от 0
Вывела 1, а мы знаем, что факториал от 0 равен 1. Значит работает верно.
Значение факториала для 1
Факториал от 1
Вывела 1, а мы знаем, что факториал от 1 равен 1. Значит работает верно.
Значение факториала для 5
Факториал от 5
Получили значение 120. Проверим:
F = 1*2*3*4*5 = 120.
Программа верно вычислила факториал.
Послесловие
Итак, мы написали две функции разными способами, которые выполняют решают одну и ту же задачу — вычисление значения факториала. Эта задача входит в список с решениями задач по программированию, если вам нужно решить еще задачу — загляните туда, возможно вы найдете нужное решение. Если остались вопросы, то задавайте их в комментариях.
Очень полезная статья, сразу все стало понятно))Спасибо!
Я написал нечто подобное на обычном Си но столкнулся с проблемой программа корректно высчитывает факториал только до 12, можете помочь ее решить ?
может дело в том что лимит значений был превышен ?
#include
int n_factorial(int n);
int main()
{
int n, res;
printf(» [ n factorial finder ] \n\n»);
for(int sucl=0; sucl==0;){
printf(» n = «);
scanf(«%i»,&n);
if(n==0){
printf(» %i! = 1″,n);
} else
if(n>0){
res=n_factorial(n);
printf(» %i! = %i»,n,res);
} else
if(n<0){
printf(" n cannot be < 0");
} else
printf(" error :\\ ");
printf("\n\n");
}
return 0;
}
n_factorial(int n){
int res=1;
for(int sucl=1; sucl<=n; sucl++){
res=sucl*res;
}
return res;
}