|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ カー ： [かー] 【名詞】 1. car 2. (n) car ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 関 ： [せき, ぜき] (suf) honorific added to names of makuuchi and juryo division sumo wrestlers ・ 関数 ： [かんすう] (n) function (e.g., math, programming, programing) ・ 数 ： [すう, かず] 1. (n,n-suf) number 2. figure
マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 ''n'' ≤ 101 に対して 91 を返し、''n'' > 101 に対しては を返す。計算機科学者ジョン・マッカーシーが考案した。 マッカーシーの91関数の定義は次の通り。 : 例 A: M(99) = M(M(110)) 99 ≤ 100 であるため = M(100) 110 > 100 であるため = M(M(111)) 100 ≤ 100 であるため = M(101) 111 > 100 であるため = 91 101 > 100 であるため 例 B: M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... このパターンが続く = M(99) （以下、例 A と同じ） = 91 ジョン・マッカーシーはこれを、自身が開発したLISP言語で次のように書いた。 (defun mc91 (n) (cond ((<= n 100) (mc91 (mc91 (+ n 11)))) (t (- n 10)))) この関数が期待通りに動作することの証明は次のようになる。 90 ≤ ''n'' < 101 のとき、 M(n) = M(M(n + 11)) = M(n + 11 - 10) なぜなら n >= 90 であるから n + 11 >= 101 となるため = M(n + 1) 従って 90 ≤ ''n'' < 101 のとき ''M''(''n'') = 91 である。 以上を基本として、11個の数のブロック毎に証明していく。''a'' ≤ ''n'' < ''a'' + 11 について ''M''(''n'') = 91 であるとする。そのとき ''a'' - 11 ≤ ''n'' < ''a'' となるような任意の ''n'' について、 M(n) = M(M(n + 11)) = M(91) 仮定から、a ≤ n + 11 < a + 11 であるため = 91 基本ケースから 以上のように ''n'' をブロック単位で考えれば ''M''(''n'') = 91 であることが求められる。ブロック間に抜けているところはないので、''n'' < 101 の場合常に ''M''(''n'') = 91 となる。また、''n'' = 101 の場合を特殊例として追加することもできる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「マッカーシーの91関数」の詳細全文を読む スポンサード リンク
|