懂麦卡锡(McCarthy)91函数的大虾请进!
今天,我在做数据结构时看到了麦卡锡(McCarthy)91函数.我很好奇:
实质上这个函数本身很简单:
１如果 N <= 100, 那么 f91(N) = f91( f91( N+11) )
２如果 N >= 101, 那么 f91(N) = N-10
但这样的函数有表达了什么规律呢?
本函数又是在什么背景下产生的呢?
本函数又常应用于那些领域呢?
问题点数：100、回复次数：12Top
1 楼ccs02287（☆兜兜里有糖☆偶滴兜兜里有糖，你和我玩不？）回复于 2006-07-02 12:12:08 得分 0
沙发……
帮顶Top
2 楼UPCC（杂食动物）回复于 2006-07-02 14:03:19 得分 20
１如果 N <= 100, 那么 f91(N) = f91( f91( N+11) )
２如果 N >= 101, 那么 f91(N) = N-10
------------------------------
很奇怪的坐标线/点？？是人工智能方面的。
原本是为了解决一个基础性的数学问题：是否只要给人以足够的时间演算，数学函数都能够通过有限次机械步骤求得解答？Top
3 楼YYmei（燕燕）回复于 2006-07-03 19:22:02 得分 0
UPCC(杂食动物) 能不能介绍一两份与该函数有关的资料给我呢？帮帮吧！Top
4 楼UPCC（杂食动物）回复于 2006-07-03 19:28:58 得分 0
楼主，我没有，不然肯定给你。
这里大家是相互帮忙的Top
5 楼UPCC（杂食动物）回复于 2006-07-03 19:42:55 得分 0
我写了一个：
int f91(int N)
{
return N<=100?f91(N+11):(N-10);
}Top
6 楼crazy_lazy_pig（疯狂懒猪）回复于 2006-07-04 01:04:16 得分 50
In discrete mathematics, the McCarthy 91 function is a recursive function which returns 91 for all integer arguments n ≤ 100 and returns n − 10 for n > 100. It was conceived by computer scientist John McCarthy.
The McCarthy 91 function is defined as
M(n)=\left\{\begin{matrix} n - 10, & \mbox{if }n > 100\mbox{ } \\ M(M(n+11)), & \mbox{if }n \le 100\mbox{ } \end{matrix}\right.
Examples:
M(99) = M(M(110)) since 99 ≤ 100
= M(100) since 110 > 100
= M(M(111)) since 100 ≤ 100
= M(101) since 111 > 100
= 91 since 101 > 100
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)
.... Pattern continues
= M(99)
(same as above proof)
= 91
Here is how John McCarthy may have written this function in Lisp, the language he invented:
(defun mc91 (n)
(cond ((< n 1) (error "Function only defined for positive values of n"))
((<= n 100) (mc91 (mc91 (+ n 11))))
(t (- n 10))))
Here is a proof that the function behaves as expected.
For 90 ≤ n < 101,
M(n) = M(M(n + 11))
= M(n + 11 - 10), since n >= 90 so n + 11 >= 101
= M(n + 1)
So M(n) = 91 for 90 ≤ n < 101.
We can use this as a base case for induction on blocks of 11 numbers, like so:
Assume that M(n) = 91 for a ≤ n < a + 11.
Then, for any n such that a - 11 ≤ n < a,
M(n) = M(M(n + 11))
= M(91), by hypothesis, since a ≤ n + 11 < a + 11
= 91, by the base case.
Now by induction M(n) = 91 for any n in such a block. There are no holes between the blocks, so M(n) = 91 for n < 101. We can also add n = 101 as a special case.
Top
7 楼pcs_starfish（苏格拉底）回复于 2006-07-04 13:49:57 得分 0
也许这样大家会很清楚
１如果 N <= 100, 那么 f91(N) = N+1
２如果 N >= 101, 那么 f91(N) = N-10
Top
8 楼crazy_lazy_pig（疯狂懒猪）回复于 2006-07-04 14:09:24 得分 0
楼上的测试过没有啊？这么简单的东西，直接编程验证一下很快的。
正确的是：
1.如果 N <= 101 ， 那么 f91(N)=91
2.如果 N > 101 , 那么 f91(N)=N-10
上面有证明过程，好好看看。Top
9 楼pcs_starfish（苏格拉底）回复于 2006-07-04 18:34:29 得分 20
也许这样大家会很清楚
１如果 N <= 100, 那么 f91(N) = f91(N+1) //更正一下
２如果 N >= 101, 那么 f91(N) = N-10Top
10 楼crazy_lazy_pig（疯狂懒猪）回复于 2006-07-04 18:42:49 得分 0
呵呵，这样对了Top
11 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-07-07 19:08:15 得分 10
原来离散数学上的mccarthy很是出名！Top
12 楼YYmei（燕燕）回复于 2006-07-07 22:01:05 得分 0
谢谢在家了。Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
