主題
Search

TAK 函式

一個由 I. Takeuchi 於 1978 年提出的遞迴函式（Knuth 1998）。對於整數 x, y, 和 z，它被定義為

t(x,y,z)={y for x<=y; t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)) otherwise
(1)

這可以更簡單地描述為

t(x,y,z)={y if x<=y; {z if y<=z; x otherwise otherwise
(2)

設 T(x,y,z) 為上述函式中 "otherwise" 被呼叫的次數。那麼對於 a>b>0，T(a,b,0) 由下式給出

T(a,b,0)=4sum_(k=0)^(b)(a-b)/(a+b-2k)(a+b-2k; b-k)-3
(3)
=1+4sum_(k=0)^(b-1)(a-b)/(a+b-2k)(a+b-2k; b-k)
(4)

(Vardi 1991)。

Takeuchi 數定義為 T_n=T(n,0,n+1)。

TAK 函式也與投票問題有關 (Vardi 1991)。

另請參閱

阿克曼函式, 投票問題, 遞迴函式, Takeuchi 數, Takeuchi-Prellberg 常數

使用 探索

參考資料

Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, p. 321, 2003.Gabriel, R. P. Performance and Implementation of Lisp Systems. Cambridge, MA: MIT Press, 1985.Knuth, D. E. "Textbook Examples of Recursion." Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy (Ed. V. Lifschitz). Boston, MA: Academic Press, pp. 207-229, 1990.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Vardi, I. "The Running Time of TAK." Ch. 9 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 179-199, 1991.

在 上被引用

TAK 函式

引用為

Weisstein, Eric W. “TAK 函式。” 來自 Web 資源。 https://mathworld.tw/TAKFunction.html

主題分類