Паскаль треугольник дает переполнение на 13

Question

Я написал код для вывода треугольника Паскаля в многострочном учебнике. Программа отлично работает для входов от 1 до 12, но выдает ошибку переполнения после ввода значения 13.

Могу ли я внести какие-либо изменения, чтобы программа точно выдавала результаты для 13 и выше?

Вот код, который я использовал:

Public Class pascal_triangle

    Private Function factorial(ByVal k As Integer) As Integer
        If k = 0 Or k = 1 Then
            Return 1
        Else
            Return k * factorial(k - 1)
        End If
    End Function


    Private Sub BtnGen_Click(sender As Object, e As EventArgs) Handles BtnGen.Click
        Dim nCr As Integer
        Dim i, j, k As Integer
        Dim output As String

        output = ""

        j = Val(TxtColumn.Text)

        For k = 0 To j
            For i = 0 To k
                Dim fact, fact1, fact2 As Integer

                fact = factorial(k)
                fact1 = factorial(k - i)
                fact2 = factorial(i)
                nCr = fact / (fact1 * fact2)
                TxtOutput.Text += Str(nCr) & output
            Next
            TxtOutput.Text += vbCrLf
        Next
    End Sub

End Class

Answer 1

Переполнение происходит потому, что 13! слишком большой, чтобы поместиться в целое число.

Самый большой представительный integer (32-разрядная подпись)

• 2147483647 (0x7FFFFFFF == 01111111 11111111 11111111 11111111b)

так:

 12!    =  479001600  
 MaxInt = 2147483647
 13!    = 6227020800    

Если вы хотите использовать большее число, чем это, вам нужно использовать больший тип номера. Следующие более крупные типы Long (64-разрядная подпись, макс. 9223372036854775807) или, для ваших целей, ULong (без знака 64-битный, так как вам не нужны отрицательные числа, что вдвое больше, чем в 18446744073709551615).

Это позволит вам рассчитать до 20!, который 2432902008176640000, Для чисел, больших, чем это, вам нужно использовать BigIntegerили другие специализированные библиотеки, которые позволяют хранить и рассчитывать произвольно большие числа.

Кроме того, вы можете посмотреть на другие методы вычисления произвольной строки без использования факториалов.

Answer 2

Ваша главная проблема в том, что вы используете Integer который слишком мал, чтобы содержать факториал 13. Измените функцию факториала, чтобы она возвращалась Long, Также было бы неплохо включить Option Strict On и сделать nCr Double,

Private Function factorial(ByVal k As Integer) As Long
    If k = 0 Or k = 1 Then
        Return 1
    Else
        Return k * factorial(k - 1)
    End If
End Function

Private Sub BtnGen_Click(sender As Object, e As EventArgs) Handles BtnGen.Click
    Dim nCr As Double
    Dim i, j, k As Integer
    Integer.TryParse(TxtColumn.Text, j)
    For k = 0 To j
        For i = 0 To k
            Dim fact, fact1, fact2 As Long
            fact = factorial(k)
            fact1 = factorial(k - i)
            fact2 = factorial(i)
            nCr = fact / (fact1 * fact2)
            TxtOutput.Text += nCr.ToString & " "
        Next
        TxtOutput.Text += vbCrLf
    Next
End Sub