Skyline algorithm for packing 2D rectangles – Julien Vernay を読んだ。
- 複数の長方形を大きな長方形に詰め込む問題(Packing)について
- オフラインでは MAXRECTS 、オンラインでは SKYLINE が良い
- この記事では SKYLINE について述べている
日: 2024年11月29日
中国の剰余定理のアルゴリズム(Algorithm.10.20)
概要
(Gathen and Gerhard 2013) を参考にして、中国の剰余定理のアルゴリズムを実装する。
実装 (Algorithm.10.20)
def alg10_20(cs, i_s, i_e, M, i_r0, j_r0): if i_e - i_s == 1: return cs[i_s] else: return M[i_r0][j_r0+1] * alg10_20(cs, i_s, i_s+(i_e-i_s)//2, M, i_r0-1, 2*j_r0) \ + M[i_r0][j_r0] * alg10_20(cs, i_s+(i_e-i_s)//2, i_e, M, i_r0-1, 2*j_r0+2)
ms = [2, 3, 5, 7, 11, 13, 17, 19] ms, r, k = pack_ms(ms) M = alg10_3(ms) cs = list(range(len(ms))) alg10_20(cs, 0, len(ms), M, -2, 0)
25524916