Algorithm PS/Algospot
[Algospot] 이분법 / ROOTS / Python 파이썬
migrationArc
2021. 8. 30. 21:47
https://www.algospot.com/judge/problem/read/ROOTS
풀이
최대 5차 방정식의 해를 이분법을 이용하여 근사하는 문제이다.
이분법의 구간은 최소 -10, 주어진 방정식 그래프의 변곡점, 최대 10 으로 두고 이분법을 실행하여야 한다.
변곡점은 주어진 방정식을 미분한 식의 해 이므로, 해를 근사 할 수 있는 1차방정식까지 연속하여 미분하고 이를 이용하여 해를 구하는 방법으로 풀이하였다.
C = int(input())
# 근사하여 x 의 해 찾기
def findZero(lo, hi, diff, N):
lo_sol = 0
for j in range(N+1):
lo_sol += diff[j] * (lo ** (N-j))
hi_sol = 0
for j in range(N+1):
hi_sol += diff[j] * (hi ** (N-j))
if hi_sol < lo_sol:
hi, lo = lo, hi
half = (hi+lo) / 2
for i in range(100):
sol = 0
for j in range(N+1):
sol += diff[j] * (half ** (N-j))
if -1 * 10**(-11) <= round(sol, 10) <= 10**(-11):
return half
if sol > 0:
hi = half
half = (hi+lo) / 2
else:
lo = half
half = (hi+lo) / 2
def DFS(N, diff):
if N == 1:
return [-10, (-1*diff[1]) / diff[0], 10]
n = N-1
n_diff = []
# 미분
for i in range(N, 0, -1):
n_diff.append(i * diff[N-i])
section = DFS(n, n_diff)
# 최소 -10
res = [-10]
for i in range(N):
lo = section[i]
hi = section[i+1]
# 미분한 방정식의 해
res.append(findZero(lo, hi, diff, N))
# 최대 10
res.append(10)
return res
for _ in range(C):
N = int(input())
origin = list(map(float, input().split()))
res = DFS(N, origin)
# -10, 10 제외한 결과
print(" ".join(map(str, res[1:-1])))
※ 수학을 못해서 몇일동안 고생하였다...