#/***********************************************************
#    spline.rb -- スプライン補間
#***********************************************************/
# 非周期関数用 

N = 5
x = [ 0, 10, 20, 30, 40 ]
y = [ 610.66, 1227.4, 2338.1, 4244.9, 7381.2 ]
z = []

def maketable( x,  y,  z)
    h = []; d = []

    z[0] = 0;  z[N - 1] = 0;  # 両端点での y''(x) / 6 
    for i in 0...(N - 1)
        h[i    ] =  x[i + 1] - x[i]
        d[i + 1] = (y[i + 1] - y[i]) / h[i].to_f
    end
    z[1] = d[2] - d[1] - h[0] * z[0]
    d[1] = 2 * (x[2] - x[0])
    for i in 1...(N - 2)
        t = h[i] / d[i].to_f
        z[i + 1] = d[i + 2] - d[i + 1] - z[i] * t
        d[i + 1] = 2 * (x[i + 2] - x[i]) - h[i] * t
    end
    z[N - 2] -= h[N - 2] * z[N - 1]
    (N - 2).downto(1) do |i|
        z[i] = (z[i] - h[i] * z[i + 1]) / d[i].to_f
    end
end

def spline( t,  x,  y,  z)
    i = 0;  j = N - 1
    while (i < j) 
        k = (i + j) / 2
        if (x[k] < t); i = k + 1; else; j = k; end
    end
    if (i > 0); i -= 1; end
    h = x[i + 1] - x[i];  d = t - x[i]
    return (((z[i + 1] - z[i]) * d / h.to_f + z[i] * 3) * d\
        + ((y[i + 1] - y[i]) / h.to_f\
        - (z[i] * 2 + z[i + 1]) * h)) * d + y[i]
end

maketable(x, y, z)
for i in 10..30
    printf("%3d %6.1f\n", i, spline(i, x, y, z))
end

exit 0