|
Ovo je klasičan primer dinamičkog programiranja u kojem kompleksan problem rešavamo rešavanjem više jednostavnijih.
Problem smo mogli da rešimo tako što bi krenuli redom i tražili svaki broj deljiv sa N. Zatim bi išli od početka i tražili po dva uzastopna broja čiji je zbir deljiv sa N. Zatim za tri, četiri, itd... tako bi najlakše rešili problem, ali to nije i optimalno rešenje jer kroz sam niz prolazimo ponovo i ponovo i ponovo iako se sami brojevi nikad ne menjaju.
Pošto je cilj zadatka da ispišemo broj neprekinutih nizova koji su deljivi sa N, problem možemo rešiti tako što ćemo prvo izračunati ostatak pri deljenju za prvi broj, zatim prvom broju dodati drugi i izračunati ostatak njihovog zbira. Zatim dodamo i treći, pa četvrti i tako do kraja.
Zašto smo to uradili... sada za kompletan niz za svaki element imamo izračunat ostatak i ako nađemo 2 elementa sa istim ostatkom znamo da možemo da dobijemo niz sa ostatkom 0 ako izbacimo element niza jednak ostatku.
Recimo da je svaki put taj element na prvom mestu podniza. Ako imamo 2 ista ostatka koja označavaju početak i kraj podniza, izbacivanjem prvog elementa dobijamo podniz bez ostatka i to je jedsn od podnizova koji ispunjava uslov. Ako imamo 3 ista ostatka, tada možemo napraviti 3 različita podniza. Prvi je od prvog do drugog istog ostatka, drugi je od drugog do trećeg i treći je od prvog do trećeg. I tako dalje... ako ih imamo 4, možemo napraviti šest. 1-2,1-3,1-4,2-3,2-4,3-4. Matematička formula koja kaže koliko ovakvih kombinacija možemo napraviti je: K*(K-1)/2
Korišćenjem logike i znanjem matemetike je osoba koja je rešila ovaj zadatak uspela da dođe do rešenja samo jednim prolazom kroz ceo niz i još jedim prolazom kroz kratak niz u kojem je zapisano koliko podnizova sa određenim ostatkom postoji u nizu.
|
