Programiranje SEKCIJA (i pripreme za takmičenja) -2021/2022

Šta prvo treba da uradimo?

Pažljivo pročitajte zadatak dva puta.

U prvom delu teksta piše da se ponedeljkom treba odrediti kojim danom se reši najviše zadataka. Zatim, da je dat broj prethodnih dana koje treba uzeti u obzir, i taj broj je u zadatku označen sa N. U istoj rečenici stoji i da je za svaki od dana dato koliko je zadataka bilo rešeno.

Analiza prvog dela teksta:

Drugi deo teksta zadatka:

Ovaj deo se odnosi na ulaz, izlaz i ograničenja. I ovaj  deo teksta treba pročitati veoma pažljivo.

Prvo red standardnog ulaza - broj N, koji predstavlja ukupan broj prethodnih dana koji ulaze u prosek.

Zatim ide N redova, i u svakom od njih se nalazi ceo broj koji označava koliko se zadataka rešilo za svaki od dana,

Izlaz: treba na standardni izlaz ispisati naziv dana za koji je najveći prosek zadataka

Ograničenje: 7 <=  N <= 1000 - ovo znači da će N koje se dobije uvek biti o ovom opsegu. To dalje znači i da će uvek biti bar jedan od svih dana. I još znači da se u programu ne treba proveravati vrednost za N, jer je uvek u tom opsegu.

Kako uneti podatke: (ovde se objašnjava način u kojem se koriste NIZOVI)

(Koristimo C++) Za N će se koristiti celobrojni tip podataka int, a za podatke za dane će biti upotrebljen niz celih brojeva. :

 int n;
 cin >> n;

 int nizPoDanima[n];
 for(int i=0; i<n; i++)
 {
   cin >> nizPoDanima[i];
 }

Kako doći do rešenja?

Načina ima raznih, ali će u ovoj analizi biti rađeno na sledeći:

Napravićemo još jedan niz koji ima 7 elemenata za svaki od 7 dana u nedelji. Elementi tog niza će biti celi brojevi u koje ćemo da smestimo sumu svi zadataka za svaki dan u nedelji. Taj niz ćemo nazvati zadaci i postavićemo sve elemente na 0 :

 int zadaci[7]={0}; /* ako samo prvi element inicijalizujete na 0, u C++ će i ostali elementi biti postavljeni na 0 */

A kako ćemo da znamo koliko se puta pojavio svaki od tih dana:

Upotrebićemo još jedan niz od 7 elemenata, za svaki od 7 dana u nedelji, u koji ćemo da stavimo broj pojavljivanja svakog od dana. Taj niz neka bude brojPojava:

 int brojPojava[7]={0};

Na kraju ćemo da proverimo za koji je dan najveći prosek.

Kako izbrojati koliko je bilo pojedinih dana i sabrati broj zadataka za svaki od dana, a da ne pomešamo dane?

I kako sve to da se izbroji:

• Prolazimo kroz niz podataka koji smo dobili na ulazu.
  
• Prvi podatak znamo da je za nedelju. A znamo da niz počinje sa indeksom 0, pa ćemo za nedelju koristiti indeks 0.
  
• onda se broj zadataka iz nizPoDanima[0] ubacuje u zadaci[0], i za 1 se povećava brojPojava[0].
• Sledeći podatak je za subotu. Broj koji je dat u nizPoDanima[1] se ubacuje u zadaci[1], a za 1 se povećava brojPojava[1].
• Za petak se broj zadataka iz nizPoDanima[2] ubacuje u zadaci[2], a za 1 se povećava brojPojava[2].
• ...
  
• i tako sve do ponedeljka, gde se broj zadataka iz nizPoDanima[6]  ubacuje u zadaci[6], a za 1 se povećava brojPojava[6].
• Sledeći dan je opet nedelja, i sada treba da se broj zadataka iz nizPoDanima[7] nadoda na zadaci[0], i za 1 se povećava brojPojava[0].
• nakon toga je subota, gde treba da se broj zadataka iz nizPoDanima[8] nadoda na zadaci[1], i za 1 se povećava brojPojava[1].
• onda ide petak, gde treba da se broj zadataka iz nizPoDanima[9] nadoda na zadaci[2], i za 1 se povećava brojPojava[2].
• ... i tako redom, sve dok se ne dođe do kraja unesenih podataka.

Evo vidite zašto je na početku, kroz inicijalizaciju, postavljena 0 u sve elementa i niza zadaci i niza brojPojava.

Ako je na početku u oba niza svaki element bio jednak nuli, onda rešenje može da bude ovako:

• prvi element sa ulaza (nizPoDanima[0]) se nadodaje na zadaci[0], i za 1 se povećava brojPojava[0]. (to je nedelja)
• drugi element sa ulaza (nizPoDanima[1]) se nadodaje na zadaci[1], i za 1 se povećava brojPojava[1]. (to je subota)
• sledeći element sa ulaza (nizPoDanima[2]) se nadodaje na zadaci[2], i za 1 se povećava brojPojava[2]. (to je petak)
• sledeći element sa ulaza (nizPoDanima[3]) se nadodaje na zadaci[3], i za 1 se povećava brojPojava[3]. (to je četvrtak)
• sledeći element sa ulaza (nizPoDanima[4]) se nadodaje na zadaci[4], i za 1 se povećava brojPojava[4]. (to je sreda)
• sledeći element sa ulaza (nizPoDanima[5]) se nadodaje na zadaci[5], i za 1 se povećava brojPojava[5]. (to je utorak)
• sledeći element sa ulaza (nizPoDanima[6]) se nadodaje na zadaci[6], i za 1 se povećava brojPojava[6]. (to je ponedeljak)
• sledeći element sa ulaza (nizPoDanima[7]) se nadodaje na zadaci[0], i za 1 se povećava brojPojava[0]. (to je nedelja)
• sledeći element sa ulaza (nizPoDanima[8]) se nadodaje na zadaci[1], i za 1 se povećava brojPojava[1]. (to je subota)
• sledeći element sa ulaza (nizPoDanima[9]) se nadodaje na zadaci[2], i za 1 se povećava brojPojava[2]. (to je petak)
• sledeći element sa ulaza (nizPoDanima[10]) se nadodaje na zadaci[3], i za 1 se povećava brojPojava[3]. (to je četvrtak)
• .... i tako redom  ... Da li vidite pravilo ... ?
  
• sledeći element sa ulaza (nizPoDanima[11]) se nadodaje na zadaci[4], i za 1 se povećava brojPojava[4]. (to je sreda)
• sledeći element sa ulaza (nizPoDanima[12]) se nadodaje na zadaci[5], i za 1 se povećava brojPojava[5]. (to je utorak)
• sledeći element sa ulaza (nizPoDanima[13]) se nadodaje na zadaci[6], i za 1 se povećava brojPojava[6]. (to je ponedeljak)
• sledeći element sa ulaza (nizPoDanima[14]) se nadodaje na zadaci[0], i za 1 se povećava brojPojava[0]. (to je nedelja)
• sledeći element sa ulaza (nizPoDanima[15]) se nadodaje na zadaci[1], i za 1 se povećava brojPojava[1]. (to je subota)
• sledeći element sa ulaza (nizPoDanima[16]) se nadodaje na zadaci[2], i za 1 se povećava brojPojava[2]. (to je petak)
• sledeći element sa ulaza (nizPoDanima[17]) se nadodaje na zadaci[3], i za 1 se povećava brojPojava[3]. (to je četvrtak)

Da li vidite pravilo?

(podsetnik: i na mestu indeksa niza može da bude izraz, čiji rezultat je ceo broj !)

Jedan način na koji je ovo moguće rešiti je sledeći:

Prolazimo kroz niz podataka sa ulaza (nizPoDanima), počev od prvog elementa (koji ima indeks 0). Ako je ostatak pri deljenju sa 7 indeksa elementa niza sa ulaza broj 0, onda znamo da se radi o nedelji. Ako je ostatak pri deljenju sa 7 indeksa elementa niza sa ulaza broj 1, onda znamo da se radi o suboti. Ako je ostatak pri deljenju sa 7 indeksa elementa niza sa ulaza broj 2, onda znamo da se radi o petku. ...

I tako redom:

for(int i=0; i<n; i++)
{
  if(i%7 == 0){
    zadaci[0] += nizPoDanima[i];
    brojPojava[0]++; }

  if(i%7 == 1){
    zadaci[1] += nizPoDanima[i];
    brojPojava[1]++; }

  if(i%7 == 2){
    zadaci[2] += nizPoDanima[i];
    brojPojava[2]++; }

  if(i%7 == 3){
    zadaci[3] += nizPoDanima[i];
    brojPojava[3]++; }

  if(i%7 == 4){
    zadaci[4] += nizPoDanima[i];
    brojPojava[4]++; }

  if(i%7 == 5){
    zadaci[5] += nizPoDanima[i];
    brojPojava[5]++; }

  if(i%7 == 6){
    zadaci[6] += nizPoDanima[i];
    brojPojava[6]++; }  
}

(podsetnik: i na mestu indeksa niza može da bude izraz, čiji rezultat je ceo broj !)

Drugi način, koji je i dosta kraći:

for(int i=0; i<n; i++)
{
    zadaci[i%7] += nizPoDanima[i];
    brojPojava[i%7]++;
}

Kako pronaći koji dan ima najveći prosek?

Koristićemo pomoćnu promenljivu maks u koju ćemo staviti maksimalni prosek, i još jednu promenljivu dan koja je tipa string, za naziv dana:

int maks=-1; /* pocetna vrednost za maksimum, koja ionako nije moguca u zadatku */
string dan;
  if(zadaci[0]/brojPojava[0] > maks)
   {
      maks = zadaci[0] / brojPojava[0];
      dan="nedelja";
   }

  if(zadaci[1]/brojPojava[1] > maks)
   {
      maks = zadaci[1] / brojPojava[1];
      dan="subota";
   }

  if(zadaci[2]/brojPojava[2] > maks)
   {
      maks = zadaci[2] / brojPojava[2];
      dan="petak";
   }

  if(zadaci[3]/brojPojava[3] > maks)
   {
      maks = zadaci[3] / brojPojava[3];
      dan="cetvrtak";
   }

  if(zadaci[4]/brojPojava[4] > maks)
   {
      maks = zadaci[4] / brojPojava[4];
      dan="sreda";
   }

  if(zadaci[5]/brojPojava[5] > maks)
   {
      maks = zadaci[5] / brojPojava[0];
      dan="utorak";
   }

  if(zadaci[6]/brojPojava[6] > maks)
   {
      maks = zadaci[6] / brojPojava[6];
      dan="ponedeljak";
   }

   cout<<dan;

Ovde je urađeno pešačkom metodom, za svaki dan prosek, upoređen sa prethodnim maksimumom i samo ako je veči, tada je na maksimum postavljena ta vrednost proseka, a u string promenljivu dan je postavljeno koji je dan u pitanju.

Za sve početnike: radite pešačkom metodom kad god možete, tako se lakše vide greške ako ih ima

drugi način:

Ovo se isto tako može rešiti na kraći način, pomoću niza stringova u koji se postave nazivi dana:

string dani[] = { "nedelja", "subota", "petak", "cetvrtak", "sreda", "utorak", "ponedeljak"};

i da koristimo pomoćne promenljive: prosek, maks i maksIndeks:

for (i = 0; i < 7; i++)
{
  prosek = zadaci[i]/brojPojava[i];
  
  if (prosek >= maks)
  {
    maksIndeks = i;
    maks = prosek;
  }
}
cout << dani[maksIndeks];

Na kraju će u pomoćnoj promenljivoj biti indeks elementa gde je bio najveći prosek. Po tom indeksu se ispisuje element niza dani.

U nastavku su dve verzije rešenja zadatka:

Isprobajte i jednu i drugu, pogledajte komletan programski kod i razmislite, na koji viste način vi rešili ovaj zadatak.

I na kraju:

Nakon zadatka, na Petlji, stoji njihovo rešenje, skrolujte na dno stranice i pogledajte.

Koje vam rešenje više odgovara?

Kako biste vi to uradili ?