Share via


每周源代码13 –斐波纳契版

[原文发表地址] The Weekly Source Code 13 - Fibonacci Edition

[原文发表时间] 2008-01-23 23:05

如果你是新来的,我要告诉你每周我都会在这里贴上些我觉得很有趣的源代码片段及其出自的项目。我之所以做这件事是本着我一贯的信念,那就是阅读源代码和写代码一样重要,甚至更为重要。我们阅读各种计算机书籍来成为更好的程序员,但除非你是阅读像《编程珠玑》这样的书籍,不然你必须不断学习各种开放源项目来寻找灵感。

所以,亲爱的读者,在这里为你们奉上第13篇每周源代码,之后也会不断继续。这里是我本周在读的一些源代码。我想看看斐波纳契数字生成器在各种不同的语言中是怎么样的。

记住(维基百科上说)斐波纳契序列是这样的:

在两个初始值后,每个数字都是前两个数字之和。第一个斐波纳契数字也表示为FN,N = 0,1,...,那就是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, ...

以下是我觉得对比很好的一些实例。在Dustin Campbell的博客里也有一些写得很棒的斐波纳契相关的东西

F#

这是用F#实现的基本的斐波纳契函数。

let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)

或者,如果你想作为一个F#控制台应用程序的输入和输出:

let fib_number = int_of_string (System.Environment.GetCommandLineArgs().GetValue(1).ToString());;

let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1);;

Printf.printf "\nThe Fibonacci value of %u is: %u\n" fib_number (fib fib_number);;

exit 0;;

Ruby

这是在Ruby中的实现,RubyTips.org中的:

x1,x2 = 0,1; 0.upto(size){puts x1; x1 += x2; x1,x2 = x2,x1}

不过这真的很难读,而且不太可能挤在一行。更典型的控制台应用程序应该是这样的

class FibonacciGenerator

def printFibo(size)

x1,x2 = 0, 1

0.upto(size){puts x1;x1+=x2; x1,x2= x2,x1} # note the swap for the next iteration

end

f = FibonacciGenerator.new

f.printFibo(10) # print first 10 fibo numbers

end

C#

在C#中做到这个有很多种方式,让我们先来看下基本的C# 2.0的实例。

static int Fibonacci (int x)

{

if (x <= 1)

return 1;

return Fibonacci (x-1) + Fibonacci (x-2);

}

现在,来看看用C# 3.0(其实是新的System.Core中的.NET 3.5和System.Func)的好方法:

Func<INT , int> fib = null;

fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

Scala

很多人对Scala的出现都很兴奋,称它为“最新程序员的闪亮对象”。它不仅因其句法有趣著称,更在于其与Java完全的互操作性。下面是Scala中的递归斐波纳契。

def fib( n: Int): Int = n match {

case 0 => 0

case 1 => 1

case _ => fib( n -1) + fib( n-2)

}

Erlang

以下是Erlang中的斐波纳契,你还能在LiteratePrograms.org上找到其他的实现,是一个不错的阅读代码的站点。

fibo(0) -> 0 ;

fibo(1) -> 1 ;

fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

你最喜欢哪一个呢?我喜欢C# 3.0和F#这两个。Ruby双变量交换的那个也很酷。它们看上去就那么让人舒服,虽然前几周LOLCode上的斐波纳契实现也不错。