写错了的斐波那契数列有关问题

写错了的斐波那契数列问题
原题地址：

http://www.51nod.com/question/index.html#!questionId=378

没找到太好的办法，难不成只能用n*log(n)的枚举？

[解决办法]
一直在刷题解，可惜还没出来，看过的人似乎也是枚举，要不你读读他们的程序？
[解决办法]

探讨

枚举的话就不用看了，我一般只喜欢讨论思路，程序不咋写

[解决办法]
提供个思路，楼主看对不对，供参考：
斐波那契数列本身是递增数列，f(n+2) = f(n+1) + f(n)
而，数列相邻元素之间的差也是斐波那契额数列，令p(n) = f(n+1) -f(n),则p(n+2) = p(n+1) + p(n)
如果某一项算错了，则差也是有规律的，比如f(4)=f(2)+f(3)=1+2时更新值错了，则原本的2+3变为1+3，总值减少1，下一步再错，总值又减少2
题目中给出了步长n，可以得到一个数组，即每一步算错之后最后值减少的额度

因为，为了算出最少的出错数，只要根据步长n，从后向前面推就好了，一旦符合要求，就停止然后输出
[解决办法]
斐波那契数列的很好的解决方式是矩阵解法，是采用的二分思想。
这个你可以到网上百度下，有很多代码和思路可以借鉴。算法复杂度是O(8*logn),8是系数，复杂度是O(logn)。
[解决办法]
n logn的算法是什么思路的?
只想到 穷举

曾经想过 用矩阵来.
正常的用矩阵(2*2)
T,错误的用F.
大致是 在一系列连乘T,若干个T被置换成F.
比较坑的是矩阵没有交换律.不知道这个怎么化简.

另一个思路是
错误的情况相当于在正常赋值后,
再把F(n + 1),F(n)置换了.
这个没什么思路.

[解决办法]

探讨

n logn的算法是什么思路的?
只想到 穷举

[解决办法]

探讨

提供个思路，楼主看对不对，供参考：
斐波那契数列本身是递增数列，f(n+2) = f(n+1) + f(n)
而，数列相邻元素之间的差也是斐波那契额数列，令p(n) = f(n+1) -f(n),则p(n+2) = p(n+1) + p(n)
如果某一项算错了，则差也是有规律的，比如f(4)=f(2)+f(3)=1+2时更新值错了，则原本的2+3变为1+3，总值减少1，下一步再错，总值又减……

查看更多 下一篇