Fibonacci数列的一种经典递归实现
刚才.NET课程期末考试,正好最后一题考的是递归实现Fibonacci数列.顺便就把代码打出来发在这里.(虽然没什么技术含量http://www.agoit.com/images/smiles/icon_wink.gif )
主要特性就是使用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 }}
页:
[1]