算法：【一列数的规则如下: 1、1、2、3、5、8、13、21、34 ，求第30位数是多少...

算法：【一列数的规则如下: 1、1、2、3、5、8、13、21、34 ，求第30位数是多少， 用递归算法实现。(C#语言)】

  /// <summary>
        /// 一列数的规则如下: 1、1、2、3、5、8、13、21、34   求第30位数是多少， 用递归算法实现。(C#语言)
        /// </summary>
        /// <param name="pos"></param>
        /// <returns></returns>
        public int GetNumberAtPos(int pos)
        {
            if(pos==0||pos==1)
            {
                return 1;
            }
            int res = GetNumberAtPos(pos - 1) + GetNumberAtPos(pos - 2);
            return res;
        }

using System; using System.Collections.Generic; using System.Linq; using System.Text;   namespace ConsoleApplication1 {     /// <summary>     /// 费伯纳契序列算法改进     /// 作者 suqifeng     /// 2011-10-24 23:43     /// </summary>     class Program     {         public static void Main(string[] args)         {               //普通递归算法             Console.WriteLine(Fibonacci(40));             //改进后递归算法             Console.WriteLine(fb(1, 1,1,40-2));             Console.Read();         }             /// <summary>         /// 普通递归算法  --费伯纳契序列         /// </summary>         /// <param name="index">第多少位费伯纳契序列 数</param>         /// <returns></returns>         static int Fibonacci(int index)         {             return index <= 2 ? 1 : Fibonacci(index - 1) + Fibonacci(index - 2);         }           /// <summary>         /// 改进后递归算法  --费伯纳契序列         /// </summary>         /// <param name="f">第一位数</param>         /// <param name="s">第二数</param>         /// <param name="index">第多少位基数从1开始</param>         /// <param name="count">第多少位费伯纳契序列 数</param>         /// <returns></returns>         public static int fb(int f, int s, int index, int count)         {               if (index <= count)             {                 return fb(s, f + s, index + 1, count);             }             return s;         }                 /// <summary>         /// 改进后递归算法  --费伯纳契序列数求和         /// </summary>         /// <param name="f">第一位数</param>         /// <param name="s">第二数</param>         /// <param name="index">第多少位基数从1开始</param>         /// <param name="count">第多少位费伯纳契序列 数</param>         /// <returns></returns>         public static int fbcSum(int f, int s, int index, int count)         {               if (index <= count)             {                 return fbcSum(s, f + s, index + 1, count);             }               return (f + s)-2;                    }       }         }

递归算法有个问题。
从n-2到3都算了2次。

　回复　引用　查看　  

#2楼[楼主] 2007-09-05 09:28 jillzhang      

@Zeus2
有什么解决办法么？

　回复　引用　查看　  

#3楼 2007-09-05 09:31 没剑      

应该要从第三位开始才递归吧
Private Function getPos(ByVal pos As Integer) As Integer
If pos <= 2 Then Return 1
Return getPos(pos - 2) + getPos(pos - 1)
End Function

　回复　引用　查看　  

#4楼[楼主] 2007-09-05 09:53 jillzhang      

@没剑
我的也是从第三位开始的咧

　回复　引用　  

#5楼 222.66.167.* 2007-09-05 10:08 小7[未注册用户]

那道面试题......

　回复　引用　查看　  

#6楼 2007-09-05 10:17 D.Oliver      

不用递归不是更好吗?
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace Test
{
public class Class1
{
private ArrayList list = new ArrayList();

public Class1()
{
}

public Class1(int num)
:base()
{
int i;

for (i = 1; i <= num; i++)
{
list.Add(Calculation(i));
}
}

private int Calculation(int num)
{
if (num == 1||num == 2)
return 1;
else
return Convert.ToInt32(list[num - 2]) + Convert.ToInt32(list[num - 3]);
}

public int Calculation()
{
return Convert.ToInt32(list[list.Count-1]);
}
}

public class test
{
public static void Main()
{
int j;
int num;
for( j=1;j<100;j++)
{
Console.WriteLine("你要计算第多少位:");
string readstr;
readstr=Console.ReadLine();
if (!string.IsNullOrEmpty(readstr))
{
if (int.TryParse(readstr, out num))
{
if (num < 1)
continue;
else
{
Class1 c1 = new Class1(num);
Console.WriteLine(c1.Calculation());
}
}
else
{
continue;
}
}
else
{
break;
}
}
}
}
}

　回复　引用　查看　  

#7楼 2007-09-05 11:56 没剑      

@jillzhang
貌似你的位置还有０的...

　回复　引用　查看　  

#8楼 2007-09-05 11:58 没剑      

老大真牛

for (i = 1; i <= num; i++)
{
list.Add(Calculation(i));
}
}


return Convert.ToInt32(list[num - 2]) + Convert.ToInt32(list[num - 3]);

　回复　引用　查看　  

#9楼[楼主] 2007-09-05 12:05 jillzhang      

其实这个方法最大的问题在哪？
在于没有验证pos的正负，这样的一个函数是很容易出错的，也是一个正确的函数，在正确使用的情况下是对的，但特殊情况下就异常了，不知道大家看出来没有

　回复　引用　查看　  

#10楼 2007-09-05 12:11 没剑      

Private Function getPos(ByVal pos As Integer) As Integer
If pos <= 2 Then Return 1
Return getPos(pos - 2) + getPos(pos - 1)
End Function
我的完成没有这个问题　

　回复　引用　查看　  

#11楼 2007-09-30 08:56 麒麟.NET      

Fibonacci数列啊

　回复　引用　查看　  

#12楼 2007-11-06 10:42 1-2-3      

好像有一种用公式来计算的方法，公式好像挺复杂的，好像在网上见过一次。

　回复　引用　  

#13楼 220.181.47.* 2007-11-25 17:27 possible[未注册用户]

public int GetNumber(int index) // index从1开始
{
int a1=1,
int a2=1,
int temp;
int count = 3
while(index >= count)
{
temp = a2;
a2 = a1+a2
a1 = temp
count++
}
return a2;
}

　回复　引用　  

#14楼 218.28.144.* 2007-12-21 14:50 小耿[未注册用户]

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication3
{
class A
{
public int GetNumberAtPos(int pos)
{
if (pos == 0 || pos == 1)
{
return 1;
}
int res = GetNumberAtPos(pos - 1) + GetNumberAtPos(pos - 2);
return res;
}
}
class Program
{

static void Main(string[] args)
{
A n = new A();

Console.WriteLine(n.GetNumberAtPos(29));
Console.ReadLine();
//int i=1;
//while (i < 4)
//{

//}

}
}
}

　回复　引用　  

#15楼 220.163.56.* 2007-12-26 22:15 NetCare[未注册用户]

int a1=1,a2=1,returnValue;
for(int i=2;i<num;i++)
{
returnValue=a2;
a2+=a1;
a1=returnValue;
}
return a1;

　回复　引用　  

#16楼 219.131.199.* 2008-02-05 14:37 imetgong[未注册用户]

public int getNumber(int pos) {
if (pos < 1) {
return -1;
}

if (pos < 3) {
return 1;
}

while (pos > 0) {
return getNumber(pos - 2) + getNumber(pos - 1);
}

return -1;
}

　回复　引用　查看　  

#17楼 2008-07-29 16:22 shawnliu      

代码效率太差了把
只需要用两个变量保存前两位不就行了 再加一个当前数值，
最后更新一下变量

　回复　引用　查看　  

#18楼 2008-07-31 14:23 丛林之王      

楼主这个貌似 应该这样
public int GetNumberAtPos(int pos)
{
if (pos == 0 ||pos == -1 )
{
return 0;
}
if ( pos == 1)
{
return 1;
}
int res = GetNumberAtPos(pos - 1) + GetNumberAtPos(pos - 2);
return res;
}

　回复　引用　  

#19楼 222.89.91.* 2008-11-25 08:23 哲思[未注册用户]

支持13楼的
using System;
using System.Collections.Generic;
using System.Text;

namespace 算法设计_一列数
{
class Program
{
static void Main(string[] args)
{

DateTime time2 = DateTime.Now;
Console.WriteLine(time2.ToString());
int number2 = GetNumber(30);
DateTime time3 = DateTime.Now;
Console.WriteLine(time3.ToString());
TimeSpan t2 = time3.Subtract(time2);
Console.WriteLine(t2.ToString());
Console.WriteLine(number2);
DateTime time = DateTime.Now;
Console.WriteLine(time.ToString());
int number = getNumber(30);
DateTime time1 = DateTime.Now;
Console.WriteLine(time1.ToString());
TimeSpan t1 = time1.Subtract(time);
Console.WriteLine(t1.ToString());
Console.WriteLine(number);

}


public static int getNumber(int pos)
{
if (pos == 0 || pos == 1)
{
return 1;

}
int s = getNumber(pos - 1) + getNumber(pos-2);
return s;

}
public static int GetNumber(int index) // index从1开始
{
int a1=1;
int a2=1;
int temp;
int count = 2;
while(index >= count)
{
temp = a2;
a2 = a1+a2;
a1 = temp;
count++;
}
return a2;
}

}
}
执行以后就可以看出差别了
数值的索引越往后差别越明显！

　回复　引用　  

#20楼 218.64.57.* 2009-03-16 10:09 test111111111111111[未注册用户]

int fwdadd(int i)
{
int s,m,n,flag;
if(i<3)
return 1;
else
{
m=1;n=1;flag=0;s=1;
for(int k=3;k<=i;k++)
{
flag=1-flag;
if(flag)
m=m+n;
else
n=n+m;

}
if(flag)
return m;
else
return n;
}
}

　回复　引用　查看　  

#21楼 2009-05-26 13:44 Funeral      

不用递归也能很简单的

int fibonacci = 0;
for (int i = 0, j = 0, k = 1, fib = 1; i < 30; fib = j + k, j = k, k = fib, i++)
{
fibonacci = fib;
}
Console.WriteLine(fibonacci);
Console.Read();

　回复　引用　  

#22楼 119.147.107.* 2009-07-08 00:46 liubaiwu[未注册用户]

private int add(int f,int s,int index)
{
int result=f+s;
if(index<=30)
{
return add(s,result,index+1);
}
return result;
}
这样的解决方法

　回复　引用　查看　  

#23楼 2011-10-24 23:51 长沙-C#山高我为峰      

View Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

using System; using System.Collections.Generic; using System.Linq; using System.Text;    namespace ConsoleApplication1 {     /// <summary>     /// 费伯纳契序列算法改进     /// 作者 suqifeng     /// 2011-10-24 23:43     /// </summary>     class Program     {         public static void Main(string[] args)         {                //普通递归算法             Console.WriteLine(Fibonacci(40));             //改进后递归算法             Console.WriteLine(fb(1, 1,1,40-2));             Console.Read();         }               /// <summary>         /// 普通递归算法  --费伯纳契序列         /// </summary>         /// <param name="index">第多少位费伯纳契序列 数</param>         /// <returns></returns>         static int Fibonacci(int index)         {             return index <= 2 ? 1 : Fibonacci(index - 1) + Fibonacci(index - 2);         }            /// <summary>         /// 改进后递归算法  --费伯纳契序列         /// </summary>         /// <param name="f">第一位数</param>         /// <param name="s">第二数</param>         /// <param name="index">第多少位基数从1开始</param>         /// <param name="count">第多少位费伯纳契序列 数</param>         /// <returns></returns>         public static int fb(int f, int s, int index, int count)         {                if (index <= count)             {                 return fb(s, f + s, index + 1, count);             }             return s;         }                     /// <summary>         /// 改进后递归算法  --费伯纳契序列数求和         /// </summary>         /// <param name="f">第一位数</param>         /// <param name="s">第二数</param>         /// <param name="index">第多少位基数从1开始</param>         /// <param name="count">第多少位费伯纳契序列 数</param>         /// <returns></returns>         public static int fbcSum(int f, int s, int index, int count)         {                if (index <= count)             {                 return fbcSum(s, f + s, index + 1, count);             }               return (f + s)-2;                     }        }           }

　回复　引用　查看　  

#24楼 2012-03-20 14:07 不死鸟一灰      

1 2 3 4 5

private static int Sum(int num) {         if(num<3)return 1;         return Sum(num-1)+Sum(num-2);     }