Язык Си в примерах/Факториал
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
- XCC C
Факториалом числа n называют произведение первых n натуральных чисел:
Ниже мы рассмотрим примеры программ, содержащих вычисляющую факториал заданного числа функцию 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 ("%d\n", factorial (n));
}
return 0;
}
Определение функции factorial
выше основано на следующей рекуррентной
формуле:
Для вычисления факториала 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 ("%Zd\n", 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 г.