Pomoc oko zadatka

Pomoc oko zadatka

offline
  • Pridružio: 15 Apr 2012
  • Poruke: 141

Gledao sam resenje zadatka na linku codingrecipies.blogspot.rs/2013/11/continuo.....le-by.html sve mi je jasno sem formule k(k-1)/2, shvatam da je to K nad 2 odnosno neke kombinacije ali ne znam zasto. Pozdrav!



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Srđan Tot
  • Am I evil? I am man, yes I am.
  • Pridružio: 12 Jul 2005
  • Poruke: 2483
  • Gde živiš: Ljubljana

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.



Ko je trenutno na forumu
 

Ukupno su 1050 korisnika na forumu :: 35 registrovanih, 4 sakrivenih i 1011 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: -[CoA]-, Ageofloneliness, Aleksandar Tomić, Andrija357, Apok, bankulen, bbogdan, Bloody, Bobrock1, Botovac, Darko8, Georgius, Insan, Koca Popovic, Melody, mercedesamg, milos.cbr, miodrag, moldway, Nemanja.M, Outis, pein, Pohovani_00, robertino, Sirius, torlak 1, Tvrtko I, vathra, Webb, wizzardone, ZetaMan, zicko.spacek, zillbg, Zvrk, |_MeD_|