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

프로그래밍/Lua 2008. 3. 14. 12:21

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

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

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

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

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

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

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

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

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