6. Bašta sljezove boje - rešenje
Varijanta I: Upotrebom ugnježdenih petlji
Ovo rešenje je da se naprave dve for petlje, jedna da bude ugnježdena u drugoj. Spoljašnja simulira promenu deljenja, N puta.Unutrašnja uzima tekući broj koji je u tom ciklusu i učitan i poredi sa prethodnim u okviru istog deljenja, tj. u prethodnom ciklusu ugnježdene petlje. U svakom novom ciklusu tekući broj postaje prethodnik za novi ciklus.
Ako se dobije da u nekom ciklusu tekući i prethodni broj nisu u neopadajućem poretku, konstatuje se da je tekuće deljenje "neispravno" i brojač neispravnih deljenja se poveća za 1. Postupak se pomoću spoljašnje petlje ponavlja i za ostala "deljenja", tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.#include <iostream>
using namespacestd;
/*
Primer 1
Ulaz
4
3
1
2
3
4
3
4
1
5
5
8
8
8
Izlaz
1
Učitani su podaci za 4 deljenja. Dobro je posloženo prvo, treće, četvrto deljenje.
Nije dobro posloženo drugo deljenje sa karticama 4,3,4.
*/
int main()
{
int n,k,br=0,b,p;
cin>>n>>k;
for(int i=0; i<n; i++)
{
bool dobro=true;
for(int j=0; j<k; j++)
{
cin>>b;
if(j==0)
{
/*Prethodnik za sledeći ciklus postaje jednak broju u tekućem ciklusu*/
p=b;
}
else
{
if(b<p)
{
dobro=false; //Nije dobro deljenje
p=b;/*Prethodnik za sledeći ciklus postaje jednak broju u tekućem ciklusu*/
}
}
}
/*Ako deljenje nije dobro brojač se povećava za 1*/
if(!dobro)
{
br++;
cout<<i<<". ->"<<"nije dobro"<<endl;
}
}
cout<<br<<endl;
return 0;
}
Varijanta II: Rešenje pomoću vektora.
Ovde koristimo vektore za pamćenje brojeva kartica u svakom deljenu. Uneti brojeve na karticama u vektor za svako deljenje. Deljenja se menjaju pomoću petlje. Treba napraviti kopiju vektora i sortirati(samo kopiju) po neopadajućem redosledu.Zatim se ta kopija upoređuje sa originalnim vektorom.
Ako su original i kopija jednaki, to znači da je i originalni vektor bio u samom početku ispravno sortiran. Dakle, ako nisu jednaki reč je o "lošem" deljenju i brojač loših deljenja se povećava za 1.
Postupak se ponovlja i za ostala deljenja, tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.
#include <iostream>
#include <vector>
#include <algorithm>
using namespacestd;
int main() {
int N, k; //Broj deljenja i broj kartica u jednom deljenju
cin >> N >> k;
int brojGresaka = 0; //broj pogrešnih deljenja, u početku je jednak nuli
for (int i = 0; i < N; ++i) {
vector<int> kartice(k);
for (int j = 0; j < k; ++j) {
cin >> kartice[j];
}
vector<int> sortiraneKartice = kartice; //Kopija vektora kartice
sort(sortiraneKartice.begin(), sortiraneKartice.end());
if (kartice != sortiraneKartice) {
++brojGresaka;
}
}
cout << brojGresaka << endl;
return 0;
}
Rezime:
- Čitanje ulaza:
- cin >> N >> k; učitava broj deljenja N i broj kartica u svakom deljenju k.
- Provera svakog deljenja:
- vector<int> kartice(k); kreira vektor veličine k za čuvanje kartica.
- cin >> kartice[j]; učitava kartice za trenutno deljenje.
- vector<int> sortiraneKartice = kartice; pravi kopiju kartica koja će biti sortirana.
- sort(sortiraneKartice.begin(), sortiraneKartice.end()); sortira kopiju kartica.
- if (kartice != sortiraneKartice) { ++brojGresaka; } proverava da li su kartice u početnom nizu različite od sortiranih kartica. Ako jesu, povećava broj grešaka.
- Ispis rezultata:
- cout << brojGresaka << endl; ispisuje ukupan broj deljenja u kojima kartice nisu bile pravilno poredane.
|
|