问题描述
#include<iostream>using namespace std;double fib(int n) ; int main(){ int n; cin>>n; double a[20000]; for(int i=0;i<n;i++)cin>>a[i]; double b[20000]; for(int j=0;j<n;j++){ for(int i=0;i<100003;i++) {if(fib(i)>a[j]){ b[j]=fib(i-1); break;} }} for(int i=0;i<n;i++)cout<<b[i]<<endl; return 0; }double fib(int n) { int result[2] = {0,1}; if(n < 2) return result[n]; double fibOne = 0; double fibTwo = 1; double fibN = 0; int i = 0; for(i = 2; i <= n; i++) { fibN = fibOne + fibTwo; fibOne = fibTwo; fibTwo = fibN; } return fibN; }
问题解答
回答1：应该是矩阵+快速幂！
回答2：如果你问的是c++，我觉得优化的余地大概是把cin，cout换成scanf，printf，或者用模板在编译期完成计算。
但是这题显然要的是语言层面以外的优化，方法就是楼上说的矩阵快速幂，不过sicp上还有一个看起来很玄学的fibonacci算法，有兴趣可以看看:-)
回答3：楼上都是瞎说 这题其实考的是二分搜索hehe~
－－－－－－－－－－－－－－分割线－－－－－－－－作为一个后端的nodejs新手 我决定用lua来实现给你看
local MAX = 48 -- 我是渣渣看错2^32 和10^32次了local MIN = 1local fib = {}fib[1] = 1fib[2] = 1local ifor i=3, MAX do fib[i] = fib[i-1] + fib[i-2]endfunction fibFloor(x, max, min) if max == min+1 thenreturn fib[min] elselocal mid = math.floor((max+min)/2)if (fib[mid] > x) then return fibFloor(x, mid, min)elseif (fib[mid] == x) then return fib[mid]else --if (fib[mid] < x) then return fibFloor(x, max, mid)end endendlocal n = io.read('*num')for i=1, n do local x = io.read('*num') print(fibFloor(x, MAX, MIN))end
看了楼下答案以后默默把MAX改成48...
回答4：c++14可以用constexpr + array + index_sequence直接生成fib数组,然后用lower_bound查询就行了。
#include <iostream>#include <algorithm>#include <array>#include <type_traits>#include <iterator>#include <utility>using namespace std;constexpr uint64_t fib(size_t n) noexcept{ if (n < 2) return n; return fib(n - 1) + fib(n - 2);}template<typename F, size_t ... I>constexpr auto make_array(F&& f, index_sequence<I...>) noexcept{ return array<result_of_t<F(size_t)>, sizeof...(I)>{ f(I)... };}constexpr auto fib_arr = make_array(fib, make_index_sequence<94>());int main(){ transform(istream_iterator<size_t>(cin), istream_iterator<size_t>(), ostream_iterator<size_t>(cout, 'rn'), [&](auto v) { auto i = lower_bound(begin(fib_arr), end(fib_arr), v); return *i == v? v: i != fib_arr.begin()? *(i - 1): fib_arr.back(); }); return 0;}回答5：
你用double干什么 double是浮点数 浮点运算慢啊
长的整型用long long
回答6：你用了int，而int最大只能到2^31 - 1于是遇到些奇怪的m值的话，你算出来的fib会不断溢出成负数，然后死循环。
既然1 <= n <= 20000，你先把它们全算出来，硬编进源码里，要用时二分搜索就行了。（楼上那些constexpr之类的高级技巧，本质上也是这样干，不过是由编译器在编译时代劳了……）
当然，再进阶一点的话，你可以用n = log(m * sqrt(5)) / log((sqrt(5) + 1) / 2)作为搜索起点。因为fib(n) = round(((sqrt(5) + 1) / 2)^m / sqrt(5))
但其实上面这些都没甚么意义，因为fib(48) = 4,807,526,976，已经比2^32大了。所以其实你只需要unsigned int[48]，根本不需要20000位。你甚至可以硬编码出一堆if else来做这题……
