Uproszczenie kodu

pytanie zadane 17 listopada 2018 w Matematyka, fizyka, logika przez Nowicjusz2018 Nowicjusz (240 p.)
otagowane ponownie 17 listopada 2018 przez Nowicjusz2018

Dzień dobry robię zadanie z platformy spoj , kod jest dobrze napisany i daje poprawny wynik problem polega na tym że za każdym razem gdy do wklejam wyskakuje błąd że "przekroczono limit czasu" czy ktoś z was może mi powiedzieć w jaki sposób go jeszcze uprościć aby jego czas został zminimalizowany do oczekiwanego minimum ? oto mój kod

#include<iostream> 
#include<cstdlib> 
#include <cmath>
#include <cstdio>
#include<stdio.h>
 
int fib(int n)
{
 
int elementA=0;
int elementB=1;
const unsigned int M = 1000000007;
int wynik;
 
if(n<2)
    return n;
 
for(int i=2;n>=i;i++){
wynik=(elementA+elementB)%M;
elementA=elementB;
elementB=wynik ;
}
return wynik ;
 
}
 
int main()
{
 

int n;
int ile;
scanf("%i",&ile);
 
if(ile>100)
     return 100;
 
for(int i=0;ile>i;i++){
   scanf("%i",&n);
 
    std::cout<< fib(n)<<'\n';
    }
 return 0;
 
}

komentarz 17 listopada 2018 przez niezalogowany

Może jakiś link do zadania? Zmień kategorię na SPOJ.

2 odpowiedzi

odpowiedź 17 listopada 2018 przez jankustosz1 Nałogowiec (35,880 p.)

Rozumiem że zadanie polega na tym że dostajesz n zapytań o k'tą liczbę w ciągu fibonaciego.

Ty za każdym zapytaniem liczysz wszystko od nowa i aż dojedziesz poszukiwanej przez Ciebie liczby. Potem dostajesz nowe zapytanie i znowu liczysz wszystko od nowa.

Optymalizacja polega na tym że nie liczysz za każdym wszystkiego od nowa, a liczysz fibonaciego raz na samym początku do maksymalnego możliwego zapytania i zapisujesz sobie wyniki w tablicy. Dzięki temu jak dostaniesz zapytanie o k'ty wynik to po prostu wypisujesz k'ty element tablicy.

Jeżeli maksymalna możliwa wartość w zapytaniu jest większa od 10^7 to rozwiązanie jest jeszcze inne i opiera się macierzach, ale raczej w to wątpię.

komentarz 17 listopada 2018 przez Nowicjusz2018 Nowicjusz (240 p.)

Mój problem polega na tym że SPOJ podaje mi informację że przekroczono limit czasu . Wiesz może jak temu zaradzić ?

komentarz 17 listopada 2018 przez jankustosz1 Nałogowiec (35,880 p.)

ale wrzuciłeś tą optymalizację którą napisałem?

odpowiedź 17 listopada 2018 przez Nowicjusz2018 Nowicjusz (240 p.)

https://www.spoj.com/WWSIASD/problems/FIBONUMS/

oto link na spoja z tym dokładnie zadaniem

komentarz 17 listopada 2018 przez jankustosz1 Nałogowiec (35,880 p.)

No dobra to rozwiązanie jest trochę skomplikowane i musisz to sobie rozpisać aby ogarnąć.

1) Zauważ, że jak weźmiesz sobie macierz 1x2 zawierającą dwie kolejne liczby z ciągu fibonacciego i macierz 2x2 zbudowaną w taki sposób:

0 1
1 1

i pomnożysz je przez siebie otrzymasz macierz zawierającą liczbę fibonacciego w twojej pierwszej macierzy i kolejną liczbę fibonacciego po niej.

2) Jak pomnożysz przez to macierz 2 razy to otrzymasz jeszcze następną itd. Dlatego to rozwiązanie sprowadza się do szybkiego potęgowania tej macierzy którą napisałem gdzie wykładnikiem jest zapytanie. I następnie wymnożenie macierzy.

Złożoność tego to będzie: T * 2^2 * log Ni (dzięki szybkiemu potęgowaniu)

czyli w najgorszym przypadku 400 * log 10^9

czyli około 12000 jeżeli niczego nie pominąłem