Завдання № 29. Обчислити число сполучень із n по k » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 29. Обчислити число сполучень із n по k

Завдання № 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} - однакові поєднання, так як вони відрізняються тільки порядком проходження елементів.
Рішення. З комбінаторики відома формула:

 

Завдання № 29. Обчислити число сполучень із n по k

    Не цікавлячись питанням її виведення і коректності, ми будемо використовувати той її варіант, який написаний після другого знака рівності (якщо дивитися зліва направо), так як він наиб-леї оптимальний для обчислень і дозволить обійтися двома циклами (для чисельника 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.

 

Код:


  1. program NumOfCombinations;
  2. var
  3. i, n, k: byte;
  4. num, denom: integer;
  5. begin
  6. readln(n, k);
  7. num := 1;
  8. for i := n downto n – k + 1 do begin
  9. num := num * i
  10. end;
  11. denom := 1;
  12. for i := 1 to k do begin
  13. denom := denom * i
  14. end;
  15. writeln(num div denom)
  16. end.

0029.-NumOfCombinations.rar [689 b] (cкачувань: 2)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 30. Вивести таблицю квадрат... Попередня сторінка » Завдання № 28. Обчислити факторіал