조립제법(Horner의 방법) 예제 for Ruby

프로그래밍/Ruby 2008. 3. 14. 11:49

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

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

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

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

아래의 소스파일은 Python용 소스파일 testSyntheticDivision.py 를 Ruby용으로 수정한 것이다.

ruby 대신 jruby 로도 수정 없이 그대로 실행된다.

=begin
Filename: testSyntheticDivision.rb
Purpose: Find the quotient and remainder when some polynomial is
divided by a monic polynomial of the first degree.
Execute: ruby testSyntheticDivision.rb -2 1 3 3 1
Or jruby testSyntheticDivision.rb -2 1 3 3 1
=end
# 사용법 표시
def printUsage()
print("사용법: ruby testSyntheticDivision.rb [수] [피제식의 계수들]" + "\n")
print("조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다." + "\n")
end
# 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
# 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
def simplify(v, width)
t = "%d" % v
tlen = t.length
if t[(tlen-2)..(tlen-1)] == ".0"
t = t[0..(tlen-2)]
end
if width != nil
if tlen < width
t = " "[0...(width - tlen)] + t
end
end
return t
end
# 다항식을 내림차순의 스트링 표현으로 반환
def toPolyString(c)
t = ""
sc0 = simplify(c[0], nil)
if c.length > 2
if sc0 == "1"
t += "x^%d" % (c.length-1)
elsif sc0 == "-1"
t += "-x^%d" % (c.length-1)
else
t += sc0 + " x^%d" % (c.length-1)
end
elsif c.length == 2
if sc0 == "1"
t += "x"
elsif sc0 == "-1"
t += "-x"
else
t += sc0 + " x"
end
elsif c.length == 1
t += sc0
end
for i in 1...c.length do
k = c.length - 1 - i
sc = simplify(c[i], nil)
if k > 1
if c[i] > 0.0
if sc == "1"
t += " + " + "x^" + k
else
t += " + " + sc + " x^%d" % k
end
elsif c[i] < 0.0
if sc == "-1"
t += " - " + "x^" + k
else
t += " - " + simplify(c[i].abs, nil) + " x^%d" % k
end
end
elsif k == 1
if c[i] > 0.0
if sc == "1"
t += " + " + "x"
else
t += " + " + sc + " x"
end
elsif c[i] < 0.0
if sc == "-1"
t += " - " + "x"
else
t += " - " + simplify(c[i].abs, nil) + " x"
end
end
elsif k == 0
if c[i] > 0.0
t += " + " + sc
elsif c[i] < 0.0
t += " - " + simplify(c[i].abs, nil)
end
end
end
return t
end
# 다향식 나눗셈 결과를
# (피제식) = (제식)(몫) + (나마지)
# 형태로 출력
def printDivisionResult(a, c, b)
strLine = " " + toPolyString(c)
print( strLine + "\n")
strLine = " = ( " + toPolyString( [1.0, -a] ) + " )"
tmp = [0.0] * (b.length - 1)
for i in 0...tmp.length do
tmp[i] = b[i]
end
strLine += "( " + toPolyString(tmp) + " )"
r = b[b.length - 1]
if r > 0.0
strLine += " + " + simplify(r, nil)
elsif r < 0.0
strLine += " - " + simplify(r.abs, nil)
end
print( strLine + "\n" )
end
# 조립제법 계산표 출력 함수
def printSyntheticTable(a, c, s, q)
strLine = " | "
strLine += simplify(c[0], 6)
for i in 1...c.length do
strLine += " " + simplify(c[i], 6)
end
print( strLine + "\n" )
strLine = simplify(a, 6) + " |"
strLine += " "
strLine += simplify(s[1], 6)
for i in 2...s.length do
strLine += " " + simplify(s[i], 6)
end
print( strLine + "\n" )
strLine = " |"
for i in 0...q.length do
strLine += "--------"
end
print( strLine + "\n" )
strLine = " "
strLine += simplify(q[0], 6)
for i in 1...q.length do
strLine += " " + simplify(q[i], 6)
end
print( strLine + "\n" )
end
# 실행 시작 지점
if ARGV.length < 2
printUsage()
exit(1)
end
######################################################
# 피제식은 c_0 x^n + c_1 x^(n -1) + ... + c_n
# 제식은 x - a
a = ARGV[0].to_f
c = [0.0]*(ARGV.length - 1)
s = [0.0]*(+ARGV.length - 1)
b = [0.0]*(ARGV.length - 1)
for i in 0...c.length do
c[i] = ARGV[i + 1].to_f
end
######################################################
# 조립제법의 주요 부분
s[0] = 0.0
b[0] = c[0]
for i in 1...c.length do
s[i] = b[i-1]*a
b[i] = c[i] + s[i]
end
######################################################
# 몫의 계수와 나머지를 출력한다.
print("몫의 계수는 ")
for i in 0...(b.length - 2) do
print(simplify(b[i], nil) + ", " )
end
print(simplify(b[b.length - 2], nil) + " ")
print("이고, 나머지는 " + simplify(b[b.length - 1], nil) + " 이다." + "\n")
print("\n")
######################################################
# 조립제법 표를 출력한다.
printSyntheticTable(a, c, s, b)
print("\n")
######################################################
# (피제식) = (제식) x (몫) + (나머지)
printDivisionResult(a, c, b)

실행> ruby testSyntheticDivision.rb 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 대한민국 라이센스에 따라 이용하실 수 있습니다.

'프로그래밍 > Ruby' 카테고리의 다른 글

황금비율(golden ratio) 구하기 with Ruby or JRuby (0)	2008.03.24
현재 시각 알아내기 for Ruby and JRuby (0)	2008.03.24
80컬럼 컨솔에 19단표 출력하기 예제 for Ruby (0)	2008.03.03
(최대공약수 구하기) while... 반복문 예제 for Ruby (0)	2008.02.21
if...else... 조건문 사용 예제 for Ruby (0)	2008.02.19