プロジェクトオイラー
http://projecteuler.net/
Q247.
y = 1 / xとx = 1とy = 0に囲まれた領域に、なるべく大きな正方形を書く。一つ書いたら、残りの領域にまたなるべく大きな正方形を書く。正方形には大きい順に1から番号を振る。また、その正方形の左と下にいくつ正方形があるかで添え字をつける。1の正方形は左と下に何もないので(0, 0)、2の正方形は左に1の正方形があるだけなので(1, 0)となる。(3, 3)となる正方形で最も番号が大きいのはいくつか。
この問題は易しい。
最初、素直に書いてみた。ある正方形の右と上に正方形を書く。番号は0としておく。番号が0のものの中で最も大きな正方形に番号をつける。その正方形の右と上に正方形を書く。こうしていけばいつか答えが求まるが、非常に時間がかかりそう。
そこで、まず(3, 3)の正方形を全て求めて最も小さい正方形をみつける。それよりも大きな正方形をすべて数える。大きな正方形はスタックにいれて、次々と発生させる。スタックが空になったら終わり。
from math import sqrtclass cSquare:
def __init__(self, x0, y0, i, j):
self.x0 = x0
self.y0 = y0
d = x0 - y0
self.length = (d + sqrt(d * d + 4)) / 2 - x0
self.ID = 0
self.i = i
self.j = j
def get_length(self):
return self.length
def make_children(self):
sq1 = cSquare(self.x0 + self.length, self.y0, self.i + 1, self.j)
sq2 = cSquare(self.x0, self.y0 + self.length, self.i, self.j + 1)
return (sq1, sq2)def get_min_length(sq0, i, j):
a = [ ]
def add(sq):
if sq.i <= i and sq.j <= j:
stk_squares.append(sq)
if sq.i == i and sq.j == j:
a.append(sq)
stk_squares = [ sq0 ]
while len(stk_squares):
sq = stk_squares.pop()
sq1, sq2 = sq.make_children()
add(sq1)
add(sq2)
return reduce(min, map(cSquare.get_length, a))def count_greater_squares(sq0, length):
counter = 0
stk_squares = [ sq0 ]
while len(stk_squares):
sq = stk_squares.pop()
counter += 1
sq1, sq2 = sq.make_children()
if sq1.length > length:
stk_squares.append(sq1)
if sq2.length > length:
stk_squares.append(sq2)
return counterimax, jmax = 3, 3
sq0 = cSquare(1.0, 0.0, 0, 0)
print count_greater_squares(sq0, get_min_length(sq0, imax, jmax)) + 1
