Как написать программу факториал - Правописание и грамматика

n! Факториал

Написать программу на C++ для вычисления(нахождения или решения) факториала — это очень популярное задание в сборниках по обучению программированию. Решение этой задачи и многих других размещено в разделе с решениями задач по программированию на C++. В данной статье мы разберем как реализовать решение на языке программирования C++.

Для начала — что такое факториал?

Факториал — это произведение всех натуральных чисел от 1 до N включительно. То есть, если N = 5, то значение факториала

F = 1*2*3*4*5 = 120.

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

До начала вычислений необходимо узнать N. N может быть больше или равно единице (N>=0). Поэтому для начала напишем каркас приложения, которое будет получать значение N и проверять его. Если N не соответствует, то программа выдаст ошибку «Error: N < 0.«. Листинг программы следующий:

#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 и возвращать результат.

Реализовать алгоритм нахождения факториала очень просто:

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).

Вставляем функцию в нашу программу:

#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.

Код реализации рекурсивной функции нахождения факториала

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.

Вставим рекурсивную функцию в программу для нахождения факториала:

#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.

Программа верно вычислила факториал.

Послесловие

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

Источник

Вычисление факториала

Вводится натуральное число. Вычислить его факториал.
Решение задачи на языке программирования Python

Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1 * 2 * 3 * 4 * 5 = 120.

Формула нахождения факториала:

n! = 1 * 2 * … * n,

где n – это число, а n! – факториал этого числа.

Формулу можно представить в таком виде:

n! = 1 * … * (n-2) * (n-1) * n,

т. е. каждый предыдущий множитель меньше на единицу, чем последующий.

С помощью цикла можно найти факториал как по первой, так и второй формуле. Для вычисления факториала с помощью рекурсии используется вторая формула.

Вычисление факториала циклом

n = int(input())
 
factorial = 1
while n > 1:
    factorial *= n
    n -= 1
 
print(factorial)

Вычисление факториала с помощью цикла for:

n = int(input())
 
factorial = 1
 
for i in range(2, n+1):
    factorial *= i
 
print(factorial)

Нахождение факториала рекурсией

def fac(n):
    if n == 0:
        return 1
    return fac(n-1) * n
 
 
print(fac(5))

0 шаг. Вызов функции: fac(5)
1. fac(5) возвращает fac(4) * 5
2. fac(4) => fac(3) * 4
3. fac(3) => fac(2) * 3
4. fac(2) => fac(1) * 2
5. fac(1) => 1
6. 1 * 2 — возврат в вызов fac(2)
7. 2 * 3 — fac(3)
8. 6 * 4 — fac(4)
9. 24 * 5 – fac(5)
10. Возврат в основную ветку программы значения 120.

Функция factorial модуля math

Модуль math языка программирования Python содержит функцию factorial, принимающую в качестве аргумента неотрицательное целое число и возвращающую факториал этого числа:

>>> import math
>>> math.factorial(4)
24

Больше задач в PDF

Источник

Язык Си в примерах

Компиляция программ
Простейшая программа «Hello World»
Учимся складывать
Максимум
Таблица умножения
ASCII-коды символов
Верхний регистр
Скобочки
Факториал
Степень числа
Треугольник Паскаля
Корень уравнения
Система счисления
Сортировка
Библиотека complex
Сортировка на основе qsort
RPN-калькулятор
RPN-калькулятор на Bison
Простая грамматика
Задача «Расчёт сопротивления схемы»
Простая реализация конечного автомата
Использование аргументов командной строки
Чтение и печать без использования stdio
Декодирование звукозаписи в формате ADX
Другие примеры

Факториалом числа n называют произведение первых n натуральных чисел:

${displaystyle n!=1cdot 2cdot ldots cdot n=prod _{i=1}^{n}i.}$

Ниже мы рассмотрим примеры программ, содержащих вычисляющую факториал заданного числа функцию factorial.

Реализация рекуррентной формулы[править]

#include <stdio.h>

static int
factorial (int n)
{
  return (n < 2) ? 1 : n * factorial (n - 1);
}

int
main (void)
{
  int n;
  while (scanf ("%d", &n) == 1) {
    printf ("%dn", factorial (n));
  }
  return 0;
}

Определение функции factorial выше основано на следующей рекуррентной
формуле:

{displaystyle n!=ncdot (n-1)!,quad 0!=1.}

Для вычисления факториала n! эта функция вызывает саму себя с аргументом n − 1.

Тернарный оператор (? :) в выражении (n < 2) ? 1 : n * factorial (n - 1) для возвращаемого значения (return) «обрывает» рекурсию, когда аргумент функции становится меньшим 2. В противном случае,
функция factorial постоянно бы вызывала саму себя, и во
время выполнения программы мы получили бы сообщение об ошибке
«переполнение стека» или «превышена глубина рекурсии». Для
того, чтобы этого не было, необходимо, чтобы при некоторых
значения аргумента, функция не вызывала саму себя, а вычисляла
свое значение «самостоятельно».

Идея рекурсии заключается в сведении задачи к этой же задаче, но
для более простых случаев (например, для меньшего значения
аргумента n). Процесс сведения задачи к предыдущей должен
когда-нибудь заканчиваться, поэтому рекурсивные функции для
простейших входных данных должны «знать», чему они равны и не
делать рекурсивных вызовов.

Использование хвостовой рекурсии[править]

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

В примере ниже, мы воспользуемся хвостовой рекурсией, сведение которой к итерации хотя и не требуется стандартом, но все же реализуется, например, компилятором C, входящим в распространенный комплект GCC. Для этого, нам потребуется определить вспомогательную функцию factorial_1, вычисляющую значение p n!, где p, n — аргументы функции.

Обратите внимание, что в этом примере мы не приводим ни определения функции main, ни директив препроцессора #include подключения используемых нами заголовков — их следует заимствовать из предыдущего примера.

static int
factorial_1 (int n, int p)
{
  return (n < 2) ? p : factorial_1 (n - 1, p * n);
}

static int
factorial (int n)
{
  return factorial_1 (n, 1);
}

Явно итеративный вариант[править]

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

static int
factorial (int n)
{
  int r;
  for (r = 1; n > 1; r *= (n--))
    ;
  return r;
}

В отличие от первого варианта (но аналогично варианту с хвостовой рекурсией) в данном примере нам потребовалась дополнительная локальная переменная. В случае «нехвостовой» рекурсии — роль такой переменной фактически играет растущий стек возврата. Отметим, впрочем, что в данной конкретной задаче это не столь важно.

Вариант «произвольный»[править]

Стандарт требует поддержки реализацией числовых типов разрядности 8, 16, 32 и 64 бит.^[1] Несложно убедиться, однако, что уже 21! = 51 090 942 171 709 440 000 — что превышает предельные значения для 64-битового числа — как со знаком (9 223 372 036 854 775 807), так и без знака (18 446 744 073 709 551 615).

Если по каким-либо причинам требуется вычислить точные значения факториала для чисел от 21 и выше, следует использовать библиотеки операций с числами произвольной разрядности — как, например, GNU MP.^[2]

#include <stdio.h>
#include <gmp.h>

static void
factorial (long n, mpz_t r)
{ 
  mpz_init_set_si (r, 1);
  for (; n > 1; n--) {
    mpz_mul_si (r, r, n);
  }
}

int
main (void)
{
  int n;
  mpz_t r;
  while (scanf ("%d", &n) == 1) {
    factorial (n, r);
    gmp_printf ("%Zdn", r);
  }
  return 0;
}

Задания[править]

Улучшите программы, добавив к ним диагностику ошибки во входных данных: если n < 0, то программа должна ясно сообщать о неопределенности факториала для отрицательных чисел.
Опытным путем определите максимальные значения аргумента и результата для «стандартных» программ выше. Исследуйте влияние на эти значения замены используемого в программах числового типа int на short, long и long long. Обратите внимание, что при этом также потребуется соответственно изменить строку формата (первый аргумент) функции printf.
Определите также максимальные значения аргумента и результата для этих программ при использовании чисел с плавающей запятой — числовых типов double, float, long double.

См. также[править]

Реализации алгоритмов/Факториал (на различных языках)

Примечания[править]

↑ 7.20.1.2 Minimum-width integer types(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
↑ The GNU MP Bignum Library(англ.) Проверено 2015-04-04 г.

Источник

На чтение 3 мин Просмотров 89 Опубликовано 28.02.2023

Содержание

Введение
Вычисление факториала циклом while
Цикл while
Цикл for
Вычисление факториала Рекурсией
Вычисление факториала методом factorial()
Заключение

Введение

В ходе статьи рассмотрим 3 способа вычислить факториал в Python.

Вычисление факториала циклом while

Цикл while

Для начала дадим пользователю возможность ввода числа и создадим переменную factorial равную единице:

number = int(input('Введите число: '))
factorial = 1

Как мы знаем, факториал – это произведение натуральных чисел от единицы до числа n. Следовательно создадим цикл, который не закончится, пока введённое пользователем число больше единицы. Внутри цикла увеличиваем значение в переменной factorial умножая его на переменную number, после чего уменьшаем значение в number на единицу:

number = int(input('Введите число: '))
factorial = 1

while number > 1:
    factorial = factorial * number
    number = number - 1

print(factorial)

# Введите число: 10
# 3628800

Цикл for

Обычно способ нахождения факториала при помощи цикла for не рассматривается, но почему бы и нет. Принцип не сильно отличается от цикла while, просто приравниваем значение введённое пользователем к переменной factorial, а в цикле указываем количество итреаций начиная с единицы, и заканчивая введённым числом:

number = int(input('Введите число: '))
factorial = number

for i in range(1, number):
    factorial = factorial * i

print(factorial)

# Введите число: 5
# 120

Вычисление факториала Рекурсией

Для вычисления факториала про помощи рекурсии, создадим функцию factorial(), и в качестве аргумента передадим number:

Внутри функции добавим условие, что если переданное число в аргумент number равняется единице, то возвращаем его. Если же условие не сработало, то вернётся аргумент number умноженный на вызов функции factorial() с передачей аргумента number – 1:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)

Дадим пользователю возможность ввода, вызовем функцию и выведем результат в консоль:

def factorial(number):
    if number == 1:
        return number
    else:
        return number * factorial(number - 1)


print(factorial(int(input('Введите число: '))))

# Введите число: 7
# 5040

Вычисление факториала методом factorial()

В стандартном модуле math есть специальный метод для вычисления факториала под названием factorial(). Используем его для нахождения факториала:

from math import factorial

number = int(input('Введите число: '))

print(factorial(number))

# Введите число: 4
# 24

Заключение

В ходе статьи мы с Вами рассмотрели целых 3 способа вычислить факториал в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂

Admin

Источник

Перейти к содержимому

Вычисление факториала на C++ можно провести с помощью циклов или рекурсии.

Стоит отметить, что так считают только факториалы небольших чисел. А для больших факториалов применяют более сложные подходы. Рассмотрим далее как расчёт факториалов с помощью циклов, так и с помощью рекурсии.

Вычисление факториала с помощью цикла for

Программа выглядит примерно так:

#include <iostream.h> // подключаем cin/cout

#include <conio.h> // подключаем getch

int main()

{

int n;

int i;

int res;

cin >> n;

res = 1;

for (i = 1; i <= n; i++) {

res = res * i;

}

cout << res;

getch();

}

В этой программе вначале подключаются заголовочные файлы iostream.h и conio.h. Затем объявляются переменные:

n — целое число, факториал, которого будет вычисляться;
i — счётчик;
res — переменная для хранения текущего результата.

Затем осуществляется ввод с помощью команды cin, это можно сделать и по-другому, например, с помощью scanf.

Далее текущему результату присваивается значение 1. И в цикле проводится n умножений.

После этого подсчитанный факториал выводится на экран с помощью команды cout. И ожидается нажатие пользователем клавиши (команда getch).

Вычисление факториала с помощью рекурсии

#include <iostream.h> // подключаем cin/cout

#include <conio.h> // подключаем getch

int factorial(int i)

{

if (i==0) return 1;

else return i*factorial(i—1);

}

int main()

{

int n;

int i;

int res;

cin >> n;

cout << factorial(n);

getch();

}

Здесь всё аналогично предыдущему случаю за исключением цикла for, которого нет. Вместо него рекурсивная функция factorial.

Эта функция всякий раз вызывает сама себя, уменьшая значение i на 1. А когда i становится равным нулю, функция завершает вычисления (используется оператор if).

Источник