一道算法的面试题

Question

已知一个数列的前几位数为，1，1，2，3，5，8，13，21，34.求第30位的数（用递归算法实现）和100位的数。

Answer 1

fib(int n)
   {
      if(n=1||n=2)
          return 1;
       else
          return fib(n-1)+fib(n-2)
   }
费波拿切数列

Answer 2

static decimal F(int n) 
{ 
  if (n < 3) return 1; 
  return F(n-1) + F(n-2); 
} 

Answer 3

http://baike.baidu.com/view/112871.htm

Answer 4

这个就可以，不过要加个返回类型int

Answer 5

/// <summary>
/// 计算1，1，2，3，5，8，13，21，34数列的第n位的值
/// </summary>
/// <param name="n">第n位</param>
/// <param name="nOne">第一位的值</param>
/// <param name="nTwo">第二位的值</param>
/// <returns>第n位的值</returns>
public int Fib(int n, int nOne, int nTwo)
{
for (int i = 2; i < n; i++)
{
nTwo += nOne;
nOne = nTwo - nOne;
}
return nTwo;
}

Answer 6

考虑到n==1时，
/// <summary>
/// 计算1，1，2，3，5，8，13，21，34数列的第n位的值
/// </summary>
/// <param name="n">第n位</param>
/// <param name="nOne">第一位的值</param>
/// <param name="nTwo">第二位的值</param>
/// <returns>第n位的值</returns>
public int Fib(int n, int nOne, int nTwo)
{
for (int i = 2; i < n; i++)
{
nTwo += nOne;
nOne = nTwo - nOne;
}
return n == 1 ? nOne : nTwo;
}

Answer 7

这也能推荐？
递归的有人写了，我写个非递归的        int Fib(int count)
        {
            int[] arr = new int[2];
            for (int i = 1; i <= count; i++)
            {
                if (i == 1 || i == 2)
                    arr[1] = arr[0] = 1;
                else
                {
                    arr[1] = arr[0] + arr[1];
                    arr[0] = arr[1] - arr[0];
                }
            }
            return arr[1];
        }

Answer 8

貌似为高精度问题，64位整数第93个数开始越位。
复杂度可以为log(n)，用线性代数知识求解。

Answer 9

        /// <summary>
        /// 计算1，1，2，3，5，8，13，21，34数列的第n位的值
        /// </summary>
        /// <param name="n">第n位</param>
        /// <param name="nOne">第一位的值</param>
        /// <param name="nTwo">第二位的值</param>
        /// <returns>第n位的值</returns>
        public int Fib(int n, int nOne, int nTwo)
        {
            for (int i = 2; i < n; i++)
            {
                nTwo += nOne;
                nOne = nTwo - nOne;
            }
            return nTwo;
        }    这样编程太复杂，可以简化！

Answer 10

public int fun(int n)
{
    if(n==1 || n==2)
        return 1;
    else
        return fun(n-1)+fun(n-2);
}

Answer 11

斐波那契数列也能被推荐？.NET版的耻辱...

Answer 12

如果用递归的话,一定要加上hash,否则算第100位会超时。另外还要注意不能用int,第94项就会超过ulong的范围了，需要大数运算或用数组模拟。

Answer 13

fib(int n) 
  { 
      if(n=1||n=2) 
          return 1; 
      else 
          return fib(n-1)+fib(n-2) 
  } 
费波拿切数列 
就是这样！

Answer 14

看了一下 大家给的递归算法效率是很低的
最好的递归解法是这个int Fib(int n)
{
 return AdditiveSequence(n,0,1);
}
int AdditiveSequence(int n,int t0,int t1)
{
 if(n==0)return(t0);
 if(n==1)return(t1);
 return AdditiveSequence(n-1,t1,t0+t1);
}

Answer 15

不需要加int 吧 不加默认就是int

Answer 16

fib(int n) 
  { 
      if(n=1||n=2) 
          return 1; 
      else 
          return fib(n-1)+fib(n-2) 
  } 
费波拿切数列就是这样啊 

Answer 17

fib(int n) 
  { 
      if(n=1||n=2) 
          return 1; 
      else 
          return fib(n-1)+fib(n-2) 
  } 

Answer 18

int a=1,b=1,n;
 public int fangfa(n)
{
 for(int i=1;i<=n;i++)
   {
     a=a+b;
     b=a+b;
   }
return b;
}
说明：调用两次 fangfa()分别让n设为14和49，得到返回的两个结果就分别是第30位和第100位上的数。