std :: map, кажется, находит элементы, которых там нет - PullRequest
Новая
       9

std :: map, кажется, находит элементы, которых там нет

0 голосов
/ 04 июня 2018

Итак, я попытался создать простую программу для вычисления n-го числа Фибоначчи mod 10^9+7, используя формулу удвоения с F[0]=0 и F[1]=1.и программа, кажется, работает на моем компьютере с компиляторами VS2010 и CodeBlocks с MinGW, однако тестирование моей программы на ideone возвращает 0 для каждого ввода.Кажется, что после первой итерации F.find (n) фактически находит элементы, которые не должны существовать.Вот мой код (в VS2010 я только что изменил включения). 

#include <bits/stdc++.h>

using namespace std;
std::map<unsigned long long,unsigned long long> F;
unsigned long long fib(unsigned long long n)
{
    if(n==-1) return 0; // Shifting index by 1
    if(n==0) return 1;
    if(n==1) return 1;
    if(F.find(n) != F.end()) return F[n]; // This seems to be the problem,
    else
    {
        if(n%2==0) //
        {
            F[n/2-1] = fib(n/2-1)%1000000007;
            F[n/2] = fib(n/2)%1000000007;
            return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;
        }
        else
        {
            F[n/2] = fib(n/2)%1000000007;
            F[n/2+1] = fib(n/2+1)%1000000007;
            return F[n] = (F[n/2]*(2*F[n/2+1]-F[n/2]))%1000000007;
        }
    }
}
int main() {
    unsigned long long int broj; 
    cin >> broj; // input the number
    cout << fib(broj-1) << endl;
    return 0;
}

Ответы [ 2 ]

0 голосов
/ 04 июня 2018

Другое возможное исправление - добавить две временные переменные, скажем, unsigned long long a,b; и изменить строки 

F[n/2-1] = fib(n/2-1)%1000000007;
F[n/2] = fib(n/2)%1000000007;

На 

a = fib(n/2-1)%1000000007;
b = fib(n/2)%1000000007;
F[n/2-1] = a;
F[n/2] = b;

Таким образом, не имеет значения, создает ли картаэлемент затем присваивает значение.Он также может оптимизировать следующую строку 

return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;

Чтобы избежать поиска F [n / 2-1] и F [n / 2] в 

return F[n] = (a*a+b*b)%1000000007;
0 голосов
/ 04 июня 2018

У вас проблема с такими выражениями: 

F[n/2-1] = fib(n/2-1)%1000000007;

, поскольку порядок вычисления operator[] для std::map не определен, он может вызвать его до fib(n/2-1) и создать там пустой элемент.Вам следует хранить кэшированное значение в функции, в которой вы его вычисляете.

Также вызов std::map::operator[] с тем же key, который вы использовали с std::map::find, расточителен.

Возможное исправление: 

   auto p = F.emplace( n, 0 );
   if( p.second ) { 
       // element was not there
       // calculate and store at p.first->second
   }
   return p.first->second;
...