• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Ackerman函数以及 Linux环境下的绘图(perl脚本实现)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

转自于http://blog.chinaunix.net/uid-20602285-id-3078231.html

老师用ackerman函数来测试我们的lisp interpreter是否能应付extremely recursive function,虽然我们都不能,但也说明了一个健壮的interpreter是需要优化recursive function的一个道理。

ackerman函数 wiki 上有介绍:http://en.wikipedia.org/wiki/Ackerman_function

我下面记录的是怎么算出来A(4,2)。(如下表述中,ns就代表A)
ns(0,x) = x + 1
ns(1,x) = ns(0, ns(x-1)) && ns(1,0) = 2. so, ns(1,x) = x + 2
ns(2,x) = ns(1, ns(2,x-1)) = ns(2,x-1)+2 && ns(2,0) = ns(1,1) = 3. so, ns(2,x) = 2x+3
ns(3,x) = ns(2,ns(3,x-1)) = 2*ns(3,x-1)+3 && ns(3,0) = ns(2,1)=5. so, ns(3,x) = 2^(x+3) - 3
ns(4,x) = ns(3, ns(x-1)) = 2^(ns(3,x-1)+3) - 3 && ns(4,0) = ns(3,1) = 13
but if we let g(x) = ns(4,x) + 3
we have g(x) = 2^(g(x-1)) && g(0) = 16 = 2^4
so I think it's the end of this story (unless we use the symbol from knuth, which I just learned from wiki,
but I can manually get ns(4,2) = g(2) -3 = 2^(g(1)) - 3 = 2^(2^(g(0))) - 3 = 2^(2^16)) - 3 = 2^65536 - 3

these links may be helpful:
http://www.wolframalpha.com/input/?i=f%28x%29%3Df%28x-1%29%2B1%2Cf%280%29%3D2
http://www.wolframalpha.com/input/?i=f%28x%29+%3D+f%28x-1%29%2B2%2Cf%280%29%3D3
http://www.wolframalpha.com/input/?i=f%28x%29%3D2*f%28x-1%29%2B3%2Cf%280%29%3D5
http://www.wolframalpha.com/input/?i=f%28x%29%3D2^%28f%28x-1%29%2B3%29-3%2Cf%280%29%3D13
http://www.wolframalpha.com/input/?i=log2%28g%28x%29%29%3Dg%28x-1%29%2Cg%280%29%3D16
http://www.wolframalpha.com/input/?i=2^65536-3

当我算出来(4,2)后,我想尝试下得到ackerman函数的通式,结果后来尝试下后也可以了,需要引入wiki里学到的knuth发明的符号。“向上箭头符号”。↑
懂得这个符号以及扩展符号↑↑后,就可以证明ackerman函数的通式了,最傻瓜的方法是用归纳法证明,首先证明base case (1,1)成立,然后证明(1,x)成立;然后假设对于小于等于m的i或小于等于n的j (i,j)都成立,证明(i,j+1)成立。这样归纳法就完整了。

但是归纳法要求事先知道通式,这个不符合认识的流程。认识的流程应该是探索->猜想->证明。
以上我得出(4,2)的过程就是一个探索的过程。但是从中观察出规律确实很难,我也是在得到wiki的启发后知道的,接下来可以证明一下(4,x),有了knuth的符号,很容易证明;接下来再证明(5,x),也是可以的,无非knuth符号多了一层。最后再猜想,便很自然了。

ackerman函数通式的得出就写到这里。

还有一个有趣的现象,是我一个同学冷潇泠想到的,他建议把函数递归过程中的B打印出来,并且配上递归层数i,形成一些(i,B)对,把这个画在坐标系上会形成无数个抛物线,且每个抛物线都是下个抛物线的前面部分。

这个图也许还不清晰,把抛物线下的点都删掉,便有更清晰的图

这个现象还是蛮有意思的。
我的ackerman函数实现如下:

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. int g = 0;

  4. int ackerman(int a, int b)
  5. {
  6. if(g++<100000) {
  7. printf("%d %d\n",a,b);
  8. }
  9. else
  10. exit(1);

  11. if(a==0)
  12. return b+1;
  13. else if (b==0)
  14. return ackerman(a-1,1);
  15. else
  16. {
  17. return ackerman(a-1,ackerman(a,b-1));
  18. }

  19. }

  20. int main()
  21. {
  22. int a,b;
  23. scanf("%d %d",&a,&b);
  24. ackerman(a,b);
  25. }
产生数据后分析数据的perl脚本如下:
  1. #!/usr/bin/perl
  2. open(INP,"ackerman4.2.txt");
  3. open(OUT,">localm1");
  4. $a=0;
  5. $b=0;
  6. $c=0;
  7. $i=0;
  8. while(defined($line=<INP>))
  9. {
  10. @col=split(" ",$line);
  11. $a=$col[1]; #the 2nd column. B
  12. if(($a<$b)&&($b>$c))
  13. {
  14. #print OUT "$i ${col[0]} $b \n";
  15. print OUT "$i $b \n";
  16. #print OUT "$i $b \n";
  17. }
  18. $c=$b;
  19. $b=$a; #b = a. b is the temporary max
  20. $i++;
  21. }

  22. close(INP);
  23. close(OUT);
然后用gnuplot
>plot 'localm1'
即可得出图片。
图片效果由于我不熟悉gnuplot便用得最原始的。

最后引用冷潇泠画的一个图,这个图更清晰。也是gnuplot。也可以用excel画。我都只知道理论上可画,但实际上都没经验。



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Perl 语言入门发布时间:2022-01-22
下一篇:
perl实例详解第四版笔记2 模块化发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap