C# 中的斐波那契数列

王林
发布: 2024-09-03 15:34:44
原创
747 人浏览过

C#中的斐波那契数列斐波那契数列是著名的数列数列之一。序列是 0, 1, 1, 2, 3, 5, 8…。斐波那契数列从零和一开始,下一个数字是前两个数字的总和。据说斐波那契数列是由Leonardo Pisano Bigollo先生在13世纪创造的。斐波那契数列对于某些场景很有用。基本上它最初是用来解决兔子问题,即一对兔子出生的数量。斐波那契数列在其他问题中也很有用。

斐波那契数列逻辑

与斐波那契数列一样,该数字是其前面两个数字的总和。因此,如果我们有一个斐波那契数列,例如 0, 1, 1, 2, 3, 5, 8, 13, 21… 根据这个,下一个数字将是其前两个数字的总和,例如 13 和 21。所以下一个数字是 13 +21=34。

这是生成斐波那契数列的逻辑

F(n)= F(n-1) +F(n-2)

其中 F(n) 是术语编号,F(n-1) +F(n-2) 是前面值的总和。

所以如果我们有系列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

根据逻辑F(n)= F(n-1) +F(n-2)

F(n)= 55+89

F(n)= 144

下一学期是 144。

创建斐波那契数列的各种方法

斐波那契数列可以通过多种方式生成。

1.迭代方法

这种方式是生成系列的最简单的方法。

代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespaceFibonacciDemo
{
classProgram
{
staticint Fibonacci(int n)
{
intfirstnumber = 0, secondnumber = 1, result = 0;
if (n == 0) return 0; //It will return the first number of the series
if (n == 1) return 1; // it will return  the second number of the series
for (int i = 2; i<= n; i++)  // main processing starts from here
{
result = firstnumber + secondnumber;
firstnumber = secondnumber;
secondnumber = result;
}
return result;
}
staticvoid Main(string[] args)
{
Console.Write("Length of the Fibonacci Series: ");
int length = Convert.ToInt32(Console.ReadLine());
for(int i = 0; i< length; i++)
{
Console.Write("{0} ", Fibonacci(i));
}
Console.ReadKey();
}
}
}
登录后复制

2.递归方法

这是解决这个问题的另一种方法。

方法一

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespaceFibonacciDemo
{
classProgram
{
staticint Fibonacci(int n)
{
intfirstnumber = 0, secondnumber = 1, result = 0;
if (n == 0) return 0; //it will return the first number of the series
if (n == 1) return 1; // it will return the second number of the series
return Fibonacci(n-1) + Fibonacci(n-2);
}
staticvoid Main(string[] args)
{
Console.Write("Length of the Fibonacci Series: ");
int length = Convert.ToInt32(Console.ReadLine());
for(int i = 0; i< length; i++)
{
Console.Write("{0} ", Fibonacci(i));
}
Console.ReadKey();
}
}
}
登录后复制

方法2

using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace FibonacciSeries
{
class Program
{
public static void Fibonacci
(
int firstnumber,
int secondnumber,
int count,
int length,
)
{
if (count <= length)
{
Console.Write("{0} ", firstnumber);
Fibonacci(secondnumber, firstnumber + secondnumber, count + 1, length);
}
}
public static void Main(string[] args)
{
Console.Write("Length of the Fibonacci Series: ");
int length = Convert.ToInt32(Console.ReadLine());
Fibonacci(0, 1, 1, length);
Console.ReadKey();
}
}
}
登录后复制

输出:

C# 中的斐波那契数列

3.使用数组的斐波那契

代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class Program
{
public static int[] Fibonacci(int number)
{
int[] a = new int[number];
a[0] = 0;
a[1] = 1;
for (int i = 2; i < number; i++)
{
a[i] = a[i - 2] + a[i - 1];
}
return a;
}
public static void Main(string[] args)
{
var b = Fibonacci(10);
foreach (var elements in b)
{
Console.WriteLine(elements);
}
}
}
登录后复制

输出:

C# 中的斐波那契数列

如何求斐波那契数列的第N项?

方法如下

方法1

代码:

using System;
namespace FibonacciSeries
{
class Program {
public static int NthTerm(int n)
{
if ((n == 0) || (n == 1))
{
return n;
}
else
{
return (NthTerm(n - 1) + NthTerm(n - 2));
}
}
public static void Main(string[] args)
{
Console.Write("Enter the nth term of the Fibonacci Series: ");
int number = Convert.ToInt32(Console.ReadLine());
number = number - 1;
Console.Write(NthTerm(number));
Console.ReadKey();
}
}
}
登录后复制

上面的代码是求斐波那契数列的第n项。例如,如果我们想要查找该系列中的第 12th 项,那么结果将为 89。

方法2

(O(Log t) 时间)。

还有另一种递归公式可用于查找第 t 个斐波那契数 如果 t 是偶数则 = t/2:

F(t) = [2*F(k-1) + F(k)]*F(k)

如果 t 是奇数,则 k = (t + 1)/2

F(t) = F(k)*F(k) + F(k-1)*F(k-1)

斐波那契矩阵

求行列式后,我们将得到 (-1)t = Ft+1Ft-1 – Ft2

FmFt + Fm-1Ft-1 = Fm+t-1

通过将 t = t+1,

FmFt+1 + Fm-1Ft = Fm+t

设 m = t

F2t-1 = Ft2 + Ft-12

F2t = (Ft-1 + Ft+1)Ft = (2Ft-1 + Ft)Ft

要获得公式,我们将执行以下操作

如果 t 是偶数,则 k = t/2

如果 t 是奇数,则 k = (t+1)/2

所以通过对这些数字进行排序我们可以防止不断使用STACK的内存空间。它给出的时间复杂度为 O(n)。递归算法效率较低。

代码:

int f(n) :
if( n==0 || n==1 )
return n;
else
return f(n-1) + f(n-2)
登录后复制

现在当上述算法运行 n=4

fn(4)

f(3)             f(2)

f(2)   f(1)     f(1)   f(0)

f(1)  f(0)

所以它是一棵树。为了计算f(4),我们需要计算f(3)和f(2)等等。对于较小的值4,f(2)计算两次,f(1)计算三次。添加的数量将会大量增长。

有一个猜想,计算f(n)所需的加法次数为f(n+1) -1。

结论

这里迭代方法总是首选,因为它有更快的方法来解决此类问题。这里我们将斐波那契数列的第一个和第二个数存储在前一个数和前一个数中(这是两个变量),并且我们使用当前数来存储斐波那契数。

以上是C# 中的斐波那契数列的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!