Optymalizacja algorytmu na ciąg Fibonacciego (zadanie Drabina)

0

Witam!
Z racji tego, że jest to mój pierwszy post to przy okazji chciałbym się przywitać :)

Mam problem z optymalizacją dosyć banalnego zadania. Link poniżej:
http://main.edu.pl/pl/archive/ilocamp/2011/dra

W dwóch ostatnich testach wyrzuca mi przekroczenie limitu czasu. Rozwiązanie jest prawdopodobnie łatwe, ale jakoś nie mogę na nie wpaść.

PS 1 Przepraszam, jeśli popełniłem jakieś rażące błędy w kodzie. Dopiero się uczę.
PS 2 Jeśli zły dział to proszę moda o przeniesienie.

5

Na pierwszy rzut oka:

  1. Czytasz p jako double mimo że to inty...
  2. Powiązane z poprzednim: masz tam do policzenia 2p a nie dowolną potęgę! Potęgi dwójki liczy sie dużo prościej i szybciej za pomocą przesunięć bitowych. Kompilator moze i by taką optymalizcję ogarnął, ale nie dajesz mu szansy przez te double ;] Anyway:
power = 1<<p[k];
  1. Skoro testów jest do miliona a p jest w zakresie 1..30 to grzechem jest liczenie tego powera za każdym razem od nowa. Czemu nie policzysz raz i nie zapiszesz sobie w tablicy po prostu wyników power dla każdej liczby od 1 do 30?
    Więc jak zrobisz sobie na początku programu coś takiego:
    unsigned int powers[30];
    for(int i=1;i<=30;i++){
        powers[i-1] = 1<<i;
    }

A potem w kodzie
power = powers[p[k]];
To przyspieszy ;)

0

Wielkie dzięki za pomoc. Double wynikało z quick fixa, którego robiłem na szybko i nie zwróciłem potem na niego uwagi. Po twoich modyfikacjach algorytm faktycznie przyspiesza, jednakże niewystarczająco. Problemem jest chyba ilość iteracji - w najgorszym przypadku 1062. Spróbuję jeszcze coś pokombinować :)

0

No ale z czym tu kombinować? Algorytmów szybkiego liczenia fibonacciego jest przecież bardzo dużo. Popatrz szczególnie na potęgowanie macierzy bo można potęgować modulo.

1

Co do algorytmu.
Nie jest to najlepsza metoda liczenia ciągu Fibonacciego. Złożoność o(s) IMO to za dużo.
Da się wycisnąć o(log s), poczytaj na wiki jakie właściwości ma ten ciąg, a odnajdziesz rekurencyjną optymalizację.
Dodatkowo dla przyspieszania wpisz twardo kilka (np 200) początkowych wartości ciągu modulo 2^32, do tego napisz sobie jakiś program, który wygeneruje taką tablicę.

Tyle powinno wystarczyć by zaliczyć zadanie. Walcząc o wynik powinieneś pomyśleć o optymalizacji IO (niestety to jest jedno z tych zadań, w którym IO ma istotny wpływ na wynik końcowy).

1

Znalazłem już rozwiązanie. Chodzi o to, żeby na początku policzyć pierwszy milion wartości ciągu modulo 230 i zapisać to do tablicy, a potem dla każdego przypadku policzyć modulo 2p z odpowiedniej wartości z tablicy. Nie jest to może demon szybkości, ale przechodzi. Dziękuję wszystkim za wkład.

1 użytkowników online, w tym zalogowanych: 0, gości: 1