Про комбінаторику, межі цілих типів і трикутник Паскаля

25 Лютого, 2015  

Цей приклад присвячено простій задачі про обчислення кількості сполук по k елементів із n без повторень, або біноміальних коефіцієнтів, як їх ще прийнято називати. Ця елементарна задача походить з комбінаторики, але знаходить своє застосування у різних розділах математики (і не тільки математики). З точки зору програмування цей приклад дозволяє продемонструвати межі допустимих значень даних цілого типу.

Створимо функцію для знаходження кількості сполук за відомою кожному школяру формулою n!/((n – k)! k!). Для знаходження факторіалів скористаємость циклами просто For всередині функції (хоча в таких випадках краще створювати окрему функію).

Function Combi_N_K(ByVal N As Integer,
ByVal K As Integer) As Long
Dim i As Integer
Dim f1 As Long
Dim f2 As Long
Dim f3 As Long
f1 = 1
For i = 1 To N
f1 = f1 * i
Next i
f2 = 1
For i = 1 To N – K
f2 = f2 * i
Next i
f3 = 1
For i = 1 To K
f3 = f3 * i
Next i
Combi_N_K = f1 / (f2 * f3)
End Function

Та процедуру для її тестування

Sub Test()
MsgBox Combi_N_K(12, 5)
End Sub

Для n = 12 k = 5 наша програма дає цілком правильний результат 792. результат

Але вже при n = 13 ми не зможемо порахувати кількості сполук для жодного k = 0, 1, …, 13. Причина тут зовсім не в “нещасливому числі 13”. Просто 13! = 6227020800, а межі допустимих значень для змінної f1 типу Long – від -2147483648 до 2147483647 (див. тут). Тому у функції Combi_N_K виникає помилка – переповненя змінної f1. Тобто, наша програма придатна для знаходження лише для

Цікавий спосіб уникнути переповнення можна знайти в самій комбінаториці – для знаходження можна можна скористатися рівністю яка лежить в основі простого правила обчислення біноміальних коефіцієнтів, відомого під назвою “трикутник Паскаля”. Щоправда, для програмної реалізації цього правила слід використати спеціальний прийом програмування – рекурсію, яка полягає у виклику функції самою себе. Наприклад, так:

Function Combi_N_K_Recursive(ByVal N As Integer, _
ByVal K As Integer) As Long
If N = K Or K = 0 Then
Combi_N_K_Recursive = 1
Else
Combi_N_K_Recursive = Combi_N_K_Recursive(N – 1, K) + _
Combi_N_K_Recursive(N – 1, K – 1)
End If
End Function

Для функції Combi_N_K_Recursive помилка з переповненням типу може виникнути лише тоді, коли за межі 2147483647 вийде саме значення , а це буде при достатньо великих значеннях n i k. На жаль, функція Combi_N_K_Recursive не зовсім позбавлена недоліків – рекурсія вимагає значних затрат часу. Так виконання процедури

Sub TestR()
MsgBox Combi_N_K_Recursive(30, 5)
End Sub

займе приблизно 15 секунд (більше, або менше, залежно від конфігурації ПК та ПЗ).