В мир информатики # 92 (16–31 мая).
Задачник
Две задачи
Л.М. Коганов,
Москва
1. Убывающий факториал
Вы, конечно, знаете, что в математике
называют факториалом числа — факториал
числа k равен произведению 1 • 2 • … • (k –1)
• k и обозначается k!.
А известно ли вам, что такое убывающий
факториал? Убывающим факториалом порядка n
числа a (обозначается (a)n) называется
произведение:
При n = 1: (a)n = a – 0 = a;
при n = 0: (a)n = 1 (по определению).
Задания для самостоятельной работы
1. Составьте программу на известном вам
языке программирования, которая вычисляла бы
убывающий факториал для заданных значений a и
n.
2. На листе электронной таблицы Microsoft
Excel в столбце D получите убывающие факториалы
числа 10 при n = 1, 2, …, 9:
2. Определение числа сочетаний с
использованием рекурсии
В статье [1] отмечалось, что число
возможных способов, которыми можно из n
элементов составлять группы по m элементов,
не обращая внимание на порядок элементов в
группе, называют “числом сочетаний из n
элементов по m”. Например, из набора четырех
элементов (n = 4): a, b, c и d группы
по два элемента (m = 2) можно сформировать
шестью способами:
1) a, b; 3) a, d; 5) b, d;
2) a, c; 4) b, c; 6) c, d
— группы b, a; c, a и т.п. не
учитываем.
Указывалось, что число сочетаний из n
элементов по m вычисляется по формуле:
Интересно, что для расчета значения  с
использованием компьютера не обязательно
использовать факториалы. Можно доказать, что = , т.е.
для определения может быть использована
рекурсия [2].
Задание для самостоятельной работы
Составьте программу на известном вам
языке программирования, которая вычисляла бы
число сочетаний из n элементов по m. Расчет
факториала в программе проводиться не должен.
Примечание. При m = 0: = 1 —
это так называемый “сингулярный случай” (от фр. singulier
— единичный, особый).
Литература
1. Крылов А.Г. Бином Ньютона,
треугольник Паскаля и… шары. / “В мир
информатики” № 60 (“Информатика” № 19/2005).
2. Рекурсия. / “В мир информатики” № 5
(“Информатика” № 37/2003). |