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

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

Створимо функцію для знаходження кількості сполук за відомою кожному школяру формулою Для знаходження факторіалів скористаємость циклами просто 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 NK
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(N1, K) + _
Combi_N_K_Recursive(N1, K1)
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 секунд (більше, або менше, залежно від конфігурації ПК та ПЗ).