[Algospot] 이분법 / ROOTS / Python 파이썬

 

[종만북] 이분법 / ROOTS / Python 파이썬

https://www.algospot.com/judge/problem/read/ROOTS

algospot.com :: 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])))

※ 수학을 못해서 몇일동안 고생하였다...