Fibonacci数列的一种经典递归实现

刚才.NET课程期末考试,正好最后一题考的是递归实现Fibonacci数列.顺便就把代码打出来发在这里.
(虽然没什么技术含量 )

主要特性就是使用buffer将先前已经计算过的Fibonacci数列的值保存下来,减少递归时的重复计算开销.C#没直接的lazy evaluation,这种采取buffer的策略应该是不错的选择吧.
另外,实现了IEnumerable<T>和IEnumerable接口,方便遍历Fibonacci对象当前已经缓存了的值.
由于该数列采用int表示,在下标超过46(包括)时就会溢出,所以在检查下标后会抛异常,使用时需要注意.

using System;
using System.Collections.Generic;

namespace TestFibonacci
{
    class Program
    {
        /// <summary>
        /// Demo program.
        /// </summary>
        /// <param name="args"></param>
        static void Main( string[ ] args ) {
            // create a new Fibonacci instance
            Fibonacci fib = new Fibonacci( );

            // demonstrate the implementation of IEnumerator
            foreach ( int i in fib ) {
                Console.WriteLine( i );
            }

            // demostrate the implementation of indexer
            for ( int i = 10; i < 46; i++ ) {
                Console.WriteLine( fib[ i ] );
            }
        }
    }

    /// <summary>
    /// A class that calculates the Fibonacci sequence
    /// and buffers previously calculated values.
    /// The Fibonacci sequence described here starts
    /// from index 0 with a value of 1.
    /// Because the return value is represented in an int,
    /// this class does not support indexes larger than 46.
    /// </summary>
    public class Fibonacci : IEnumerator<int>
    {
        #region Fibonacci Constructors

        /// <summary>
        /// Default constructor. Buffer length defaults to 10.
        /// </summary>
        public Fibonacci( ) : this( 10 ) { }

        /// <summary>
        /// Create an Fibonacci instance with specified buffer length.
        /// </summary>
        /// <param name="initLength"></param>
        public Fibonacci( int initLength ) {
            this.buffer = new List<int>( );
            this.buffer.Add( 1 );
            this.buffer.Add( 1 );
            InitializeBuffer( initLength );
        }

        #endregion

        #region Fibonacci Member Methods

        /// <summary>
        /// Initialize the buffer of Fibonacci sequence.
        /// </summary>
        /// <param name="length">Length of buffer.
        /// Cannot exceed 46 or an OverflowException will be thrown</param>
        public void InitializeBuffer( int length ) {
            if ( length <= this.buffer.Count ) return;
            if ( length > 46 )
                throw new OverflowException(
                    string.Format( "index {0} will cause int to overflow",
                    ( length - 1 ).ToString( ) ) );

            Calculate( length - 1 );
        }

        /// <summary>
        /// Recursively calculate the Fibonacci sequence.
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private int Calculate( int index ) {
            if ( index >= this.buffer.Count ) {
                int current = Calculate( index - 1 ) + Calculate( index - 2 );
                this.buffer.Add( current );
            }
            return this.buffer[ index ];
        }

        public IEnumerator<int> GetEnumerator( ) {
            return this;
        }

        #endregion

        #region Fibonacci Member Properties

        /// <summary>
        /// Read-only property for retrieving the
        /// Fibonacci sequence at specified index.
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public int this[ int index ] {
            get {
                InitializeBuffer( index + 1 );
                return this.buffer[ index ];
            }
        }

        #endregion

        #region Fibonacci Member Fields

        /// <summary>
        /// Buffers previously calculated values.
        /// </summary>
        private List<int> buffer;

        #endregion

        #region IEnumerator<int> Members

        /// <summary>
        /// Current enumerator cursor position.
        /// </summary>
        private int position = -1;

        public int Current {
            get {
                try {
                    return this.buffer[ position ];
                } catch ( IndexOutOfRangeException ) {
                    throw new InvalidOperationException( );
                }
            }
        }

        #endregion

        #region IDisposable Members

        public void Dispose( ) {
            // do nothing because there's nothing to release
        }

        #endregion

        #region IEnumerator Members

        object System.Collections.IEnumerator.Current {
            get {
                return this.Current;
            }
        }

        public bool MoveNext( ) {
            this.position++;
            return ( position < this.buffer.Count );
        }

        public void Reset( ) {
            this.position = -1;
        }

        #endregion
    }
}

评论

3 楼 lwwin 2008-06-06  

yield 出现太多了…… C#表示什么？

2 楼 RednaxelaFX 2008-05-22  

顺带，上面这generator版本编译出来的东西是这样的：
(via Lutz Roeder's .NET Reflector)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;

public class FibonacciGenerator {
    public static IEnumerable<int> Generate(int ord) {
        <Generate>d__0 d__ = new <Generate>d__0(-2);
        d__.<>3__ord = ord;
        return d__;
    }

    [CompilerGenerated]
    private sealed class <Generate>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable {
        private int <>1__state;
        private int <>2__current;
        public int <>3__ord;
        private int <>l__initialThreadId;
        public int <current>5__5;
        public int <first>5__1;
        public int <i>5__4;
        public int <maxord>5__3;
        public int <second>5__2;
        public int ord;

        [DebuggerHidden]
        public <Generate>d__0(int <>1__state) {
            this.<>1__state = <>1__state;
            this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
        }

        private bool MoveNext() {
            switch (this.<>1__state) {
                case 0:
                    this.<>1__state = -1;
                    this.<first>5__1 = 1;
                    this.<second>5__2 = 1;
                    this.<maxord>5__3 = (this.ord < 0x2e) ? this.ord : 0x2e;
                    this.<i>5__4 = 0;
                    while (this.<i>5__4 < this.<maxord>5__3) {
                        this.<current>5__5 = this.<first>5__1 + this.<second>5__2;
                        this.<>2__current = this.<first>5__1;
                        this.<>1__state = 1;
                        return true;
                    Label_0084:
                        this.<>1__state = -1;
                        this.<first>5__1 = this.<second>5__2;
                        this.<second>5__2 = this.<current>5__5;
                        this.<i>5__4++;
                    }
                    break;

                case 1:
                    goto Label_0084;
            }
            return false;
        }

        [DebuggerHidden]
        IEnumerator<int> IEnumerable<int>.GetEnumerator() {
            FibonacciGenerator.<Generate>d__0 d__;
            if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2)) {
                this.<>1__state = 0;
                d__ = this;
            } else {
                d__ = new FibonacciGenerator.<Generate>d__0(0);
            }
            d__.ord = this.<>3__ord;
            return d__;
        }

        [DebuggerHidden]
        IEnumerator IEnumerable.GetEnumerator() {
            return this.System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator();
        }

        [DebuggerHidden]
        void IEnumerator.Reset() {
            throw new NotSupportedException();
        }

        void IDisposable.Dispose() { }

        int IEnumerator<int>.Current {
            [DebuggerHidden]
            get { return this.<>2__current; }
        }

        object IEnumerator.Current {
            [DebuggerHidden]
            get { return this.<>2__current; }
        }
    }
}

1 楼 RednaxelaFX 2008-05-20  

明天有同学考.NET，又让我翻出这题。想了想，要让他们能记住的话这么长的代码肯定不行……于是给他们写了这个短版本：

using System;
using System.Collections.Generic;

public class FibonacciGenerator {
    public static IEnumerable<int> Generate(int ord) {
        int first = 1;
        int second = 1;
        int maxord = (ord < 46)? ord : 46;
        for (int i = 0; i < maxord; ++i) {
            int current = first + second;
            yield return first;
            first = second;
            second = current;
        }
    }
}

sealed class Program {
    static void Main(string[] args) {
        int n = 10;
        foreach (int i in FibonacciGenerator.Generate(n)) {
            Console.WriteLine(i);
        }
    }
}

哦哦C#的generator真是太有爱了 T T