`
RednaxelaFX
  • 浏览: 3049306 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

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

    博客分类:
  • C#
阅读更多
刚才.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

相关推荐

    C++实现Fibonacci数列递归及非递归算法

    对于Fibonacci数列,递归实现非常直观: ```cpp int fibonacciRecursion(int n) { if (n ) return n; return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2); } ``` 这个函数通过递归调用自身计算F(n)...

    递归方法实现斐波那契数列_递归方法实现斐波那契数列_python_源码

    Python中递归实现斐波那契数列的基本代码如下: ```python def fibonacci(n): if n print("输入错误,n应大于0") elif n == 1 or n == 2: return 1 else: return fibonacci(n-1) + fibonacci(n-2) ``` 这个...

    Fibonacci数列(非递归的函数调用)

    斐波那契数列是一个经典的数学概念,在计算机科学中经常被用作算法示例和问题解决的工具。这个数列的定义是这样的:第一项F0等于0,第二项F1等于1,从第三项开始,每一项都等于前两项之和。即Fn = Fn-1 + Fn-2 (n &gt;=...

    C++:斐波那契数列(迭代和递归)

    C++是一种强大的编程语言,特别适合用来实现各种算法,包括斐波那契数列的计算。我们可以使用两种主要方法在C++中实现斐波那契数列:迭代和递归。 **迭代法**: 迭代法是通过循环结构来计算斐波那契数列的一种高效...

    DiGuiDemo.zip_斐波那契_斐波那契数列_递归_递归求阶乘

    在IT领域,递归是一种强大的编程技术,常用于解决复杂问题。这个名为"DiGuiDemo.zip"的压缩包文件包含了关于斐波那契数列、递归以及递归求阶乘的知识点,通过一个名为"DiGuiDemo.java"的Java源代码文件进行演示。 ...

    递归算法算斐波那契数列

    递归是一种解决问题的方法,通过将问题分解为更小的子问题来解决原问题。在计算机科学中,递归通常涉及到调用自身的过程或函数。对于斐波那契数列来说,可以通过递归来简单直观地实现。 #### 递归函数设计 递归函数...

    华为题(斐波那契数列非递归)[定义].pdf

    华为题(斐波那契数列非递归) ...结论:本文总结了斐波那契数列的定义、非递归实现、栈数据结构、malloc和realloc函数、斐波那契数列的应用和软件网络技术等知识点,并对斐波那契数列的实现和应用进行了深入探讨。

    汇编语言,计算斐波那契数列的前22项,斐波那契数列,分别用两种方法:递归调用,普通循环加法

    在汇编语言中,递归实现斐波那契数列通常涉及调用子程序。子程序会接收当前项的前两个值,然后返回它们的和。递归调用的优点在于其代码简洁,但缺点是效率较低,因为每次调用都会涉及到栈操作,对于较大的n,可能会...

    java实现Fibonacci数列

    迭代方法是一种更高效的实现方式,它避免了递归方法中的重复计算问题。通过使用循环结构,仅需一次遍历即可计算出指定位置上的Fibonacci数。 ```java public class Fibonacci { public int fib(int n) { if (n ) ...

    斐波那契数列(前100项).rar

    6. **数据结构**:斐波那契堆是一种高效的数据结构,用于优先队列操作,其名字来源于斐波那契数列。 综上所述,"斐波那契数列(前100项).rar"这个压缩包可能是为学习者提供一个参考,用于验证自己的代码是否正确...

    递归斐波那契数列

    斐波那契数列是一个经典的数学概念,在计算机科学中有着广泛的应用,特别是在算法设计和分析中。这个数列由以下规则定义:F(0) = 0,F(1) = 1,对于n &gt; 1,F(n) = F(n-1) + F(n-2)。递归是一种解决问题的方法,它将...

    斐波那契递归时间和非递归时间的比较(csdn)————程序.pdf

    递归在解决斐波那契数列这类问题时表现出明显的性能瓶颈,而迭代方法则提供了一种更优的解决方案,特别是在处理大规模数据时。这不仅是一个基础编程练习,也是理解算法复杂性和优化技巧的一个重要实例。

    c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    斐波那契数列是一种经典的数学序列,其中每个数字是前两个数字的和。数列的前两个数字通常是0和1,之后的每个数字都是前两个数字相加得到的。斐波那契数列的前几项是1、1、2、3、5、8、13、21、34等。在计算机科学中...

    算法基础与递归-百积问题-递归求公约数-求阶乘-斐波那契数列

    在计算机科学中,递归算法是一种非常重要的算法设计技术。递归算法的基本思想是将问题分解成更小的子问题,然后使用同样的方法解决这些子问题,直到问题的规模小到可以直接解决为止。本文将通过实验和代码实现,来...

    java用非递归的方法打印Fibonacci数列

    Java 非递归打印 Fibonacci 数列 Java 中的 Fibonacci 数列是通过非递归的方法来实现的,该方法使用循环来计算 ...使用非递归的方法来打印 Fibonacci 数列是一种非常有用的技术,可以帮助我们更好地解决实际问题。

    组合数学fibonacci数列递归非递归求解

    递归是求解Fibonacci数列的一种直观方法,其代码实现如给定文件中的第一个示例所示: ```c #include int f(int i) { if (i == 1 || i == 2) return 1; else return f(i - 1) + f(i - 2); } void main() { int n,...

    经典斐波那契数列的算法实现教案.doc

    * 斐波那契数列是一种经典的数学算法题,它可以通过 FOR 循环实现。 * 斐波那契数列的算法实现可以培养学生变通性思维能力和程序设计能力。 * 斐波那契数列的算法实现可以作为 FOR 循环构造知识点的稳固性算法题。 ...

    详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    尾递归是递归的一种特殊形式,它在函数的最后返回递归调用的结果,不进行其他操作。如 `Fib_tail_recursion` 函数所示,它通过传递额外的参数来存储中间结果,从而避免了重复计算。尾递归可以被编译器或解释器优化...

    mips汇编语言实现斐波那契数列的排列

    MIPS汇编语言实现斐波那契数列的排列 本资源使用MIPS汇编语言在Mars环境下实现斐波那契数列的排列,并输出前n项的下标、十进制数值和十六进制数值。 知识点总结: 1. MIPS汇编语言基础知识:MIPS汇编语言是一种...

    Fibonacci(斐波那契)数列的JAVA解法

    递归算法是解决斐波那契数列问题的一种常见方法。该方法的思想是将问题分解成更小的子问题,直到问题的答案变得明确。下面是一个使用递归算法计算斐波那契数列的JAVA代码: public class Fib_ra{ public static int...

Global site tag (gtag.js) - Google Analytics