Задача № 28. Вычислить факториал
Формулировка. Дано натуральное число n (которое также может быть равно нулю). Вычислить n!
Примечание: n! (факториал числа n, читается «эн факториал») – произведение всех натуральных чисел до n включительно.
Решение. Задача очень просто решается через цикл for по всем i от 1 до n, в теле которого мы на каждом шаге домножаем переменную-результат fact (которой до входа в цикл присвоено значение 1) на i. При этом сохраняется и правило 0! = 1, так как при вводе нуля программа не войдет в цикл и на выход пойдет неизмененное в переменной fact число 1.
Код:
| 1. program Factorial; 2. 3. var 4. i, n: byte; 5. fact: integer; 6. 7. begin 8. readln(n); 9. fact := 1; 10. for i := 1 to n do begin 11. fact := fact * i 12. end; 13. writeln(fact) 14. end. |
Примечание: для накопления результата мы использовали переменную fact типа integer. Как уже говорилось, этот тип охватывает диапазон целых чисел от –2147483648 до 2147483647 (Borland Delphi 7 и PascalABC). Данная переменная позволит сформировать результаты вплоть до 12! (= 479001600) включительно.
Задача № 29. Вычислить число сочетаний из n по k
Формулировка. Даны натуральные числа n и k (k не превышает n). Вычислить число сочетаний из n по k.
Примечание: в комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов; при этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми. Обозначение числа сочетаний из n по k элементов: 
. При этом считается, что 
, 
и 
для любого натурального n.
|
|
|
Например, найдем все 2-элементные сочетания 3-элементного множества {1, 2, 3}. Таковыми являются {1, 2}, {1, 3} и {2, 3}. То есть, таковых сочетаний 3. При этом, например, {1, 2} и {2, 1} – одинаковые сочетания, так как они отличаются только порядком следования элементов.
Решение. Из комбинаторики известна формула:
Не интересуясь вопросом ее вывода и корректности, мы будем использовать тот ее вариант, который написан после второго знака равенства (если смотреть слева направо), так как он наиболее оптимален для вычислений и позволит обойтись двумя циклами (для числителя for с downto, для знаменателя – просто for). Для числителя и знаменателя предусмотрим соответственно переменные num (от англ. numerator – «числитель») и denom (от англ. denominator – «знаменатель»), которым нужно поначалу присвоить значения 1, чтобы осуществить контроль частных случаев (этот вопрос упомянут в предыдущей задаче):
1) При k = 0 переменная num останется неизменной и будет равна 1, так как невозможен вход в цикл с уменьшением от n до ( n + 1), переменная denom будет равна 1 как 0!;
2) При n = k num и denom будут вычислены и при делении дадут единицу;
3) При n = k = 0 переменная denom будет вычислена как 0!, а переменная num не изменится по невозможности входа в цикл с уменьшением от 0 до 1.
|
|
|
Код:
Дата добавления: 2018-10-25; просмотров: 692; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!