Язык Си в примерах/Факториал: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Нет описания правки
Строка 69: Строка 69:
i для того, чтобы использовать в вычислениях натуральное число, которое с каждой итерацией цикла становится больше на единицу.<br>
i для того, чтобы использовать в вычислениях натуральное число, которое с каждой итерацией цикла становится больше на единицу.<br>
x содержит в себе промежуточный результат и он же выводится как конечный итоговый результат.
x содержит в себе промежуточный результат и он же выводится как конечный итоговый результат.
== Пример 3 ==

Вариант без рекурсии

<source lang="c">
#include <stdio.h>
int factorial(int x) {
int result=1;
for (;n>0;--n)
result *= n;
return result;
}
void main() {
int n;
while( scanf("%d", &n) == 1)
printf("%d\n", factorial (n));
}
</source>




== Задания ==
== Задания ==

Версия от 12:58, 8 июня 2011

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


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII-коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN-калькулятор
  18. RPN-калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX
  25. Другие примеры

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


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

#include <stdio.h>
int factorial(int x) { 
    if( x == 0 ) return 1;
    return x * factorial (x - 1);
}
void main() {
    int n;
    while( scanf("%d", &n) == 1)
      printf("%d\n", factorial (n));
}

Это определение основано на следующей рекуррентной формуле:


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

Если бы не было строчки

if( n == 0 ) return 1;

то функция factorial постоянно бы вызывала саму себя, и во время выполнения программы мы получили бы сообщение об ошибке «переполнение стека» или «превышена глубина рекурсии». Для того, чтобы этого не было, необходимо, чтобы при некоторых значения аргумента, функция не вызывала саму себя, а вычисляла свое значение «самостоятельно».

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

Пример 2

Можно ещё реализовать эту же задачу такой программой:

#include <stdio.h> 
main() 
{ 
 unsigned int n, i, x = 1; 

printf("n = "); 
 scanf("%i", &n); 

for (i = 1; i <= n; i++) x *= i; 
  printf("Result: %i", x); 

 return 0; 
}

Эта программа основана на последовательном умножении натуральных чисел пока не будет достигнуто число n.
Минус данной программы в том, что она использует дополнительные переменные i и x, которые необходимы для:
i для того, чтобы использовать в вычислениях натуральное число, которое с каждой итерацией цикла становится больше на единицу.
x содержит в себе промежуточный результат и он же выводится как конечный итоговый результат.

Пример 3

Вариант без рекурсии

#include <stdio.h>
int factorial(int x) { 
	int result=1;
	for (;n>0;--n)
		result *= n;
	return result;
}
void main() {
    int n;
    while( scanf("%d", &n) == 1)
      printf("%d\n", factorial (n));
}


Задания

  1. Улучшите программу, добавив к ней защиту от дурака: если n < 0, то программа должна по-прежнему адекватно работать, например, сообщать, что факториал для отрицательных чисел не определен, и не вызывать Runtime error — ошибку выполнения программы.

См. также