如何存储非常大的斐波那契数的输出? [英] How to store output of very large Fibonacci number?
问题描述
我正在编写第n个斐波那契数的程序.我使用递归和记忆创建了以下程序. 主要问题是n的值可以达到10000，这意味着10000的斐波那契数将超过2000位数长.
I am making a program for nth Fibonacci number. I made the following program using recursion and memoization. The main problem is that the value of n can go up to 10000 which means that the Fibonacci number of 10000 would be more than 2000 digit long.
通过一些谷歌搜索，我发现我可以使用数组并将解决方案的每一位存储在数组的元素中，但是我仍然无法弄清楚如何用我的程序实现这种方法.
With a little bit of googling, I found that i could use arrays and store every digit of the solution in an element of the array but I am still not able to figure out how to implement this approach with my program.
#include<iostream>
using namespace std;
long long int memo[101000];
long long int n;
long long int fib(long long int n)
{
if(n==1 || n==2)
return 1;
if(memo[n]!=0)
return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
int main()
{
cin>>n;
long long int ans = fib(n);
cout<<ans;
}
我该如何实现这种方法，或者还有另一种方法可以用来实现如此大的价值?
How do I implement that approach or if there is another method that can be used to achieve such large values?
推荐答案
我想指出的一件事是，还有其他实现fib的方法，这些方法对于C ++之类的计算来说要容易得多
One thing that I think should be pointed out is there's other ways to implement fib that are much easier for something like C++ to compute
考虑以下伪代码
function fib (n) {
let a = 0, b = 1, _;
while (n > 0) {
_ = a;
a = b;
b = b + _;
n = n - 1;
}
return a;
}
这不需要记忆，您不必担心过多的递归调用会炸毁堆栈.递归是一个非常强大的循环结构，但它是其中最好的语言之一，最好由Lisp，Scheme，Kotlin，Lua(以及其他一些语言)这样的lang来提供如此优雅的支持.
This doesn't require memoisation and you don't have to be concerned about blowing up your stack with too many recursive calls. Recursion is a really powerful looping construct but it's one of those fubu things that's best left to langs like Lisp, Scheme, Kotlin, Lua (and a few others) that support it so elegantly.
这并不是说在C ++中不可能消除尾部调用，但是除非您正在明确地对其进行优化/编译，否则我怀疑您使用的编译器默认情况下会支持它.
That's not to say tail call elimination is impossible in C++, but unless you're doing something to optimise/compile for it explicitly, I'm doubtful that whatever compiler you're using would support it by default.
对于计算非常大的数字，您必须在添加困难之道"时变得很有创意，或者依赖于
As for computing the exceptionally large numbers, you'll have to either get creative doing adding The Hard Way or rely upon an arbitrary precision arithmetic library like GMP. I'm sure there's other libs for this too.
添加困难之路™
还记得当您有点不习惯，只是从铝箔上拿出来时，您是如何添加大数字的吗?
Remember how you used to add big numbers when you were a little tater tot, fresh off the aluminum foil?
5岁的数学
1259601512351095520986368
+ 50695640938240596831104
---------------------------
?
好吧，您必须从右到左添加每一列.并且当一列溢出到两位数时，请记住将那个1携带到下一列.
Well you gotta add each column, right to left. And when a column overflows into the double digits, remember to carry that 1 over to the next column.
... <-001
1259601512351095520986368
+ 50695640938240596831104
---------------------------
... <-472第10,000个斐波纳契数长为数千个数字，因此C ++提供的任何整数都无法开箱即用.因此，无需依赖库，就可以使用字符串或单位数字的数组.要输出最终数字，您必须将其转换为字符串tho.
The 10,000th fibonacci number is thousands of digits long, so there's no way that's going to fit in any integer C++ provides out of the box. So without relying upon a library, you could use a string or an array of single-digit numbers. To output the final number, you'll have to convert it to a string tho.
( woflram alpha:fibonacci 10000 )
通过这种方式，您将执行几百万个单位的加法运算；可能要花一些时间，但是对于任何现代计算机来说，这都是一件轻而易举的事情.该去上班了！
Doing it this way, you'll perform a couple million single-digit additions; it might take a while, but it should be a breeze for any modern computer to handle. Time to get to work !
这是JavaScript中的Bignum模块的一个示例
Here's an example in of a Bignum module in JavaScript
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
b .reverse () .join ("")
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
我们可以验证上述Wolfram Alpha答案是否正确
We can verify that the Wolfram Alpha answer above is correct
const { fromInt, toString, add } =
Bignum
const bigfib = (n = 0) =>
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n > 0) {
_ = a
a = b
b = add (b, _)
n = n - 1
}
return toString (a)
}
bigfib (10000)
// "336447 ... 366875"
展开下面的程序以在浏览器中运行
Expand the program below to run it in your browser
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s) .reverse ()
, toString: (b) =>
b .reverse () .join ("")
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
const { fromInt, toString, add } =
Bignum
const bigfib = (n = 0) =>
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n > 0) {
_ = a
a = b
b = add (b, _)
n = n - 1
}
return toString (a)
}
console.log (bigfib (10000))
这篇关于如何存储非常大的斐波那契数的输出?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
