05.09.2021
Zadanie "Jabłka" - najbardziej optymalne rozwiązanie
Cześć,
Dzisiaj postanowiłam rozwiązać zadanie „Jabłka”.
Oto link do zadania: https://szkopul.edu.pl/problemset/problem/jablka/site/?key=statement
Dokładnie przeanalizowałam problem i uznałam, że trzeba znaleźć wszystkie dzielniki liczby jabłek.
Można by było sprawdzać każdą liczbę, jednak złożoność czasowa tego rozwiązania to O(n). Wbrew pozorom nie jest to bardzo dużo, jednak uważam, że w tym zadaniu chodzi o coś trudniejszego, ale szybszego. Przypomniało mi się lepsze rozwiązanie dla problemów tego typu…
Rozważmy przypadek, gdy liczba jabłek wynosi 16.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Jej dzielniki to 1, 2, 4, 8 i 16. Zauważcie, że:
1 * 16 = 16
2 * 8 = 16
A czwórka nie ma pary – po prostu zostaje sama :)
Moglibyśmy szukać dzielników w inny sposób… Po prostu wystarczy dodawać jednocześnie zarówno właśnie sprawdzony dzielnik (np. 2), jak i jego parę – 16 / 2 = 8.
Czyli:
dodaj(1)
dodaj(16/1), czyli 16
dodaj(2)
dodaj(16/2), czyli 8
dodaj(4)
Chwila… Teraz 16 / 4 = 4. To nie ma sensu, prawda? 16 / 8 to 2… A dwójkę już znaleźliśmy. W związku z tym nie musimy sprawdzać dalej niż do √ 16.
Teraz złożoność naszego rozwiązania wynosi O(sqrt(n)).
Spróbujmy na innym przykładzie:
Liczba jabłek to 10.
C++ zaokrągli nam √ 10 do 3. A więc teraz wystarczy poszukać dzielników mniejszych lub równych 3:
1 2 3
dodaj(1)
dodaj(10/1), czyli 10
dodaj(2)
dodaj(10/2), czyli 5.
Jest to zarówno szybkie, jak i w miarę łatwe w implementacji rozwiązanie. Dostałam za nie 100 punktów. Mam nadzieję, że moje wytłumaczenie jest dla Was zrozumiałe :) W razie problemów napiszcie do mnie w zakładce Kontakt.
Do zobaczenia!
Oto link do zadania: https://szkopul.edu.pl/problemset/problem/jablka/site/?key=statement
Dokładnie przeanalizowałam problem i uznałam, że trzeba znaleźć wszystkie dzielniki liczby jabłek.
Można by było sprawdzać każdą liczbę, jednak złożoność czasowa tego rozwiązania to O(n). Wbrew pozorom nie jest to bardzo dużo, jednak uważam, że w tym zadaniu chodzi o coś trudniejszego, ale szybszego. Przypomniało mi się lepsze rozwiązanie dla problemów tego typu…
Rozważmy przypadek, gdy liczba jabłek wynosi 16.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Jej dzielniki to 1, 2, 4, 8 i 16. Zauważcie, że:
1 * 16 = 16
2 * 8 = 16
A czwórka nie ma pary – po prostu zostaje sama :)
Moglibyśmy szukać dzielników w inny sposób… Po prostu wystarczy dodawać jednocześnie zarówno właśnie sprawdzony dzielnik (np. 2), jak i jego parę – 16 / 2 = 8.
Czyli:
dodaj(1)
dodaj(16/1), czyli 16
dodaj(2)
dodaj(16/2), czyli 8
dodaj(4)
Chwila… Teraz 16 / 4 = 4. To nie ma sensu, prawda? 16 / 8 to 2… A dwójkę już znaleźliśmy. W związku z tym nie musimy sprawdzać dalej niż do √ 16.
Teraz złożoność naszego rozwiązania wynosi O(sqrt(n)).
Spróbujmy na innym przykładzie:
Liczba jabłek to 10.
C++ zaokrągli nam √ 10 do 3. A więc teraz wystarczy poszukać dzielników mniejszych lub równych 3:
1 2 3
dodaj(1)
dodaj(10/1), czyli 10
dodaj(2)
dodaj(10/2), czyli 5.
Jest to zarówno szybkie, jak i w miarę łatwe w implementacji rozwiązanie. Dostałam za nie 100 punktów. Mam nadzieję, że moje wytłumaczenie jest dla Was zrozumiałe :) W razie problemów napiszcie do mnie w zakładce Kontakt.
Do zobaczenia!