Takmicenje iz programiranja 2017 - Kvalifikacije - 2. krug - Zadatak 2 - Trivijalan broj - Algoritamsko resenje (nije optimizovano)

Dragi takmičari,

U prilogu se nalazi algoritamsko rešenje 2. zadataka, ali potpuno neoptimizovano, ipak, najjednostavnije za razumevanje šta se zapravo traži u zadatku.

 

Organizatori takmičenja u ovom zadatku traže vremensku optimizaciju programskog koda, a za tako nešto je potrebno iskustvo, vežba, vereme i poznavanje posebnih alogoritamskih metoda, koje ćemo postepeno početi da učimo od ovog zadatka.

 

Programski kod u prilogu daje tačne rezultate za sve test primere, ali veoma sporo, tako da će osovojiti bodove samo za prva 3 test primera, odnosno 30 bodova, što se možete i sami uveriti do 28.01, tako šte ćete postaviti programski kod iz priloga na:

• https://arena.petlja.org/Competitions/Competition/171

Kako onda da naučimo vremenskiu optimizaciju?

 

Postepeno i polako. Za sam početak koristićemo recimo Excel kao pomoć da bolje uočimo neke nove sličnosti i mešusobnu zavisnost traženih brojeva u zadatku.

 

U prilogu se nalazi i Excel fajl kao pomoć pri rešanju drugog zadatka Trivijalan broj:

• Prikazani su podaci za prvih 1050 (počev od 2) brojeva u 3 kolone: X - prirodan broj (Ai),  S - zbir svih jnegovih pozitivnih delilaca i TB - trivijalnost broja X, odnosno količnih S / X (prikaz podataka u ovoj koloni je na 3 decimale, ali možete namestiti na više 5 ili 6 da bi bolje uočili razlike).
• U samom zadatku X može biti do 5 miliona, a ovde smo prikazali samo do 1050, ali je princip isti.
• Ovaj zadatak možemo da rešimo bez upotrebe nizova i relativno jednostavno, ako ne vodimo računa o vremenskoj optimizaciji, tako što ćemo za svaki broj x pronaći i sabrati sve njegove delioce, a zatim podeliti zbir sa samim brojem i taj količnik proveriti da li je manji od do tada najmanjeg (početni najmanji je 1,5 za broj 2).
• Sve promenljive su celobrojne (LongInt) osim promenljive za količnik i najmanji količnik koje su Real (ne moraju biti double). 
• Tek kada tako rešite zadatak, testirajte za nekoliko test primera i proverite sa podacima u ovoj tabelu u Excel-u (u prilogu).
• Rešenje (bez vremenske optimizacije) će verovatno proći sve test primere, međutim zbog vremenskog ograničenja, sigrno sporo, što znači da će bodove imati samo za nekoliko jednostavnih test primera (sa ne mnogo velikim brojevima).

Tek kada ovako rešite zadatak, ako imate vremena, možete da počnete da razmišljate o vremenskoj optimizaciji postepeno po sledećim koracima:

• Obratite pažnju da su svi količnici u opsegu između 1 i 4, tačnije 3,5.
• Kako se uvek kreće od broja 2, to znači da treba tražiti najmanji količnik u opsegu između 1 i 1,5.
• Obratite pažnju na cikličnu strukuturu za izračunavanje zbira delilaca ne mora da kreće od 1 i da ide do broja x, jer svaka suma u stratu ima početni zbir 1+x, jer je svaki broj deljiv sa 1 i samim sobom. Dakle brojač petlje ne ide od 1 do X, već od 2 do x-1, mada to i nije neka velika vremenska ušteda, ali u ovom slučaju nije ni zanemarljiva, jer za svaki broj x ponavljamo ovu unutrašnju petlju.
• Takođe obratite pažnju da prilikom izračunavanja zbira delilaca nema potrebe da ispitujemo da li je broj x deljiv sa brojevima koji su veći od x/2, jer sigurno nije. To znači da brojač ciklusa može da ide od 2 do x / 2, odnosno x div 2, što već donosi dvostruku uštedu u brzini rada.
• Zatim pređite na Excel fajl i posmatrajte količnije parnih i neparnih brojeva. Šta primećujete?
• Možete i da sortirate podatke po TB u rastućem redosledu, pa ponovo pregledajte sve podatke.
• Posebnu pažnju obratite na proste brojeve. Primetićete da prosti brojevi imaju najmanje količnike koji su uvek (1+x)/x, odnosno 1 + 1/x.
• Takođe, primetićete da, naročito za velike brojeve x, da je glavni deo zadatka da pronađemo prvi prost broj koji je manji od x.
• S obzirim da je trivijalnost broja 2 (kolčinik) 1.5, a broja 3 1,33, sledećeg neparnog i prostog broja 5 1,2 i 7 1,143, a već broja 13 1,077, teško da ćemo naići na neki broj veći od 1000 koji nije prost a čija je trivijanost manja od 1,1, tačnije od 1,077. Pa čak i da postoji, u prvih 1000 brojeva najveći prost broj je 997 čija je trivijalnost 1,001. Dakle, i bez previše matematičkih alata (teorema, dokaza), ali uključujući logiku, testiranje i matemtićko poznavanje prostih brojeva, količnika i uočvanja pravila (rasta ili opadanja vrednosti) možemo prilčno da ubrzamo agloritamsko rešenje.

Pozdrav,

Dragan Ilić