算法 - 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來做這題…