วันเสาร์ที่ 29 ธันวาคม พ.ศ. 2550

Infinite Sequence Part III - Fibonacci

Last post, I had described about how to create based class for infinite sequence, and create a simple generic sequence. This post, we will move on to Fibonacci sequence.

Each Fibonacci number is the sum of 2 preceding number. First and second Fibonacci numbers are 0 and 1. Third Fibonacci number is the sum of First and Second (0+1) equal to 1. And forth Fibonacci number is the sum of Second and Third number (1+1) equal to 2. First 20 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Now let's start coding Fibonacci.

public class Fibonacci : BaseSequence<BigInteger> {
    protected override IEnumerable<BigInteger> Enumerate() {
        BigInteger value = BigInteger.Zero;
        BigInteger value2 = BigInteger.One;

        yield return value;
        yield return value2;
        while (true) {
            value += value2;
            yield return value;
            value2 += value;
            yield return value2;
        }
    }
}


Just few lines of code, Fibonacci sequence is finished! Value and value2 return value alternately. Value variable return value in odd position. And value2 return value in even position.

Test Fibonacci sequence with projecteuler.net questions.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x < 1000000).Where(x => x % 2 == 0).Sum()
);
//1089154


What is the first term in the Fibonacci sequence to contain 1000 digits?

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x.ToString(10).Length < 1000).Count()
);
//4782


Next post, we will go to much harder sequence, which is Prime sequence.

ไม่มีความคิดเห็น: