カテゴリー別アーカイブ: CodeIQ

CodeIQの問題と解説

[解説]「再帰関数で逆順並べ替え」

問題文

再帰関数で逆順並べ替え
基本関数だけで逆順アルゴリズムを実現してみよう!
今回の問題は基本的な関数のみを使って、リスト項目を逆順にするアルゴリズムを考えてみます。

問題
4つの関数car, cdr, cons, nullpのみを使って、リストの項目を逆順にする関数reverse_auxとreverse2をつくってください。

例えば、reverse2は['A','B','C','D']を、逆順の['D','C','B','A']に並べ替えます。

reverse2()は1変数、reverse_aux()は2変数のリストを取ります。
最終的には、reverse2が必要なのですが、その前段階としてreverse_auxを作ってください。


reverse_aux(x, y)の性質は以下の通りです。

reverse_auxは、リストx, yを取ります。
例えば、

reverse_aux( [‘A’, ‘B’, ‘C’, ‘D’], [‘E’, ‘F’, ‘G’] )

= [‘D’, ‘C’, ‘B’, ‘A’, ‘E’, ‘F’, ‘G’]

 のように、リストxを逆順にして、リストyはそのままで連結します。 まず、reverse_auxを作ってください。 
●基本関数 使って良い関数はcar, cdr, cons, nullpのみです。
・carは先頭の項目を返す関数です。
例えば、

car([‘A’, ‘B’, ‘C’]) = ‘A’

・cdrは先頭項目を除いたリストを返す関数です。   例えば、

cdr([‘A’, ‘B’, ‘C’]) = [‘B’, ‘C’]

 ・consは一つの項目とリストを引数する関数です。consは項目xをリストyの最初に付け足したリストを返す関数です。
例えば、

cons(‘X’, [‘A’, ‘B’, ‘C’]) = [‘X’, ‘A’, ‘B’, ‘C’]

 ・nullp()は1変数の関数で、true <- nullp([]) となり、それ以外の時(アトムあるいは有限要素数のリストの場合)はfalseを返します。
reverse_auxを定義する前に、予め自分の処理系でcar, cdr, cons, nullpを定義してください。 その時は、どんな組み込み関数を使っても構いませんが、reverse_auxだけは、上記の基本関数のみを使ってください。ただし、ifなどの条件文やreturnなどはOKです。
最後に、reverse_auxを使って、reverse2を作ってください。 名前がreverse2なのは、built-in関数との競合を防ぐためです。問題なければ、reverseでも結構です。 作成したコードは、ファイル名を reverse.txt として、アップロードしてください。

その他注意事項 今回の問題は、純LISP に関する問題です。 LISPで解くと簡単にできますが、他の言語処理系だと基本関数定義の所で手間取るかもしれません。 結構大変かと思いますが、頑張ってください。 言語はPythonを希望しますが、解答の論理構造がわかるものであれば、どの言語処理系でも解答可能です。

解説

今回は純LISPに関する問題です。純LISPとはatom, eq, car, cdr, consとう5つの基本関数でプログラミング言語です。実際には、cond, quote, lambda, defineという関数も必要となりますが、必要最小限のもので、プログラミング言語を作ることができるというのは非常に面白い考えだと思います。まるで、数学の有限の公理で色々な証明を行うのに似ています。

Pythonでの解答例


#!/usr/bin/python

#
# reverse.py
#

def car(x): return x[0]

def cdr(x): return x[1:]

def cons(x, y): return [x] + y

def nullp(x): return len(x) == 0

def reverse_aux(x, y):

print x, y # Show variables
if nullp(x):
return y
else:
return reverse_aux(cdr(x), cons(car(x), y))

def reverse2(x):

return reverse_aux(x, [])

####
print reverse_aux([‘A’,’B’,’C’,’D’], [‘E’,’F’,’G’])


reverse_aux(X, Y) の解説をします。

diagram

X=[‘A’,’B’,’C’,’D’], Y=[‘E’,’F’,’G’] とすると、cdr(X)=[‘B,’C’,’D’]を次のreverse_auxのX’に引き継ぎます。更に、car(X)=’A’とY=[‘E’,’F’,’G’] をcons()で結合したものを次のreverse_auxのY’に引き継ぎます。処理がreverse_auxで再帰的に行われ、X部分の要素が逆順になります。

うまく、再帰関数で定義できたでしょうか。再帰関数を使うと、whileやfor文などを使わずに、繰返し処理が表現できますね。

[問題解説12] 男性と女性の殺人被害者数の関係は?

かなり遅くなってしまいましたが、「男性と女性の殺人被害者数の関係は?」の問題解説をします。

今回の問題は、前回の問題「ヒストグラムと散布図を描いてみよう」の発展問題です。

データとプログラムは下記のGitHubリポジトリーにおいてあります。

問題

世界各国の殺人被害者データを用いて女性被害者数から男性被害者数を予測してみましょう。

UNODC(United Nations Office on Drugs and Crime : 国連薬物犯罪事務所)から公開されている世界176ヶ国の殺人被害者の男女別のデータがあります。女性被害者数から男性被害者数を予測してみましょう。

homicide_log.zipをダウンロードしてください。解凍して、homicide_log.csvを読み込んでください。
男性・女性の殺人被害者数のデータは10を底とする対数化してあります。
元データは下記のページから入手しました。
Global Study on Homicide(殺人に関するグローバル調査)

■課題

1.回帰分析を行ってください。

Rの回帰分析関数 lm() を使用して予測式を求める計算をしてください。

2.予測式の値を答えてください。

男性被害者数をM、女性被害者数をFとすると、以下の予測式が成り立ちます。
M = a * F + b
a, b を小数点3桁まで答えてください。解答方法はプログラムの最終行に以下のように記述してください。
# a = x.xxx
# b = y.yyy
3.散布図を作成し、予測式の直線を表示してください。 X軸は女性被害者、Y軸は男性被害者。2Dの散布図を作成してください。表示範囲はX軸、Y軸ともに[-1,3]とする。 その散布図に重ねて、予測式の直線を青色で表示してください。

■解答方法 R言語のプログラムを作成し、上記1~3の課題に答えてください。プログラムファイル名は predict.txt として、アップロードしてください。 散布図は predict.pdf というファイル名でPDFとして出力するプログラムにしてください。

[問題解説12] 男性と女性の殺人被害者数の関係は? の続きを読む

設問4:コマンドを定期的に自動実行させよう!

CodeIQに投稿した設問4の解答を説明します。

問題

cron でユーザーのディスク使用量管理

管理しているサーバーの全ユーザーのディスク使用状況を知りたいと思い、毎日定時にディスク使用量をログを取ることにしました。

UNIX のcron 機能 を使って、定期的に各ユーザーのディスク使用量の情報を取得する設定をしてください。

詳細は以下の通りです。

・/home の下にある全ユーザーのディレクトリ内の使用量をdu を使って求めてください。

・毎日23:30に情報を取得してください。

・ファイルは、/var/lib/bak に保存し、名前はdu-YYYYMMDD.log のようにしてください。

 例えば、2013年4月31日ならば、/var/lib/bak/du-20130431.log となります。

 日付の生成にはdateコマンドを使ってください。

・crontab -e で編集し、設定は crontab -e 内の一行のみで実現させてください。

 他のスクリプトファイルを読みに行くようなことはしないでください。

・使用するシェルはbashです。

【解答方法】

crontab -l の表示結果をテキストファイルに貼り付けて、そのテキストファイルをアップロードしてください。

解答

問題のプログラムのポイントは以下の3点です。

1. cronによるコマンド自動実行の理解

2. du, dateのオプションの理解

3. シェルのコマンド展開機能の理解

解答例

30 23 * * * du -s /home/* > /var/lib/bak/du-`date +"\%Y\%m\%d"`.log

dateコマンドの展開部分が難しいです。

bashスクリプト実行では、`date +”%Y%m%d”`でコマンドの展開がうまく行きますが、cronの中ではフォーマットの%\でエスケープしないと正常に動作しないです。

下記のURLも参考にしてください。

http://maruta.be/intfloat_staff/67

/var/libは管理者権限があり、実際のコマンド実行には、/var/lib/bakにユーザーの書き込み権限を与える必要があります。

設問5:PythonでXML解析をしてみよう

CodeIQの設問5について解答します。

問題

日本人の同姓同名データのファイルをXMLパーサのElementTreeを使ってパースしてみよう。

更に、姓と名の漢字の組み合わせを集計してみます。

課題

person_name.xmlファイルを読み込み、PythonのXMLパーサモジュールElementTreeを使って苗字、名前、同姓同名の数を抜き出して、標準出力で表示してください。

同姓同名のファイルを下記からダウンロードしてください。

下記zipファイルを解凍するとperson_name.xmlが入っています。

person_name.zip

※このファイルは「同姓同名辞典」の全国ランキング1位から20000位までのHTMLファイルを修正したものです。

http://www.douseidoumei.net/00/dou01.html

ElementTreeについては以下を参照。

http://d.hatena.ne.jp/hikm/20090206/1233950923

出力するもの

・文字列の両端にある不要な空白は除いてください。

・文字コードはUTF-8にしてください。(難しければ、他の文字コードでも可です)

・ファイル形式はヘッダを一行にして、コンマ区切りで以下のようにしてください。

順位,姓,名,件数

1,田中,実,2620

2,鈴木,茂,2470

課題の提出はプログラムのみです。

完成したら、テキストファイル(.txt)に変換し、ファイルアップロードにて提出してください。

 

解答

問題のプログラムのポイントは以下の3点です。

1. XMLの理解

2. xml.etree.ElementTree

3. 漢字コードの扱い

解答例

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
#                               element.py
#
from xml.etree import ElementTree
def main(i_file, o_file):
o_handle = open(o_file, 'w')
tree = ElementTree.parse(i_file)
elem = tree.getroot()
for tr in list(elem):
td = list(tr)
w = ''
w += '%s,' % td[0].text.encode('utf-8').strip()
w += '%s,' % ','.join(td[1].text.encode('utf-8').strip().split(" "))
w += '%s' % td[2].text.encode('utf-8').strip()
o_handle.write('%s\n' % w)
##############################################################
main('person_name.xml', 'personal_name.txt')

設問6の解説:アッカーマンの呪い

CodeIQに投稿した問題6「アッカーマンの呪い」の解答を解説します。

問題

昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。

その人の手帳には以下のような式が書かれていました。

A(m, n) =
m = 0 ならば n + 1
n = 0 ならば A(m - 1, 1)
他の場合は A(m - 1, A(m, n - 1))

この関数を計算してみましょう。

A(1,3)の場合は以下のようになります。

A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問1A

A(2,1)を手で計算してみましょう。

(解答を提出する必要はありません)

問1B

気力のある人はA(2,2)を手で計算してみましょう。

(解答を提出する必要はありません)

問2A

再帰関数を使ってプログラムを書いてみましょう。

プログラミング言語は問いません。

A(3,4) の値はいくつになりますか。

答えと使った言語名のみを書いて提出してください。

プログラムの提出は必要ありません。

問2B

A(4,1) をプログラムで計算してみましょう。

ただし、スタックオバーフローのエラーが出る恐れがありますので、

パラメータ値の増加には十分注意してください。

ハングアップする恐れがあるので、他の重要なプログラムが走っているときは実行するの

はやめたほうが良いです。

(もし値が計算できたら、3行目に答を書いてください)

【解答方法】

テキストファイルに以下のように解答を書いてください。

完成しましたら、ファイルアップロードより提出してください。

???   # 1 行目 問2Aの答え
???   # 2 行目 プログラミング言語名
???   # 3 行目 問2Bの答え(計算出来なかったら空欄でも構いません)

【補足】

A(4,1) は何とか計算できるかもしれませんが、

A(4,2) はあまりにも値が大きいので普通の方法では計算できないでしょう。

LISP等を使ったほうがすんなり行くかもしれません。

コンピュータを壊さないように気をつけて頑張ってください。

解説

今回の問題はWilhelm Friedrich Ackermannというドイツの数学者が考案したアッカーマン関数を問題としました。残念ながら、進撃の巨人とは何の関係もありません。(ただし、進撃の巨人の舞台がドイツらしいので関係なくはありませんが…)

手計算の結果は以下の通りです。何度も再帰的に計算しているが視覚的に分かるように省略せずに全過程を書いてみました。僅かな数なのに再帰が深くなっているのが分かるでしょうか。

問2.1

A(2,1))
=A(1,A(2,0))
=A(1,A(1,1))
=A(1,A(0,A(1,0))
=A(1,A(0,A(0,1)))
=A(1,A(0,2))
=A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問2.2

A(2,2)
=A(1,A(2,1))
=A(1,A(1,A(2,0)))
=A(1,A(1,A(1,1)))
=A(1,A(1,A(0,A(1,0)))
=A(1,A(1,A(0,A(0,1))))
=A(1,A(1,A(0,2)))
=A(1,A(1,3))
=A(1,A(0,A(1,2)))
=A(1,A(0,A(0,A(1,1))))
=A(1,A(0,A(0,A(0,A(1,0)))))
=A(1,A(0,A(0,A(0,A(0,1)))))
=A(1,A(0,A(0,A(0,2))))
=A(1,A(0,A(0,3)))
=A(1,A(0,4))
=A(1,5)
=A(0,A(1,4))
=A(0,A(0,A(1,3)))
=A(0,A(0,A(0,A(1,2))))
=A(0,A(0,A(0,A(0,A(1,1)))))
=A(0,A(0,A(0,A(0,A(0,A(1,0))))))
=A(0,A(0,A(0,A(0,A(0,A(0,1))))))
=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))
=A(0,A(0,A(0,4)))
=A(0,A(0,5))
=A(0,6)
=7

アッカーマン関数は、自分自身を値として取る再帰関数ですが、簡単な定義にも関わらず、最初の部分でさえ爆発的に大きな値が現れてしまいます。

f:id:infoarchitect:20130625120719p:image:w640

Wikipedia:アッカーマン関数より転載

私が大学の夏期特別講座でこのアッカーマン関数を知りました。当時は、コンピュータは一般的には存在せず、共有の大型コンピュータをかろうじて使うことが出来ましたが、一行書くのに一回リターンキーを押してしまうと二、三分待たなければ、レスポンスが帰ってこないと言う有様でした。年がバレてしまいますがwww。

ですから、自分でこの関数をコンピュータでプログラミングするなんてできませんから、手で計算したのです。ところが、小さな値で計算を始めたにも関わらず、なかなか答えが収束せず、大変な思いをしました。その時、友人が書きすぎて手が痛くなったので、「これはアッカーマンの呪いだ!」と叫んでいました。そこで、これを今回の問題のタイトルにしたというわけです。

Pythonでのプログラミングの例

def ack(m, n):
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
else:
return ack(m - 1, ack(m, n - 1))
###
print ack(3,4)

挑戦者のtakana32さんがいろいろな言語で書いたアッカーマン関数のプログラムを公開してくれたので、参考にしてください。

https://github.com/Rosetta-Ack

問2A

A(3,4)の答えは125。

問2B

A(4,1)の答えは65533となります。

既にA(4,1)でコンピュータがエラーを吐き出し始めるかと思います。私のUbuntuの場合、パラメータをいじったのですが、A(4,1)はスタックオーバーフローで計算できませんでした。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってしまい、通常のやり方では計算不可能です。しかし、PythonやRubyではintegerに収まらない数も扱えるため、既に計算した値を保持することで、A(4,2)等も計算することができます。

スタックオーバーフローの対処方法についてはいくつかありますので、参考にしてみてください。

スタックオーバーフローの対処方法

とにかく、こんな簡単な式でこんな爆発的に大きな数が作れるなんて不思議ですね。しかも、コンピュータの普及していない時代にこんな関数を考えだすなんて数学者ってすごいなと思います。

CodeIQで問題作成してますので、他の問題も挑戦してみてください。

https://codeiq.jp/ace/kawagashira_nobuyuki/

07解説:SQLで行列積の計算???

CodeIQの設問「SQLで行列積の計算???」の解説をします。

問題文

下記のような4×3の疎行列Aがあります。多くの要素が0となっている行列を疎行列(sparse matrix)といいます。

0  1 -3
2  0  0
0  0  0
-1  0  4

この行列Aは列と行の情報で取り出すと、以下のように表現できます。

row_id col_id val_nr
1      2       1
1      3      -3
2      1       2
4      1      -1
4      3       4

行列を疎行列の表として表すことができます。

問1 基本問題

行列AとBが与えれたとすると、AとBの行列の積はどのようにSQLクエリーで表現できるかを考え、行列積ABを表すSQLクエリーをselect文で答えてください。

行列A, Bは以下のようなフィールドの行として表現できます。

(row_id, col_id, val_nr)

答えの行列積の表は (row_id, col_id, val_nr)という形式となります。

AとBの行列の積はAとBの表の結合として表せます。ただし、JOIN文は使いません。

データの表示順は(row_id, col_id)の昇順にしてください。

行列積Cの行列の各要素(i,k)をC(i,k)と表すと、下記の式が成り立ちますので、参考にしてください。

C(i,k) = Σ (j=1 to end) {  A(i,j) * B(j,k) }

計算結果の数値は必要ありません。データは確認用に使ってください。

添付ファイルはこちらからダウンロードしてください。

multiply.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。

$ psql yourdb < multiply.txt

前半部分は表作成とデータのロードとなっています。

mysqlやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。

問2 発展問題

表Aと表Bにはimg_nrという値が含まれており、下記のようなフィールド形式になっています。

(row_id, col_id, val_nr, img_nr)

val_nrを複素数の実数部、img_nrを複素数の虚数部とみなして、複素数行列A、Bの行列積を計算するSQLクエリーを作ってください。行列積の結果もA, Bと同じフィールド形式になります。

問1と同じく、multiply.txt内に書き込む部分がありますので、書き込んだらmultiply.txtを送ってください。

複素数x, yをx = a + bi, y = c + di (a, b, c, d ∈R, iは虚数)とすると以下の式が成り立つことに注意。

x y = (ac - bd) + (bc + ad)i

練習問題

問題が難しいようでしたら、下記の練習問題がありますので、その練習問題を解いてからこの問題に再挑戦してみてください。

エレガントにベクトル内積計算

解説

問1 基本問題

解答は以下の通りです。

select A.row_id, B.col_id, sum(A.val_nr * B.val_nr) as val_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;

表AとBの結合として表現します。制約条件を与えないと、結果がAの全行とBの全行の組み合わせとなってしまうので、制約条件を与えます。結果となる行列の要素C(i,k)について考えると以下の式が成り立ちます。

C(i,k) = Σ (j=1 to end) {  A(i,j) * B(j,k) }
= A(i,1)*B(1,k) + A(i,2)*B(2,k) + ... + A(i,m)*B(m,k)

j は 1,2,…,m の値を取りますが、C(i,k)はAの要素A(i,j)とBの要素B(j,k)を取り出して、かけたものの和になっています。

各項A(i,j)*B(j,k)ではjが共通しており、Aの列jとBの行jが共通しているので、SQLで書くと以下のような条件となります。

where A.col_id = B.row_id

C(i,k)の要素はA(i,j)*B(j,k)の和になっているので、集計関数sum()で和を計算します。

制約条件だけではなく、Cの(i,k)要素毎に結果を求める必要があるので、下記のグループ句が必要となります。

group by A.row_id, B.col_id

最後に計算結果を(i,k)順に表示するため、下記のオーダー句が書き加えます。

order by A.row_id, B.col_id

どうでしょうか。面倒くさそうな計算がSQLの結合を使うと意外と簡単に書けますね。

SQLの出力は以下のようになっていれば、うまく行っています。

row_id | col_id | val_nr
--------+--------+--------
1 |      1 |      3
1 |      2 |     -6
1 |      4 |      4
2 |      2 |      2
2 |      3 |      4
2 |      4 |     -6
4 |      2 |      7
4 |      3 |     -2
4 |      4 |     -1

問2 発展問題

解答は以下の通りです。

select A.row_id, B.col_id,
sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr) as val_nr,
sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr) as img_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;

Aの要素の実数部、虚数部をそれぞれReA, ImAとして、Bの要素の実数部、虚数部をReB, ImBとすると次の式が成り立ちます。

(ReA + ImA i) * (ReB + ImB i) = (ReA * ReB – ImA * ImB) + (ReA * ImB + ImA * ReB) i

実数部の間にマイナスがあるので、注意。

従って、行列積要素の実数部と虚数部をSQLで書くと下記の通りになります。

sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr)
sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr)

この問題は、複素数の虚数の扱いを知っていれば、応用なので、簡単ですね。

SQLの出力は以下のようになっていれば、うまく行っています。

row_id | col_id | val_nr | img_nr
--------+--------+--------+--------
1 |      1 |      3 |      3
1 |      2 |     -9 |      7
1 |      4 |      2 |     10
2 |      2 |      2 |      2
2 |      3 |      4 |     -2
2 |      4 |     -6 |      0
4 |      2 |      9 |     -5
4 |      3 |      2 |      9
4 |      4 |      5 |    -26

まとめ

集計関数sum()を使うことを思いつかないとなかなか解答に辿り着くのが難しかったようです。

一旦、気づいてしまうとエレガントに解けて、面白いかと思います。

もう少し簡単にした問題も作成しましたので、予備練習としてこちらの方も解いてみてください。

エレガントにベクトル内積計算

「アッカーマンの呪い」のスタックオーバーフローの対処方法

数多くの方々の「アッカーマンの呪い」への挑戦ありがとうございます。

プログラムは再帰関数で解くのが答えとなっていますが、A(4,1), A(4,2)の計算あたりで、計算爆発が起こり、スタックオーバーフローのエラーが発生し、計算終了となってしまいます。

挑戦者からの解答も参考にしながら、対処法をいくつか、書いてみたいと思います。

A(4,1)は65533となります。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってします。プログラミング言語が19729桁まで表現できるかというのも、チェックする必要があります。

1. スタックオーバーフローの対処

アッカーマン関数の計算は再帰が深くなるので、スタックサイズをできるだけ増やす必要があります。

Rubyでは、2.0で環境変数RUBY_THREAD_VM_STACK_SIZEが導入されたので、4MB等に設定してみてはどうでしょうか。

Pythonでは下記のようにsys.setrecursionlimit()でスタックサイズを増やせます。

import sys
sys.setrecursionlimit(10**9)

私の環境では、これでもA(4,1)は計算できませんでした。

2. 計算結果を保持する方法

m✕nの格納場所を確保しておき、一度計算したA(m,n)の結果をメモリに保存しておくと、スタックも深くならず、計算速度も向上します。

3. m=3以下のものを公式で置き換える

この方法は挑戦者のだいじゅさんから頂いた解答です。下記のようにアッカーマン関数の公式があるので、m=3以下の場合について公式で置き換えます。

If m=0 or m=1 then A(m,n) = n + 1 + m

If m=2 then A(2,n) = 2 * n + 3

If m=3 then A(3,n) = 2^(n+3) – 3

import sys
sys.setrecursionlimit(5000)
def A(m, n):
if m < 2:
return n + 1 + m
elif m == 2:
return 2*n + 3
elif m == 3:
return (2 ** (n+3)) - 3
elif n == 0:
return A(m-1, 1)
else:
return A(m-1, A(m, n-1))
def do(m, n):
try:
return A(m, n)
except RuntimeError:
raise RuntimeError, "maximum recursion depth exceeded"
except:
print "Error"
#######################
print A(4, 2)

このプログラムですと、驚くほど早くA(4,2)が求まります。

A(4,3)については、私の環境では28GBのバーチャルメモリを食い、画面は固まったまま、三日後にエラーがでて終了しました。

A(4,2)は 2^65536 – 3 になり、19729桁の十進数です。そもそも全宇宙の水素原子の数が10^80個、つまり81桁だから、既に全宇宙の水素原子数を超えている。

A(4,3)=2^(2^65536) – 3 だから、途方もない数になります。なんか、くらくらしてきた。