算法 - 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

It should be matrix + fast power!

Answer 2

If you are asking about C++, I think the room for optimization is to replace cin and cout with scanf and printf, or use templates to complete calculations at compile time.

But this question obviously requires optimization beyond the language level. The method is the matrix fast power mentioned above. However, there is also a fibonacci algorithm on sicp that looks very metaphysical. If you are interested, you can take a look:-)

Answer 3

The people above are all talking nonsense. This question actually tests binary search hehe~

-------------Dividing line--------
As a back-end nodejs newbie, I decided to use lua to implement it for you to see

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

After reading the answer below, I silently changed MAX to 48...

Answer 4

C++14 can use constexpr + array + index_sequence to directly generate the fib array, and then use lower_bound to query.

#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

What are you using double for? Double is a floating point number
Floating point operations are slow

For long integers use long long

Answer 6

You used int, and int can only reach a maximum of 2^31 - 1
So if you encounter some strange m value, the fib you calculated will continue to overflow into a negative number, and then loop endlessly.

Since 1 <= n <= 20000, you can calculate them all first, hard-code them into the source code, and just use binary search.
(The advanced techniques like constexpr above are essentially the same thing, but the compiler does the work during compilation...)

Of course, if you want to get a little more advanced, you can use n = log(m * sqrt(5)) / log((sqrt(5) + 1) / 2) as the starting point for your search.
Becausefib(n) = round(((sqrt(5) + 1) / 2)^m / sqrt(5))

But in fact, all of the above are meaningless, because fib(48) = 4,807,526,976, which is already larger than 2^32.
So actually you only need unsigned int[48], and you don’t need 20000 bits at all.
You can even hardcode a bunch of if elses to do this question...