什么是斐波那契數列？經典數學問題之一；斐波那契數列，又稱黃金分割數列，指的是這樣一個數列：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
