什么是斐波那契数列？经典数学问题之一；斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……想必看到这个数列大家很容易的就推算出来后面好几项的值，那么到底有什么规律，简单说，就是前两项的和是第三项的值，用递归算法计第50位多少。
这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列：｛1,1,2,3,5,8,13,21...｝
递归算法，耗时最长的算法，效率很低。
|
1
2
3
4
5
6
|
public static long CalcA(int n)
{
if (n <= 0) return 0;
if (n <= 2) return 1;
return checked(CalcA(n - 2) + CalcA(n - 1));
}
|
通过循环来实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static long CalcB(int n)
{
if (n <= 0) return 0;
var a = 1L;
var b = 1L;
var result = 1L;
for (var i = 3; i <= n; i++)
{
result = checked(a + b);
a = b;
b = result;
}
return result;
}
|
通过循环的改进写法
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static long CalcC(int n)
{
if (n <= 0) return 0;
var a = 1L;
var b = 1L;
for (var i = 3; i <= n; i++)
{
b = checked(a + b);
a = b - a;
}
return b;
}
|
通用公式法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
/// <summary>
/// F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long CalcD(int n)
{
if (n <= 0) return 0;
if (n <= 2) return 1; //加上，可减少运算。
var a = 1 / Math.Sqrt(5);
var b = Math.Pow((1 + Math.Sqrt(5)) / 2, n);
var c = Math.Pow((1 - Math.Sqrt(5)) / 2, n);
return checked((long)(a * (b - c)));
}
|
其他方法
|
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
using System;
using System.Diagnostics;
namespace Fibonacci
{
class Program
{
static void Main(string[] args)
{
ulong result;
int number = 10;
Console.WriteLine("************* number={0} *************", number);
Stopwatch watch1 = new Stopwatch();
watch1.Start();
result = F1(number);
watch1.Stop();
Console.WriteLine("F1({0})=" + result + " 耗时：" + watch1.Elapsed, number);
Stopwatch watch2 = new Stopwatch();
watch2.Start();
result = F2(number);
watch2.Stop();
Console.WriteLine("F2({0})=" + result + " 耗时：" + watch2.Elapsed, number);
Stopwatch watch3 = new Stopwatch();
watch3.Start();
result = F3(number);
watch3.Stop();
Console.WriteLine("F3({0})=" + result + " 耗时：" + watch3.Elapsed, number);
Stopwatch watch4 = new Stopwatch();
watch4.Start();
double result4 = F4(number);
watch4.Stop();
Console.WriteLine("F4({0})=" + result4 + " 耗时：" + watch4.Elapsed, number);
Console.WriteLine();
Console.WriteLine("结束");
Console.ReadKey();
}
/// <summary>
/// 迭代法
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
private static ulong F1(int number)
{
if (number == 1 || number == 2)
{
return 1;
}
else
{
return F1(number - 1) + F1(number - 2);
}
}
/// <summary>
/// 直接法
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
private static ulong F2(int number)
{
ulong a = 1, b = 1;
if (number == 1 || number == 2)
{
return 1;
}
else
{
for (int i = 3; i <= number; i++)
{
ulong c = a + b;
b = a;
a = c;
}
return a;
}
}
/// <summary>
/// 矩阵法
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
static ulong F3(int n)
{
ulong[,] a = new ulong[2, 2] { { 1, 1 }, { 1, 0 } };
ulong[,] b = MatirxPower(a, n);
return b[1, 0];
}
#region F3
static ulong[,] MatirxPower(ulong[,] a, int n)
{
if (n == 1) { return a; }
else if (n == 2) { return MatirxMultiplication(a, a); }
else if (n % 2 == 0)
{
ulong[,] temp = MatirxPower(a, n / 2);
return MatirxMultiplication(temp, temp);
}
else
{
ulong[,] temp = MatirxPower(a, n / 2);
return MatirxMultiplication(MatirxMultiplication(temp, temp), a);
}
}
static ulong[,] MatirxMultiplication(ulong[,] a, ulong[,] b)
{
ulong[,] c = new ulong[2, 2];
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
c[i, j] += a[i, k] * b[k, j];
}
}
}
return c;
}
#endregion
/// <summary>
/// 通项公式法
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
static double F4(int n)
{
double sqrt5 = Math.Sqrt(5);
return (1/sqrt5*(Math.Pow((1+sqrt5)/2,n)-Math.Pow((1-sqrt5)/2,n)));
}
}
}
|
OK，就这些了。用的long类型来存储结果，当n>92时会内存溢出。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://www.jianshu.com/p/31b783e3eb46