重构斐波那契算法

Question

我已经多年没有使用静态类型语言了，现在我需要学习C#。我的第一个任务是完成这里的15个练习。

我刚刚完成了第二个斐波那契任务，虽然并不难实现且可行，但是我认为它看起来很丑，而且是否可以用更加典雅精简的代码实现呢？

我通常喜欢和已经知道自己在做什么的人一起学习编程，但今天这个选项对我不适用，所以我希望在这里发帖会是下一个最好的选择。

因此，对于所有的C#高手们，如果您要重构以下代码，它会是什么样子？

using System;
using System.Collections;

namespace Exercises
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Find all fibinacci numbers between:");
            int from = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("And:");
            int to = Convert.ToInt32(Console.ReadLine());
            Fibonacci fibonacci = new Fibonacci();
            fibonacci.PrintArrayList(fibonacci.Between(from, to));

        }
    }

    class Fibonacci
    {   
        public ArrayList Between(int from, int to)
        {               
            int last = 1;
            int penultimate = 0;
            ArrayList results = new ArrayList();
            results.Add(penultimate);
            results.Add(last);

            while(last<to)
            {
                int fib = last + penultimate;
                penultimate = last;
                last = fib;
                if (fib>from && fib<to) results.Add(fib.ToString());
            }
            return results;
        }

        public void PrintArrayList(ArrayList arrayList)
        {
            Console.WriteLine("Your Fibonacci sequence:");
            Console.Write(arrayList[0]);
            for(int i = 1; i<arrayList.Count; i++)
            {
                Console.Write("," + arrayList[i]);
            }
            Console.WriteLine("");
        }

    }
}

Regards,

Chris

- ChrisInCambo

Answer 1

作为一个迭代器块：

using System;
using System.Collections.Generic;
using System.Linq;

static class Program {
    static IEnumerable<long> Fibonacci() {
        long n = 0, m = 1;

        yield return 0;
        yield return 1;
        while (true) {
            long tmp = n + m;
            n = m;
            m = tmp;
            yield return m;
        }
    }

    static void Main() {
        foreach (long i in Fibonacci().Take(10)) {
            Console.WriteLine(i);
        }
    }
}

现在这个方法是完全的惰性运算，使用LINQ的Skip/Take等方法可以方便地控制开始和结束。例如，对于你的“between”查询：

foreach (long i in Fibonacci().SkipWhile(x=>x < from).TakeWhile(x=>x <= to)) {...}

- Marc Gravell

---

SO上是否有绝地徽章？ - AnthonyWJones

恐怕不行……有“大师”的，但我没有它；-p - Marc Gravell

谢谢Marc，这正是我想要的，现在我有新的事情可以去学习了。还有其他人有解决同样问题的替代方法吗？ - ChrisInCambo

你可以使用数组或List<T>而不是ArrayList，但这两种方法都涉及缓冲，而迭代器块则避免了这种情况。 - Marc Gravell

谢谢您的建议，我会查看免费章节。Marc，我需要使用哪些包才能使您的示例编译通过？目前编译器无法处理Take扩展方法。 - ChrisInCambo

Answer 2

如果你更喜欢递归而不是循环：

public static void Main(string[] args)
{
    Func<int, int> fib = null;
    fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

    int start = 1;
    int end = 10;
    var numbers = Enumerable.Range(start, end).Select(fib);
    foreach (var number in numbers)
    {
        Console.WriteLine(number);
    }
}

- Paco

---

只是我的个人看法...在计算斐波那契数列时，递归是很浪费资源的。 - Gishu

函数式编程语言不使用循环。 - Paco

我不知道FProgs没有循环...奇怪。 - Gishu

在使用递归匿名函数时，请使用Y组合子！^^ - Dario

Answer 3

我会将 IEnumerable<int> 类型更改为 IEnumerable<Int64>，因为它从50开始就会溢出。

- Can

---

你想把IEnumerable<int>改成IEnumerable<long>吗？ - tuinstoel

Answer 4

对于那些像我一样还没有屈服于 Linq 的人，这是“Simple Jack”版本。我在绝地俱乐部被封杀了 ;)

static List<int> GetAllFibonacciNumbersUpto(int y)
{
   List<int> theFibonacciSeq = new List<int>();

   theFibonacciSeq.Add(0);   theFibonacciSeq.Add(1);

   int F_of_n_minus_2 = 0;   int F_of_n_minus_1 = 1;
   while (F_of_n_minus_2 <= y)
   {
      theFibonacciSeq.Add(F_of_n_minus_1 + F_of_n_minus_2);

      F_of_n_minus_2 = F_of_n_minus_1;
      F_of_n_minus_1 = theFibonacciSeq.Last<int>();
   }
   return theFibonacciSeq;
}

现在我们把这个解决了...

// read in some limits
int x = 0; int y = 6785;

foreach (int iNumber in GetAllFibonacciNumbersUpto(y).FindAll(element => (element >= x) && (element <= y)))
    Console.Write(iNumber + ",");
Console.WriteLine();

- Gishu

---

除非你使用了Last()，LINQ的扩展方法……否则要使其不使用LINQ，则必须使用list[list.Count-1]。 - Marc Gravell

唯一让我不满意的是LINQ使代码难以阅读。Last()，FindAll() - 我可以猜测它们的作用.. 但我不得不去MSDN查找Take()和TakeWhile()的含义.. - Gishu

可能是因为我还不熟悉LINQ吧。顺便说一句，我已经给你的答案点了赞。它很简洁明了，尽管有点复杂。 - Gishu

你的最终数字将会有一个尾随逗号。 - Andrew Gray

@AndrewGray - 是的，我在使用 String.Join 之前就这样写了 :) 现在我会这样写：String.Join(",", enumerableSeq)。 - Gishu