Siema. Jestem tu nowy i rozwiazalem raptem kilka zadan. Z NWD mam jednak problem - kod dziala poprawnie ale przekraczam limit czasu. Ktos jest w stanie pokazac gdzie moglbym cos zoptymalizowac?
UWAGA! Nie prosze o rozwiazanie, tylko linie kodu do ptymalizacji 
Feb '17
May '17
Dane wejściowa A może być zerem . Co robi twój program w takim przypadku ?
Dane wejściowa B może być zerem -- wtedy mój program wypisuje 0 - choć nie wiem czy taki przypadek jest w testach .
Są sposoby na optymalizację wyszukiwania dzielnika . Jedną z metod jest ograniczenie się do liczb mniejszych niż pierwiastek z danej liczby .
Dla maksymalnych danych A=1 milion , B = 1 Milion Twój program wykonuje 2 miliony dzieleń . Jak autor zadania był złośliwy to dał powiedzmy 10000 liczb poprzedzających milion jako dane wejściowe i na tym poległo twoje dzieło . Jak będziesz wyszukiwać wśród liczb nie większych niż pierwiastek z mniejszej liczby zaoszczędzisz bardzo dużo czasu .
Przykładowo dla danych wejściowych A=1 Milion , B=1 Milion wystarczy wykonać tylko 2 tysiące dzieleń .
Możesz iść jeszcze bardziej za ciosem i raz z tablicować wyniki ( dzielniki ) dla każdej możliwej liczby na wejściu ( 1..1'000'000 ) . Po takiej operacji znalezienie NWD sprowadza się do wyszukania pierwszego wsólnego ( takiej samej liczby ) elementu na dwóch listach pod indeksem A i B .
Dzięki za porady. Zaimplementowałem przypadki z zerami.
Dodałem jeszcze linijkę kodu, która dzieli większą liczbę przez mniejszą. Jeśli reszta to 0, funkcja zwraca mniejszą liczbę. To też uniknięcie masy dzielenia.
Mam jeszcze wątpliwości do punktu 3. Jeśli wpisze liczby 50 i 15, gdzie nwd to 5, otrzymuje wynik 1. To dlatego, że sqrt(15) = 3,8 = 3. Pętla nigdy nie dotrze do 5 - przynajmniej nie w tym przypadku. Robiąc to moim sposobem uzyskałem poprawny wynik.
@EDIT
Rozwiązałem problem. Zrobiłem pętlę która zaczyna w i=a/2 (czyli mniejsza liczba dzielona na 2) i kończy na 1. Przy pierwszym przypadku gdzie obie reszty to 0, dałem break.
Jak dzielisz 15 przez 3 to otrzymujesz liczbę 5 . Żeby znaleść wszystkie dzielniki danej liczby postepujesz tak :
1. Tworzysz listę małych liczb pierwszych ( w tym zadaniu wystarczą liczby od 2 do 997 )
2. W pętli sprawdzasz czy liczba X dzięki się przez kolejne liczby pierwsze ( ale nie większe od pierwiastka z X ) .
3. Jeżeli znalazłeś dzielnik to dodajesz go do listy dzielnikow liczby X, dzielisz X przez ten dzielnik i jeżeli jest liczba pierwsza też dodajesz do listy . Jeżeli nie szukasz dalej sprawdzając czy po podzieleniu X nie jest mniejsze od liczby przez którą dzielisz .
Jeżeli tak jest wyskakujesz z pętli ( żeby zaoszczędzić czas ).
4. Tym sposobem dla 15 otrzymasz liczby 3 i 5 , a dla 50 = 2 , 5 , 5 . Pierwsza wspólna liczba to 5 na obu listach .
Byłeś blisko ale trzeba innego trochę podejścia od twojego
1: przechowuj wszystko w tablicy
2: używaj ++i zamiast i++
3: tworzysz za dużo zmiennych, za dużo niepotrzebnych przeskoków. Jeden krótki if/else trwa bardzo krótko, a że kodu jest trochę więcej / powtarza się - shit happens, najważniejsze, że działa szybko, oraz jest względnie czytelne.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| MBPROB01 - History version in plaintext pl.spoj.com | Zbiór zadań | 6 | 168 | Jul '24 |
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 89 | Apr 2 |
| PP0504B - StringMerge - w języku C | Zbiór zadań | 5 | 200 | Jun '24 |
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 137 | Feb 1 |
| TOPSORTL - Porządek leksykograficzny w grafie | Zbiór zadań | 3 | 140 | Jul '24 |
