Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
TAKの実装と高速化

TAKの実装と高速化

Pandoc で お好みの形式に変換してご利用ください。

問題1

Common Lispの以下の実装を参考に竹内関数(Tak) を自身の言語で実装してください。

(defun tak (x y z)
  (if (<= x y)
      y
      (tak (tak (1- x) y z)
           (tak (1- y) z x)
           (tak (1- z) x y))))

参考 defun

関数定義です。

http://clhs.lisp.se/Body/m_defun.htm#defun

参考 1-

1- は以下の定義を満す、引数より1少ない数を返す関数です。

http://clhs.lisp.se/Body/f_1pl_1_.htm

問題2

問題1で実装したTAKに 12 6 0の引数を与えて実行して実行にかかったリソースを測定し、 その後、効率よく計算できるように変更して再度実行し、前回に比べてどれくらいリソースが 節約できたかを調べてください。

CL-USER> (time (tak 12 6 0))
(TAK 12 6 0)
took 29,804 microseconds (0.029804 seconds) to run.
During that period, and with 4 available CPU cores,
     28,354 microseconds (0.028354 seconds) were spent in user mode
        793 microseconds (0.000793 seconds) were spent in system mode
12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment