我对课堂作业有疑问,我需要知道如何使用迭代返回斐波那契数列的第 n 个数(不允许递归)。
我需要一些关于如何执行此操作的提示,以便我可以更好地理解我做错了什么。我在我的program.cs中输出到控制台,因此它在下面的代码中不存在。
// Q1)
//
// Return the Nth Fibonacci number in the sequence
//
// Input: uint n (which number to get)
// Output: The nth fibonacci number
//
public static UInt64 GetNthFibonacciNumber(uint n)
{
// Return the nth fibonacci number based on n.
if (n == 0 || n == 1)
{
return 1;
}
// The basic Fibonacci sequence is
// 1, 1, 2, 3, 5, 8, 13, 21, 34...
// f(0) = 1
// f(1) = 1
// f(n) = f(n-1) + f(n-2)
///////////////
//my code is below this comment
uint a = 0;
uint b = 1;
for (uint i = 0; i < n; i++)
{
n = b + a;
a = b;
b = n;
}
return n;
:)
static ulong Fib(int n)
{
double sqrt5 = Math.Sqrt(5);
double p1 = (1 + sqrt5) / 2;
double p2 = -1 * (p1 - 1);
double n1 = Math.Pow(p1, n + 1);
double n2 = Math.Pow(p2, n + 1);
return (ulong)((n1 - n2) / sqrt5);
}
只是为了一点乐趣,你可以使用无限的斐波那契列表和一些 IEnumerable 扩展来做到这一点
public IEnumerable<int> Fibonacci(){
var current = 1;
var b = 0;
while(true){
var next = current + b;
yield return next;
b = current;
current = next;
}
}
public T Nth<T>(this IEnumerable<T> seq, int n){
return seq.Skip.(n-1).First();
}
得到第n个数字就是
Fibonacci().Nth(n);
public static int GetNthFibonacci(int n)
{
var previous = -1;
var current = 1;
int index = 1;
int element = 0;
while (index++ <= n)
{
element = previous + current;
previous = current;
current = element;
}
return element;
}
我认为这应该可以解决问题:
uint a = 0;
uint b = 1;
uint c = 1;
for (uint i = 0; i < n; i++)
{
c = b + a;
a = b;
b = c;
}
return c;
public IEnumerable<BigInteger> FibonacciBig(int maxn)
{
BigInteger Fn=1;
BigInteger Fn_1=1;
BigInteger Fn_2=1;
yield return Fn;
yield return Fn;
for (int i = 3; i < maxn; i++)
{
Fn = Fn_1 + Fn_2;
yield return Fn;
Fn_2 = Fn_1;
Fn_1 = Fn;
}
}
你可以通过
得到第n个数字 FibonacciBig(100000).Skip(n).First();
这是你作业的答案,你应该从 3 开始,因为你已经有了 f1 和 f2 的数字(前两个数字)。请注意,获取第 0 个斐波那契数是没有意义的。
public static UInt64 GetNthFibonacciNumber(uint n)
{
// Return the nth fibonacci number based on n.
if (n == 1 || n == 2)
{
return 1;
}
uint a = 1;
uint b = 1;
uint c;
for (uint i = 3; i <= n; i++)
{
c = b + a;
a = b;
b = c;
}
return c;
}
public static UInt64 GetNthFibonacciNumber(uint n)
{
if (n == 0 || n == 1)
{
return 1;
}
UInt64 a = 1, b = 1;
uint i = 2;
while (i <= n)
{
if (a > b) b += a;
else a += b;
++i;
}
return (a > b) ? a : b;
}
public static List<int> PrintFibonacci(int number)
{
List<int> result = new List<int>();
if (number == 0)
{
result.Add(0);
return result;
}
else if (number == 1)
{
result.Add(0);
return result;
}
else if (number == 2)
{
result.AddRange(new List<int>() { 0, 1 });
return result;
}
else
{
//if we got thus far,we should have f1,f2 and f3 as fibonacci numbers
int f1 = 0,
f2 = 1;
result.AddRange(new List<int>() { f1, f2 });
for (int i = 2; i < number; i++)
{
result.Add(result[i - 1] + result[i - 2]);
}
}
return result;
}
只需要 2 个变量(在 for 循环中声明一个也算)。
public int NthFib(int n)
{
int curFib = 0;
int nextFib = 1;
while (--n > 0)
{
nextFib += curFib;
curFib = nextFib - curFib;
}
return curFib;
}
如果您想查看 n 的序列,请将其更改为:
public IEnumerable<int> NthFib(int n)
{
int curFib = 0;
int nextFib = 1;
while (n-- > 0)
{
yield return curFib;
nextFib += curFib;
curFib = nextFib - curFib;
}
}
public long Fibonacci(int n)
{
int a = 0;
int b = 1;
int c = 0;
for (int i = 0; i < n; i++)
{
c = a + b;
a = b;
b = c;
}
return a;
}