这样一个数列：0、1、1、2、3、5、8、13、21、。。。。。求第300个。。。
童鞋们，注意是第300个哦。
------解决思路----------------------
static void Fibonacci(uint idx)
{
List<BigInteger> list = new List<BigInteger>() { 0, 1 };
for (var i = 2; i <= idx; i++)
{
list.Add(list[i - 2] + list[i - 1]);
Console.WriteLine(string.Format("Index:{0} Value:{1}", i, list[i]));
}
}
------解决思路----------------------
能不用递归就不用，虽然看起来比循环简洁，逻辑明确，但是堆栈消耗太严重，我这里算第50个就要一会了。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication8
{
class Program
{
static void Main(string[] args)
{
Fibonacci();
Console.ReadKey();
}
static void Fibonacci()
{
HugeNumber[] hn = new HugeNumber[500];
hn[0] = new HugeNumber(0);
hn[1] = new HugeNumber(1);
for (int i = 2; i < hn.Length; i++)
{
hn[i] = hn[i - 1] + hn[i - 2];
Console.WriteLine("第{0,-4}个斐波那契数列值为{1}", i + 1, hn[i].ToString());
}
}
}
class HugeNumber
{
private const int MAXBIT = 200;
private char[] bits = new char[MAXBIT];
private int length = 0;
private HugeNumber()
{
this.bits[0] = '0';
this.length = 1;
}
public HugeNumber(int n)
{
char[] c = n.ToString().ToArray();
Array.Reverse(c);
c.CopyTo(bits, 0);
this.length = c.Length;
}
public HugeNumber(long n)
{
char[] c = n.ToString().ToArray();
Array.Reverse(c);
c.CopyTo(bits, 0);
this.length = c.Length;
}
public HugeNumber(HugeNumber n)
{
n.bits.CopyTo(this.bits, 0);
this.length = n.length;
}
protected HugeNumber(char[] bits)
{
Array.Copy(bits, 0, this.bits, 0, MAXBIT);
for (int i = 0; i < MAXBIT; i++)
{
if (bits[i] == '\0')
{
this.length = i ;
return;
}
}
this.length = MAXBIT;
}
public static HugeNumber operator +(HugeNumber l, HugeNumber r)
{
char[] c = new char[MAXBIT];
bool carry = false;
int itor = l.length > r.length ? l.length : r.length;
for (int i = 0; i < itor; i++)
{
int b = 0;
b += l.bits[i] == '\0' ? 0 : l.bits[i] - 0x30;
b += r.bits[i] == '\0' ? 0 : r.bits[i] - 0x30;
if (carry)
b++;
if (b > 9)
{
carry = true;
c[i] = (char)(b - 10 + 0x30);
}
else
{
carry = false;
c[i] = (char)(b + 0x30);
}
}
if (carry)
c[itor] = '1';
return new HugeNumber(c);
}
public override string ToString()
{
var q = from t in this.bits
where t != '\0'
select t;
char[] c = q.ToArray();
StringBuilder sb = new StringBuilder();
for (int i = c.Length; i > 0; i--)
{
sb.Append(c[i - 1]);
}
return sb.ToString();
}
}
}
------解决思路----------------------
用long好像100个以内就溢出了，主要考的是对问题考虑的全面性
网上有用二维数组来求的 http://zhidao.baidu.com/link?url=rlDA6eRarbdnvqinKd58GVhTzM2E6BWeuhA-o-8XHD91NyTEWml8LKcM3UI0qyZZfJVJw0bqTyo5kU5NxxjyuK
------解决思路----------------------
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
System.Diagnostics.Stopwatch timer =new System.Diagnostics.Stopwatch ();
timer.Start();
//代码块
Recursion();
//Loop(300);
timer.Stop();
Console.WriteLine("递归执行时间为:{0}毫秒!", timer.ElapsedMilliseconds.ToString());
System.Diagnostics.Stopwatch timer1 = new System.Diagnostics.Stopwatch();
timer1.Start();
//代码块
//Recursion();
Loop(300);
timer1.Stop();
Console.WriteLine("循环执行时间为:{0}毫秒!", timer1.ElapsedMilliseconds.ToString());
}
public static System.Numerics.BigInteger x1 = 0;
public static System.Numerics.BigInteger y1 = 1;
public static System.Numerics.BigInteger z1 = 0;
public static long iLoop = 1;
private static void Recursion()
{
if (iLoop == 1)
{
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop, x );
iLoop += 1;
}
if (iLoop == 2)
{
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop,y);
iLoop += 1;
}
else
{
z1 = x1+y1;
y1 = x1;
x1 = z1;
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop, z);
iLoop += 1;
if (iLoop == 301)
{
Console.WriteLine("当前是第{0}次,值是:{1}", iLoop-1, z1);
return;
}
}
Recursion();
}
private static void Loop(int i)
{
System.Numerics.BigInteger x = 0;
System.Numerics.BigInteger y = 1;
System.Numerics.BigInteger z = 0;
for (int iLoop = 1; iLoop < i; iLoop++)
{
if (iLoop == 1)
{
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop, x);
}
if (iLoop == 2)
{
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop, y);
}
else
{
z = x + y;
y = x;
x = z;
//Console.WriteLine("当前是第{0}次,值是:{1}", iLoop, z);
}
}
Console.WriteLine("当前是第{0}次,值是:{1}", i, z);
}
}
}
------解决思路----------------------
这题考的难道不是用矩阵法+快速幂求斐波那契数列吗
┏ ┓ ┏ ┓┏ ┓
┃f(n+2) f(n+1)┃ ┃ 1 1 ┃┃f(n+1) f(n) ┃
┃ ┃ = ┃ ┃┃ ┃
┃f(n+1) f(n) ┃ ┃ 1 0 ┃┃ f(n) f(n-1)┃
┗ ┛ ┗ ┛┗ ┛
=>
┏ ┓ ┏ ┓2┏ ┓ ┏ ┓n-1┏ ┓ ┏ ┓n-1┏ ┓ ┏ ┓n
┃f(n+2) f(n+1)┃ ┃ 1 1 ┃ ┃ f(n) f(n-1)┃ ┃ 1 1 ┃ ┃f(3) f(2)┃ ┃ 1 1 ┃ ┃ 1 1 ┃ ┃ 1 1 ┃
┃ ┃ = ┃ ┃ ┃ ┃ = ... = ┃ ┃ ┃ ┃ = ┃ ┃ ┃ ┃ = ┃ ┃
┃f(n+1) f(n) ┃ ┃ 1 0 ┃ ┃f(n-1) f(n-2)┃ ┃ 1 0 ┃ ┃f(2) f(1)┃ ┃ 1 0 ┃ ┃ 1 0 ┃ ┃ 1 0 ┃
┗ ┛ ┗ ┛ ┗ ┛ ┗ ┛ ┗ ┛ ┗ ┛ ┗ ┛ ┗ ┛
一个整数的快速幂例子，时间复杂度O(logn)
uint pow(uint x,uint n)
{
uint r=1;
while(n>0)
{
if((n&1)!=0) r*=x;
x*=x;
n>>=1;
}
return r;
}
最后用矩阵法+快速幂求斐波那契数列
public static BigInteger fib(BigInteger n)
{
BigInteger[,] dat=new BigInteger[,]{{1,1},{1,0}};
BigInteger[,] ret=new BigInteger[,]{{1,0},{0,1}};
while(n>0)
{
if((n&1)!=0)
{
ret=new BigInteger[,]
{
{
ret[0,0]*dat[0,0]+ret[0,1]*dat[1,0],
ret[0,0]*dat[0,1]+ret[0,1]*dat[1,1]
},
{
ret[1,0]*dat[0,0]+ret[1,1]*dat[1,0],
ret[1,0]*dat[0,1]+ret[1,1]*dat[1,1]
}
};
}
dat=new BigInteger[,]
{
{
dat[0,0]*dat[0,0]+dat[0,1]*dat[1,0],
dat[0,0]*dat[0,1]+dat[0,1]*dat[1,1]
},
{
dat[1,0]*dat[0,0]+dat[1,1]*dat[1,0],
dat[1,0]*dat[0,1]+dat[1,1]*dat[1,1]
}
};
n>>=1;
}
return ret[1,1];
}
第300位是
137347080577163115432025771710279131845700275212767467264610201
测试第1000000位计算用时12.166秒
------解决思路----------------------
修正一下：MyBigInteger类中的ToString方法中加个if，但刚才的结果没错
public override string ToString()
{
StringBuilder sb = new StringBuilder(numList[0].ToString());
for (int i = 1; i < numList.Count - 1; i++)
{
sb.Insert(0, string.Format("{0:000000000000000000}", numList[i]));
}
if (numList.Count > 1)
sb.Insert(0, numList[numList.Count - 1]);
return sb.ToString();
}