アッカーマン関数
一応残しておく.
$ python Python 2.6.2 (r262:71600, Jun 5 2009, 23:21:35) [GCC 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)] on cygwin Type "help", "copyright", "credits" or "license" for more information. >>> cache = {} >>> >>> def memoize(f): ... global cache ... def _(*args): ... if not args in cache: ... cache[args] = f(*args) ... return cache[args] ... return _ ... >>> @memoize ... def ack(m, n): ... if m == 0: ... return n + 1 ... elif m == 1: ... return n + 2 ... elif m == 2: ... return n * 2 + 3 ... elif m == 3: ... return 2 ** (n + 3) - 3 ... elif n == 0: ... return ack(m - 1, 1) ... else: ... if not (m, n - 1) in cache: ... for i in range(n): ... ack(m, i) ... return ack(m - 1, ack(m, n - 1)) ... >>> ack(4, 1) 65533 >>> len(str(ack(4, 2))) 19729