조립제법(Horner의 방법) 예제 for Visual Basic

다항식 p(x) 를 1차 다항식 x - a 로 나눌 때의 몫과 나머지를 구하는 조립제법을
Visual Basic 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.

         p(x) = (x - a)q(x) + r

여기서 r은 나머지이며 r = p(a) 이다. 또 q(x)는 몫이다.

[참고]
    * 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표 
    * 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수

' ---------------------------------------------------------
'  Filename: TestSyntheticMethod.bas
'
'  Purpose:  Find the quotient and remainder when some polynomial is
'            divided by a monic polynomial of the first degree.
'
'  Compile: vbc TestSyntheticMethod.bas
'
'  Execute: TestSyntheticMethod -2 1 3 3 1
' ---------------------------------------------------------

Imports System

Public Class SyntheticMethod

        ' 사용법 표시
        Shared Sub PrintUsage()
             Console.WriteLine("사용법: TestSyntheticMethod [수] [피제식의 계수들]")
             Console.WriteLine("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.")
        End Sub

        ' 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
        Shared Function Simplify0(v As Double) As String
            Dim t As String = "" & v
            If t.EndsWith(".0") Then
                t = Mid(t, 0, Len(t) - 2)
            End If
            Simplify0 = t
        End Function

        ' 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
        ' 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
        Shared Function Simplify(v As Double, width As Integer) As String
            Dim t As String = "" & v
            If t.EndsWith(".0") Then
                t = Mid(t, 1, t.Length - 2)
            End If
            Dim len As Integer = t.Length
            if (len < width)
                t = Mid("               ", 1, width - len) & t
            End If
            Simplify = t
        End Function

        ' 다항식을 내림차순의 스트링 표현으로 반환
        Shared Function ToPolyString(ByVal c() As Double) As String
            Dim t As String = ""
            Dim i As Integer
            If c.Length > 2 Then
                If Simplify0(c(0)) = "1" Then
                    t = t & "x^" & (c.Length-1)
                ElseIf Simplify0(c(0)) = "-1" Then
                    t = t & "-x^" & (c.Length-1)
                Else
                    t = t & Simplify0(c(0)) & " x^" & (c.Length-1)
                End If
            ElseIf c.Length = 2 Then
                If Simplify0(c(0)) = "1" Then
                    t = t & "x"
                ElseIf Simplify0(c(0)) = "-1" Then
                    t = t & "-x"
                Else
                    t = t & Simplify0(c(0)) + " x"
                End If
            ElseIf c.Length = 1 Then
                t = t & Simplify0(c(0))
            End If

            For i = 1 To c.Length - 1
                If c.Length - 1 - i > 1 Then
                    If c(i) > 0.0 Then
                        If Simplify0(c(i)) = "1" Then
                            t = t & " + " & "x^" & (c.Length - 2 - i)
                        Else
                            t = t & " + " & Simplify0(c(i)) & " x^" & (c.Length - 2 - i)
                        End If
                    ElseIf c(i) < 0.0 Then
                        If Simplify0(c(i)) = "-1" Then
                            t = t & " - " & "x^" & (c.Length - 2 - i)
                        Else
                            t = t & " - " & Simplify0(Math.Abs(c(i))) & " x^" & (c.Length - 2 - i)
                        End If
                    End If
                ElseIf c.Length - 1 - i = 1 Then
                    If c(i) > 0.0 Then
                        If Simplify0((i)) = "1" Then
                            t = t &  " + " & Simplify0(c(i)) & "x"
                        Else
                            t = t &  " + " & Simplify0(c(i)) & " x"
                        End If
                    ElseIf c(i) < 0.0 Then
                        If Simplify0(c(i)) = "-1" Then
                            t = t &  " - " & "x"
                        Else
                            t = t &  " - " & Simplify0(Math.Abs(c(i))) & " x"
                        End If
                    End If
                ElseIf c.Length - 1 - i = 0 Then
                    If c(i) > 0.0 Then
                        t = t & " + " & Simplify0(c(i))
                    ElseIf c(i) < 0.0 Then
                        t = t & " - " & Simplify0(Math.Abs(c(i)))
                    End If
                End If
            Next
            ToPolyString = t
        End Function

        ' 다항식 나눗셈 결과를
        '     (피제식) = (제식)(몫) + (나마지)
        ' 형태로 출력
        Shared Sub PrintDivisionResult(a As Double, c() As Double, b() As Double)

            Console.WriteLine("  " & ToPolyString(c))
            Console.WriteLine()
            Console.Write("    = ( " & ToPolyString( New Double() {1.0, -a} ) & " )")

            Dim tmp(b.Length -  2) As Double
            For i = 0 To tmp.Length - 1
                tmp(i) = b(i)
            Next
            Console.Write("( " & ToPolyString(tmp) & " )")

            Dim r As Double = b(b.Length - 1)
            If r > 0.0 Then
                Console.Write(" + " & Simplify0(r))
            ElseIf r < 0.0 Then
                Console.Write(" - " & Simplify0(Math.Abs(r)))
            End If

            Console.WriteLine()
        End Sub

        ' 조립제법 계산표 출력 메쏘드
        Shared Sub PrintSyntheticTable(a As Double, c() As Double, s() As Double, q() As Double)
            Console.Write("       | ")
            Console.Write(Simplify(c(0), 6))
            For i = 1 To c.Length - 1
                Console.Write("  " & Simplify(c(i), 6))
            Next
            Console.WriteLine()

            Console.Write(Simplify(a, 6) & " | ")
            Console.Write("        ")
            Console.Write(Simplify(s(1), 6))
            For i = 2 To s.Length - 1
                Console.Write("  " & Simplify(s(i), 6))
            Next
            Console.WriteLine()

            Console.Write("       |-")
            For i = 0 To q.Length - 1
                Console.Write("--------")
            Next
            Console.WriteLine("")

            Console.Write("         ")
            Console.Write(Simplify(q(0), 6))
            For i = 1 To q.Length - 1
                Console.Write("  " & Simplify(q(i), 6))
            Next
            Console.WriteLine()
        End Sub

        ' Java 언어의 main 메소드에 해당하는 Visual Basic 언어의 Main
        Shared Sub Main(ByVal args As String())
            If args.Length < 3 Then
                PrintUsage()
                Return
            End If

            ' ----------------------------------------------------
            '  피제식은 c_0 x^n +  c_1 x^(n -1) + &. + c_n
            '  제식은 x -  a
            Dim a As Double = Convert.ToDouble(args(0))
            Dim c(args.Length-2) As Double
            Dim s(args.Length-2) As Double
            Dim b(args.Length-2) As Double
            For i = 0 To c.Length - 1
                c(i) = Convert.ToDouble(args(i+1))
            Next

            ' ----------------------------------------------------
            ' 조립제법의 주요 부분
            s(0) = 0.0
            b(0) = c(0)
            For i = 1 To c.Length - 1
                s(i) = b(i-1)*a
                b(i) = c(i) + s(i)
            Next i

            ' -----------------------------------------
            ' 몫의 계수와 나머지를 출력한다.
            Console.Write("몫의 계수는 ")
            For i = 0 To b.Length - 3
                 Console.Write(Simplify0(b(i)) & ", " )
            Next
            Console.Write(Simplify0(b(b.Length - 2)))
            Console.WriteLine(" 이고, 나머지는 " & Simplify0(b(b.Length - 1)) & " 이다.")
            Console.WriteLine()

            ' -----------------------------------------
            ' 조립제법 표를 출력한다.
            PrintSyntheticTable(a, c, s, b)
            Console.WriteLine()

            ' -----------------------------------------
            ' (피제식) = (제식) x (몫) + (나머지)
            PrintDivisionResult(a, c, b)
       End Sub
End Class

컴파일> vbc TestSyntheticMethod.bass
실행> TestSyntheticMethod 1 2 3 4 5
몫의 계수는 2, 5, 9 이고, 나머지는 14 이다.

       |      2       3       4       5
     1 |              2       5       9
       |---------------------------------
              2       5       9      14

  2 x^3 + 3 x^2 + 4 x + 5
    = ( x - 1 )( 2 x^2 + 5 x + 9 ) + 14

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.