算法 - C++一直超时，如何优化

Question

#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;  
}  

Answer 1

应该是矩阵+快速幂！

Answer 2

如果你问的是c++，我觉得优化的余地大概是把cin，cout换成scanf，printf，或者用模板在编译期完成计算。

但是这题显然要的是语言层面以外的优化，方法就是楼上说的矩阵快速幂，不过sicp上还有一个看起来很玄学的fibonacci算法，有兴趣可以看看:-)

Answer 3

楼上都是瞎说 这题其实考的是二分搜索hehe~

－－－－－－－－－－－－－－分割线－－－－－－－－
作为一个后端的nodejs新手 我决定用lua来实现给你看

local MAX = 48 -- 我是渣渣看错2^32 和10^32次了
local MIN = 1

local fib = {}
fib[1] = 1
fib[2] = 1
local i
for i=3, MAX do
    fib[i] = fib[i-1] + fib[i-2]
end

function fibFloor(x, max, min)
    if max == min+1 then
        return fib[min]
    else
        local 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
    end
end

local n = io.read("*num")
for i=1, n do
    local x = io.read("*num")
    print(fibFloor(x, MAX, MIN))
end

看了楼下答案以后默默把MAX改成48...

Answer 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, "\r\n"), [&](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;
}

Answer 5

你用double干什么 double是浮点数
浮点运算慢啊

长的整型用long long

Answer 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来做这题……