Главная » Реализация известных алгоритмов на языке программирования Python

Вычисление факториала на языке программирования Python

Опубликовано plustilino в Январь 10, 2010 - 13:46. Changed Январь 3, 2011 - 18:43

Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1*2*3*4*5 = 120. Формулу нахождения факториала можно записать следующим образом: n! = 1 * 2 * … * n, где n – это число, а n! – факториал этого числа.
Можно записать немного по-другому: n! = 1 * … * (n-2) * (n-1) * n, т.е. каждое предыдущее число меньше на единицу, чем последующее. Нахождение факториала числа по первой формуле можно реализовать с помощью цикла while, а по второй формуле – с помощью рекурсии.

Исходный код на Python с использованием цикла

n = input("Факториал числа ") 
n = int(n) 
fac = 1 
i = 0 
while i < n:
     i += 1
     fac = fac * i 
print ("равен",fac)

Предположим, что в переменная n была связана с числом 5. Т.е. надо найти 5!.

Первых проход по телу цикла while свяжет переменную fac с произведением 1 * 1. Второй - 1 * 2, затем 2 * 3, 6 * 4, 24 * 5. Шестой раз цикл while выполняться не будет, т.к. значение переменной i будет равно 5 и выражение i < n вернет false.

Исходный код на Python с использованием рекурсии

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

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.
#1Опубликовано Гость в Ноябрь 1, 2011 - 14:24.

Лучше бы показали простой

Лучше бы показали простой пример рисования фрактала с использованием рекурсии, а то таких примеров, как у вас, в интернете навалом.
#2Опубликовано Гость в Октябрь 30, 2011 - 23:41.

Исходный код на Python с использованием рекурсии

Извините, пожалуйста, за глупый вопрос.
Объясните пожалуйста, как получаются и от куда берутся значения, при вычисление факториала, при помощи рекурсии.

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

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.
#3Опубликовано plustilino в Октябрь 31, 2011 - 13:32.

Когда n равна 1, то выражение

Когда n равна 1, то выражение fac(n-1) * n возвращает fac(0) * 1.

В свою очередь fac(0) возращает 1 (выполняется ветка if). Получается, что после этого происходит выход из функции и до второго return дело не доходит, иначе он должн быть обернут в ветку else.

Поскольку fac(0) = 1, то fac(0) * 1 = 1.
#4Опубликовано Гость в Ноябрь 1, 2011 - 00:25.

Исходный код на Python с использованием рекурсии

спасибо большое, не думал, что ответит кто нибудь.