Problem 57 - Project Euler
30分プログラム、その335。Problem 57 - Project Euler。
昨日(id:mzp:20080706:euler)の修正版。冷静に見直すと動的計画法がうまくできてなかった。それを直したら、再帰に関する例外も消えたし、速くもなった。
使い方
$ python problem57.py ... 951 956 964 972 977 985 990 998 answer: 153
ソースコード
#! /usr/bin/python # -*- mode:python; coding:utf-8 -*- # # problem57.py - # # Copyright(C) 2008 by mzp # Author: MIZUNO Hiroki / mzpppp at gmail dot com # http://howdyworld.org # # Timestamp: 2008/07/06 22:51:36 # # This program is free software; you can redistribute it and/or # modify it under MIT Lincence. # from math import log10 def gcd(n,m): if m == 0: return n else: return gcd(m,n % m) class Ratio(): def __init__(self,num,denom=1): n = gcd(num,denom) self.num = num/n self.denom = denom/n def __add__(self,other): return Ratio(self.num*other.denom+other.num*self.denom, self.denom * other.denom) def __div__(self,other): return Ratio(self.num*other.denom, self.denom*other.num) def __repr__(self): return "%s/%s" % (self.num,self.denom) memo = {} def makeFrac(n): if not (n in memo): if n == 0: memo[0] = Ratio(0) else: memo[n] = Ratio(1) / (Ratio(2,1)+makeFrac(n-1)) return memo[n] def makeNum(n): return Ratio(1)+makeFrac(n) def isSatisfy(r): return int(log10(r.num)) > int(log10(r.denom)) count = 0 for n in xrange(0,1001): if isSatisfy(makeNum(n)): count += 1 print n print "answer:",count