Ackermann函数

　　这是我注册is-programmer博客以来第一篇博客，我打算主要在这个博客里写一些技术性的文章。这个博客的风格很好，界面非常清爽，速度也快。网易博客虽然功能稳定，但是风格太繁，不太适合纯程序方面的文章。特别是贴代码，那个真麻烦，以前我为了贴一些把代码贴得漂亮点，花了很多功能，要么它把那些缩进的Tab键给我弄没了，要么带有高亮的风格速度超慢。弄个截图更是麻烦。后来偶尔见到了这个博客站点，感觉很对我的胃口。简约但不失强大，速度很快。

　　Ackermann是我在一个专门测试各类编程语言上的网站见到过一次，后来在charlee的博客上又看到了相关的说明，原来这个函数虽然很简单，但是其算法的复杂度却很高，适于语言性能的比较。文章里专门还用Perl和C语言进行了对比，结果C语言比Perl快了280倍以上！看来得了解一下，文章还提供了一个MathWorld的链接，里面有更详细的说明，下面是Ackermann函数的定义，图是从MathWorld里弄来的。

　　下面是测试所用的Perl代码：

  1. #!/usr/bin/perl
  2.  
  3. sub ackermann {
  4.   my ( $m, $n ) = @_;
  5.  
  6.   return $n + 1 if $m == 0;
  7.   return ackermann( $m - 1, 1 ) if $n == 0;
  8.   return ackermann( $m - 1, ackermann( $m, $n - 1 ) );
  9. }
  10.  
  11. print ackermann( 3, 10 ), "\n";
　　下面是C代码：
  1. #include <stdio.h>
  2.  
  3. int ackermann(int m, int n);
  4.  
  5. int main() {
  6.   int result = ackermann(3, 10);
  7.   printf("%d\n", result);
  8.   return 0;
  9. }
  10.  
  11. int ackermann(int m, int n) {
  12.   if (m == 0) return n+1;
  13.   if (n == 0) return ackermann(m-1, 1);
  14.   return ackermann(m-1, ackermann(m, n-1));
  15. }
  16.  

 　　下面我再写一个Lua代码，纯粹测试一下is-programmer的FCKEditor 2.6的所提供的代码美化功能：

  1. #! /usr/bin/env lua
  2.  
  3. function ackermann(m,n)
  4.         if m==0 then
  5.                 return n+1
  6.         elseif n==0 then
  7.                 return ackermann(m-1,1)
  8.         else
  9.                 return ackermann(m-1,ackermann(m,n-1))
  10.         end     
  11. end
  12.  
  13. print(ackermann(3,10))

 

Perl Perl Comments(0) 2008年4月11日 13:28