如何递归计算第n个斐波那契数? (使用数组) [英] How do i calculate n-th fibonacci number recursively ? (using arrays)

问题描述

我需要编写一个使用C ++计算第n个斐波那契数的程序.结果(第n个斐波那契数)将最大为128位，我必须使用int数组来解决此问题.我已经做过使用数组计算第n个斐波那契数的部分.我定义了3个数组来解决问题:

I need to write a program that computes the nth Fibonacci number using C++. The result (nth Fibonacci number) will be maximum 128bit and I have to use int arrays to solve the problem. I already did the part that computes the nth fibonacci number using arrays. I defined 3 arrays to solve the problem:

// digits of a number are stored in array.
...
unsigned int fib1[100];
unsigned int fib2[100];
unsigned int result[101];
...

结果是fib1和fib2的总和；例如[2,1] + [3,4] = [5,5](21 + 34 = 55)

但是现在我需要编写另一个程序来递归地计算第n个斐波那契数.我真的不知道该如何对128位数字执行此操作.有什么办法可以重新实现我的代码来解决此问题?

还是有人有其他想法?

PS:不允许使用长双精度"类型或任何准备好的库，例如TTmath或GMP.

result is the summation of fib1 and fib2; for example [2,1] + [3,4] = [5,5] (21+34=55)

But now I need to write another program that computes the nth Fibonacci number recursively. I really don''t know how to do that for 128bit numbers. Is there any way to reimplement my code to solve this problem?

Or anyone has another idea?

PS : I am not allowed to use "long double" type or any prepared library like TTmath or GMP.

推荐答案

如果您在Internet上搜索 c ++递归斐波那契，您会找到很多解决方案.

相比这里要快！

If you do an internet search for c++ recursive fibonacci you will find lots of solutions.

Which would have been quicker than asking here!

自己编写它甚至更快.只需遵循裸定义并使用循环，无需递归.糟糕！您说递归".好的，然后使用递归.
任何类型都可以，对于算法来说并不重要.

不要浪费时间在寻找确切的实现上，只需使用第一个原则: http://en.wikipedia.org/wiki/Fibinochi_numbers [ ^ ](我想您已经知道了，但是请看).
顺便说一句，请遵循以下提示:您实际上并不需要数组，除非您需要返回0..N斐波那契数字的数组，而不是放在第一位的第N个斐波那契数字.

如果您使用长双精度的实现，只需更改以键入128位整数或您喜欢的其他任何类型即可:算法不应更改.

—SA

It''s even faster to write it on your own. Just follow the bare definition and use the loop, no recursion. Oops! You say "recursive". OK then, use recursion.
Any type is fine, it does not really matter for the algorithm.

Instead of wasting time on finding exact implementation, use just first principles: http://en.wikipedia.org/wiki/Fibinochi_numbers[^] (I think you already know that, but take a look).
By the way, take this hint: you don''t really need an array, unless you''re required to return the array of 0..N Fibonacci numbers, not N-th Fibonacci number as you put it in first place.

If you have the implementation with long double, just change to type the 128-bit integer or any other at your liking: the algorithm should not change.

—SA

这篇关于如何递归计算第n个斐波那契数? (使用数组)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！