Разбор задачи B6 (демо ЕГЭ 2013)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * n, при n >1
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
F(1) = 1
F(n) = F(n–1) * n, при n >1
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Ответ: 120
Решение:
2 способ (быстрый, если разобраться)
Факториал вычисляется следующим образом (упрощенный вид):
Это задача на знание рекурсии.
1 способ
F(1) = 1
F(2) = F(1)*2
F(3) = F(2)*3
F(4) = F(3)*4
F(5) = F(4)*5=F(3)*4*5=F(2)*3*4*5=F(1)*2*3*4*5=1*2*3*4*5=24*5=120
2 способ (быстрый, если разобраться)
Функция F(n) - это факториал числа n, т.е. F(n)=n!
Рассмотрим, почему данный алгоритм описывает поиск факториала.
Рекурентная формула факториала имеет вид:
Подставляя вместо n! F(n) и учитывая, что мы начали с n=1, получим формулу:
Факториал вычисляется следующим образом (упрощенный вид):
n!=1*2*...*n.
Подставляя значение 5 вместо n, получим:
5!=1*2*3*4*5=120.