15. TAČAN IZRAZ - REŠENJE ZADATKA
U ovom zadatku, vaš cilj je da proverite tačnost matematičkog izraza tako što ćete pravilno rasporediti operatore između brojeva. Zadatak vas vodi kroz izazov sastavljanja tačnih aritmetičkih operacija u nizu, uz primenu logičkih operatora i pažljivo vođenje računa o redosledu operacija.
Na ovoj stranici pružamo dva različita pristupa rešavanju ovog problema, svaki sa detaljnim objašnjenjem i pratećim kodom. Prvi pristup se fokusira na jednostavniju implementaciju, dok drugi koristi složenije algoritme za efikasnije rešavanje zadatka. Cilj je da vam pokažemo različite načine kako se može pristupiti jednom problemu i da vas podstaknemo da eksperimentišete sa svojim rešenjima.
U nastavku teksta, pročitajte zadatak, a zatim istražite rešenja koja su data uz objašnjenja svakog koraka.
Na ovoj stranici pružamo dva različita pristupa rešavanju ovog problema, svaki sa detaljnim objašnjenjem i pratećim kodom. Prvi pristup se fokusira na jednostavniju implementaciju, dok drugi koristi složenije algoritme za efikasnije rešavanje zadatka. Cilj je da vam pokažemo različite načine kako se može pristupiti jednom problemu i da vas podstaknemo da eksperimentišete sa svojim rešenjima.
U nastavku teksta, pročitajte zadatak, a zatim istražite rešenja koja su data uz objašnjenja svakog koraka.
Tekst zadatka
/*
U izraz a_b_c=d umesto donjih crta treba ubaciti dve računske operacije tako da izraz bude tačan. Računske operacije koje se mogu koristiti su sabiranje (+), oduzimanje (−), množenje (∗) i celobrojno deljenje (/). Važe standardni prioriteti računskih operacija.
Ulaz
U svakom od četiri reda standardnog ulaza se unosi po jedan ceo broj (redom se unose a,b,c i d).
Svi brojevi su u opsegu[1,1000].
Izlaz
Na standardni izlaz ispisati sva moguća rešenja (u proizvoljnom redosledu), svako u posebnom redu. Jedno rešenje se ispisuje u formi 2 znaka (razdvojena razmakom) koji predstavljaju računske operacija koje je tim redom potrebno ubaciti da bi izraz bio tačan.
Ukoliko nije moguće postići tačan izraz, ispisati nemoguce.
Primer 1
Ulaz
2
3
4
2
Izlaz
* -
+ /
- /
Objašnjenje
∗− je rešenje jer važi 2∗3−4=2
+/ je rešenje jer važi 2 + 3/4=2 (primetiti da ovde imamo celobrojno deljenje koje je većeg prioriteta od sabiranja i čiji je rezultat 0)
−/ je rešenje jer važi 2−3/4=2 (primetiti da ovde imamo celobrojno deljenje koje je većeg prioriteta od sabiranja i čiji je rezultat 0)
Primer 2
Ulaz
8
3
2
12
Izlaz
* /
Primer 3
Ulaz
2
2
9
3
Izlaz
nemoguce
Primer 4
Ulaz
2
2
7
4
Izlaz
nemoguce
*/
U izraz a_b_c=d umesto donjih crta treba ubaciti dve računske operacije tako da izraz bude tačan. Računske operacije koje se mogu koristiti su sabiranje (+), oduzimanje (−), množenje (∗) i celobrojno deljenje (/). Važe standardni prioriteti računskih operacija.
Ulaz
U svakom od četiri reda standardnog ulaza se unosi po jedan ceo broj (redom se unose a,b,c i d).
Svi brojevi su u opsegu[1,1000].
Izlaz
Na standardni izlaz ispisati sva moguća rešenja (u proizvoljnom redosledu), svako u posebnom redu. Jedno rešenje se ispisuje u formi 2 znaka (razdvojena razmakom) koji predstavljaju računske operacija koje je tim redom potrebno ubaciti da bi izraz bio tačan.
Ukoliko nije moguće postići tačan izraz, ispisati nemoguce.
Primer 1
Ulaz
2
3
4
2
Izlaz
* -
+ /
- /
Objašnjenje
∗− je rešenje jer važi 2∗3−4=2
+/ je rešenje jer važi 2 + 3/4=2 (primetiti da ovde imamo celobrojno deljenje koje je većeg prioriteta od sabiranja i čiji je rezultat 0)
−/ je rešenje jer važi 2−3/4=2 (primetiti da ovde imamo celobrojno deljenje koje je većeg prioriteta od sabiranja i čiji je rezultat 0)
Primer 2
Ulaz
8
3
2
12
Izlaz
* /
Primer 3
Ulaz
2
2
9
3
Izlaz
nemoguce
Primer 4
Ulaz
2
2
7
4
Izlaz
nemoguce
*/
Rešenje
Program posle unosa vrednosti za a, b, c, i d, u dva dela menja moguće operacije, tako što kroz for petlju menja indekse od i=0 do i=3 i koristeći switch naredbu rasčlanjuje sve aritmetičke operacije: za i=0 npr operacija je "+", za i=1 operacija je "-", za i=2 je "*" i za i=3 je "/".
Ako su operacije "+" ili "-", za prvi blok tj. za a operacija1 b, onda se ta operacija neće izvršiti odmah, već naknadno, zbog većeg prioriteta operacija "*" i "/" nad operacijama "-" ili "+", pa se upamćena vrednost operacije posle tog prvog dela(prva petlja for) izvršava naknadno, posle izvršenja operacije2 u drugoj for petlji. Za ovo se koriste logičke promenljive posle i posle2, a za čuvanje rezultata r, rMinus i r1.
Na primer ako su unete vrednosti a=2,b=3,c=4, i d=2 i ako se proverava slučaj a+b ili a-b, onda se samo zapamti operacija, ali se ne izračunava rezultat odmah, nego se dalje unutar druge petlje izračunava npr r= b+c ili r=b*c ili r=b/c, pa se tek naknadno posle toga izračuna a+r.
Ako je prvo bio minus, onda dodatno treba obratiti pažnju da će se znak b promeniti.
Unutar druge for petlje posle izračunavanja obe operacije proverava se da li se izračunata vrednost podudara sa zadatom vrednošću d i ako se podudara, onda se operacije ispisuju. U slučaju da se nijedna operacija nije poklopila, onda bi logička promenljiva nemoguce ostala jednaka true i na ekranu bi se ispisala poruka "nemoguće".
Ako su operacije "+" ili "-", za prvi blok tj. za a operacija1 b, onda se ta operacija neće izvršiti odmah, već naknadno, zbog većeg prioriteta operacija "*" i "/" nad operacijama "-" ili "+", pa se upamćena vrednost operacije posle tog prvog dela(prva petlja for) izvršava naknadno, posle izvršenja operacije2 u drugoj for petlji. Za ovo se koriste logičke promenljive posle i posle2, a za čuvanje rezultata r, rMinus i r1.
Na primer ako su unete vrednosti a=2,b=3,c=4, i d=2 i ako se proverava slučaj a+b ili a-b, onda se samo zapamti operacija, ali se ne izračunava rezultat odmah, nego se dalje unutar druge petlje izračunava npr r= b+c ili r=b*c ili r=b/c, pa se tek naknadno posle toga izračuna a+r.
Ako je prvo bio minus, onda dodatno treba obratiti pažnju da će se znak b promeniti.
Unutar druge for petlje posle izračunavanja obe operacije proverava se da li se izračunata vrednost podudara sa zadatom vrednošću d i ako se podudara, onda se operacije ispisuju. U slučaju da se nijedna operacija nije poklopila, onda bi logička promenljiva nemoguce ostala jednaka true i na ekranu bi se ispisala poruka "nemoguće".
#include <iostream>
using namespace std;
int main()
{
int a,b,c,d,r;
bool nemoguce=true; //Ako ostane true, ne može se dobiti jednakost a operacija1 b operacija2 c=d
cin>>a>>b>>c>>d;
char x, y;
x='+';
y='+';
r=a;
for(int i=0; i<4; i++)
{
bool posle=false; //Početna vrednost prve operacije
bool minus=false; //Početna vrednost druge operacije
int rMinus=a;
/* Prvi blok nardbi koji menja sve aritmetičke operacije +,-,*,/, koristeći for petlju i switch naredbu unutar nje*/
switch(i)
{
case 0:
{
x='+'; //prva moguća operacija je sabiranje. Koristi se x promenljiva tipa char da upamti znak operacije
posle=true; //Izračunaće se posle izračunavanja druge operacije
r=0; //privremen rezultat izvršavanja prve operacije u ovom slučaju ostaje nula
break;
}
case 1:
{
x='-'; //prva moguća operacija je oduzimanje. Koristi se x promenljiva tipa char da upamti znak operacije
r=0;
posle=true; //Izračunaće se posle izračunavanja druge operacije
minus=true; /*Dodatna indikacija da je oduzimanje prva operacija da bi se prilikom izvršavanja druge operacije promenio znak promenljivoj b*/
break;
}
case 2:
{
r=a*b; //prva moguća operacija je množenje i izračunava se odmah.
x='*';
break;
}
case 3:
{
r=a/b; //prva moguća operacija je deljenjei izračunava se odmah.
x='/';
break;
}
}
int r1=r; //Prepisuje rezultat izvršenja operacije1 u promenljivu r1
bool posle2=posle; /*prepisuje vrednost promenljive posle u drugu promenljivu posle2 u slučaju da je prva operacija oduzimanje*/
/* Drugi blok nardbi koji menja sve aritmetičke operacije +,-,*,/, koristeći for petlju i switch naredbu unutar nje*/
for(int j=0; j<4; j++)
{
switch(j)
{
case 0:
{
if(minus)posle2=false; //Ako je prva operacija bila oduzimanje koristi se izračunata vrednost prve operacije rMinus
if(posle2) //ako je bio minus onda će posle2 biti jednako false
{
r=b+c; // Privremen rezultat druge operacije, u ovom slučaju sabiranja
}
else if(minus) //ako je bio minus
{
r=rMinus-b+c; /* Za prvu operaciju oduzimanja, ta operacija je izvršena i rezultat je upamćen kao rMinus, a pri tome vrednost b mora da promeni znak */
}
else //Množenje ili delenje
{
r=r+c; //Dodaje drugu operaciju na rezultat prethodne r
}
y='+';
break;
}
case 1:
{
if(minus)posle2=false;
if(posle2)
{
r=b-c;
}
else if(minus) //ako je bio minus
{
r=rMinus-b-c;
}
else
{
r=r-c;
}
y='-';
break;
}
case 2:
{
y='*';
if(posle2)
{
r=b*c;
}
else
{
r=r*c;
}
break;
}
case 3:
{
y='/';
if(posle2)
{
r=b/c;
}
else
{
r=r/c;
}
break;
}
}
//naknadno radi prvu operaciju
if(posle2 && x=='+')//Ako je prethodno bila operacija sabiranje
{
r=a+r;
}
else if(posle2 && x=='-') //Ako je prethodno bila operacija oduzimanje
{
r=a-r;
}
/* Ako se rezultat izračunavanja operacija podudara sa d onda se operacije ispisuju*/
if(r==d)
{
cout<<x<<" "<<y<<endl;
nemoguce=false;
}
r=r1;
posle2=posle;
}
r=a;
}
if(nemoguce)
cout<<"nemoguce"<<endl;
return 0;
}
using namespace std;
int main()
{
int a,b,c,d,r;
bool nemoguce=true; //Ako ostane true, ne može se dobiti jednakost a operacija1 b operacija2 c=d
cin>>a>>b>>c>>d;
char x, y;
x='+';
y='+';
r=a;
for(int i=0; i<4; i++)
{
bool posle=false; //Početna vrednost prve operacije
bool minus=false; //Početna vrednost druge operacije
int rMinus=a;
/* Prvi blok nardbi koji menja sve aritmetičke operacije +,-,*,/, koristeći for petlju i switch naredbu unutar nje*/
switch(i)
{
case 0:
{
x='+'; //prva moguća operacija je sabiranje. Koristi se x promenljiva tipa char da upamti znak operacije
posle=true; //Izračunaće se posle izračunavanja druge operacije
r=0; //privremen rezultat izvršavanja prve operacije u ovom slučaju ostaje nula
break;
}
case 1:
{
x='-'; //prva moguća operacija je oduzimanje. Koristi se x promenljiva tipa char da upamti znak operacije
r=0;
posle=true; //Izračunaće se posle izračunavanja druge operacije
minus=true; /*Dodatna indikacija da je oduzimanje prva operacija da bi se prilikom izvršavanja druge operacije promenio znak promenljivoj b*/
break;
}
case 2:
{
r=a*b; //prva moguća operacija je množenje i izračunava se odmah.
x='*';
break;
}
case 3:
{
r=a/b; //prva moguća operacija je deljenjei izračunava se odmah.
x='/';
break;
}
}
int r1=r; //Prepisuje rezultat izvršenja operacije1 u promenljivu r1
bool posle2=posle; /*prepisuje vrednost promenljive posle u drugu promenljivu posle2 u slučaju da je prva operacija oduzimanje*/
/* Drugi blok nardbi koji menja sve aritmetičke operacije +,-,*,/, koristeći for petlju i switch naredbu unutar nje*/
for(int j=0; j<4; j++)
{
switch(j)
{
case 0:
{
if(minus)posle2=false; //Ako je prva operacija bila oduzimanje koristi se izračunata vrednost prve operacije rMinus
if(posle2) //ako je bio minus onda će posle2 biti jednako false
{
r=b+c; // Privremen rezultat druge operacije, u ovom slučaju sabiranja
}
else if(minus) //ako je bio minus
{
r=rMinus-b+c; /* Za prvu operaciju oduzimanja, ta operacija je izvršena i rezultat je upamćen kao rMinus, a pri tome vrednost b mora da promeni znak */
}
else //Množenje ili delenje
{
r=r+c; //Dodaje drugu operaciju na rezultat prethodne r
}
y='+';
break;
}
case 1:
{
if(minus)posle2=false;
if(posle2)
{
r=b-c;
}
else if(minus) //ako je bio minus
{
r=rMinus-b-c;
}
else
{
r=r-c;
}
y='-';
break;
}
case 2:
{
y='*';
if(posle2)
{
r=b*c;
}
else
{
r=r*c;
}
break;
}
case 3:
{
y='/';
if(posle2)
{
r=b/c;
}
else
{
r=r/c;
}
break;
}
}
//naknadno radi prvu operaciju
if(posle2 && x=='+')//Ako je prethodno bila operacija sabiranje
{
r=a+r;
}
else if(posle2 && x=='-') //Ako je prethodno bila operacija oduzimanje
{
r=a-r;
}
/* Ako se rezultat izračunavanja operacija podudara sa d onda se operacije ispisuju*/
if(r==d)
{
cout<<x<<" "<<y<<endl;
nemoguce=false;
}
r=r1;
posle2=posle;
}
r=a;
}
if(nemoguce)
cout<<"nemoguce"<<endl;
return 0;
}
Objašnjenje zadatka
Ovo rešenje zadatka koristi kombinaciju for petlji i switch naredbi da bi generisalo sve moguće kombinacije dve aritmetičke operacije koje bi mogle povezati brojeve a, b, c tako da dobijemo zadati rezultat d. Evo detaljnog objašnjenja ključnih delova:
1. Unos podataka
int a,b,c,d,r;
bool nemoguce=true;
cin >> a >> b >> c >> d;
char x, y;
r = a;
bool nemoguce=true;
cin >> a >> b >> c >> d;
char x, y;
r = a;
Prvo se unose brojevi a, b, c i d, a nemoguce je logička promenljiva koja prati da li je moguće naći rešenje. Ako ne nađemo nijedno rešenje, na kraju programa ispisujemo "nemoguce".
2. Prva for petlja (odabir prve operacije)
for(int i=0; i<4; i++)
{
// Switch koji menja prvu operaciju: '+', '-', '*', '/'
switch(i)
{
case 0: x = '+'; posle = true; r = 0; break;
case 1: x = '-'; posle = true; r = 0; minus = true; break;
case 2: r = a * b; x = '*'; break;
case 3: r = a / b; x = '/'; break;
}
{
// Switch koji menja prvu operaciju: '+', '-', '*', '/'
switch(i)
{
case 0: x = '+'; posle = true; r = 0; break;
case 1: x = '-'; posle = true; r = 0; minus = true; break;
case 2: r = a * b; x = '*'; break;
case 3: r = a / b; x = '/'; break;
}
Ova petlja prolazi kroz sve četiri moguće operacije za prvi deo izraza (a operacija1 b). Operacije su sabiranje (+), oduzimanje (-), množenje (*) i deljenje (/). Ako je prva operacija + ili -, tada se rezultat ne računa odmah zbog prioriteta operacija i obeležava se promenljivom posle. Ako je operacija množenje ili deljenje, rezultat se odmah računa.
3. Druga for petlja (odabir druge operacije)
for(int j=0; j<4; j++)
{
switch(j)
{
case 0: r = b + c; y = '+'; break;
case 1: r = b - c; y = '-'; break;
case 2: r = b * c; y = '*'; break;
case 3: r = b / c; y = '/'; break;
}
{
switch(j)
{
case 0: r = b + c; y = '+'; break;
case 1: r = b - c; y = '-'; break;
case 2: r = b * c; y = '*'; break;
case 3: r = b / c; y = '/'; break;
}
Druga petlja testira sve moguće operacije za drugi deo izraza (operacija2 c). Opet se koriste iste četiri operacije: +, -, *, i /. Ove operacije se primenjuju na prethodni rezultat (ili na b ako je prva operacija + ili -).
4. Naknadna primena prve operacije
if(posle2 && x == '+') r = a + r;
else if(posle2 && x == '-') r = a - r;
else if(posle2 && x == '-') r = a - r;
Ako prva operacija ima niži prioritet (tj. ako je to + ili -), ona se naknadno primenjuje na rezultat druge operacije. Ako je prva operacija bila -, mora se izvršiti oduzimanje na kraju, nakon druge operacije.
5. Provera i ispis rezultata
if(r == d)
{
cout << x << " " << y << endl;
nemoguce = false;
}
{
cout << x << " " << y << endl;
nemoguce = false;
}
Ako dobijeni rezultat odgovara zadatom broju d, program ispisuje operacije koje su dovele do tačnog rezultata. Ako nijedna kombinacija operacija nije dala tačan rezultat, na kraju programa će se ispisati "nemoguce".
Važne napomene:
Važne napomene:
- Prioritet operacija: U zadatku su sabiranje i oduzimanje nižeg prioriteta od množenja i deljenja. Zato je program podešen tako da naknadno primeni sabiranje ili oduzimanje, ako je to prva operacija.
- Celobrojno deljenje: Pošto se koristi celobrojno deljenje (/), rezultati deljenja će biti zaokruženi na niži ceo broj.
Rešenje 2
Ovaj zadatak se sastoji u ispitivanju različitih kombinacija matematičkih operacija koje mogu biti smeštene između tri broja kako bi se dobila tražena vrednost. Koristeći četiri osnovne operacije (+, -, *, /) i njihove prioritete, treba pronaći sve validne kombinacije koje zadovoljavaju izraz.
Ideja rešenja:
Ideja rešenja:
- Na ulazu imamo četiri broja aaa, bbb, ccc i ddd, gde izraz a ? b ? c=da \, \text{?} \, b \, \text{?} \, c = da?b?c=d treba biti tačan.
- Računske operacije koje se mogu koristiti su sabiranje, oduzimanje, množenje i celobrojno deljenje.
- Prioriteti operacija moraju biti ispoštovani, tj. množenje i deljenje imaju veći prioritet od sabiranja i oduzimanja.
- Treba ispitati sve moguće kombinacije operacija i provesti izračunavanje da vidimo da li odgovaraju traženom rezultatu ddd.
- Ispitujemo sve moguće kombinacije operacija između aaa, bbb i ccc.
- Za svaku kombinaciju proveravamo da li je rezultat jednak ddd, poštujući prioritet operacija.
- Ukoliko nije moguće naći odgovarajuće operacije, ispisujemo "nemoguce".
#include <iostream>
using namespace std;
// Funkcija koja računa rezultat izraza sa zadatim operacijama
int calculate(int a, int b, int c, char op1, char op2) {
int result;
if (op1 == '*' || op1 == '/') {
if (op1 == '*') result = a * b;
else if (op1 == '/') result = a / b;
// Nakon što izračunamo a op1 b, primenjujemo op2 sa c
if (op2 == '+') result += c;
else if (op2 == '-') result -= c;
else if (op2 == '*') result *= c;
else if (op2 == '/') result /= c;
} else {
// Ako su op1 + ili -, prvo računamo a op1 b, pa op2 sa c
if (op1 == '+') result = a + b;
else if (op1 == '-') result = a - b;
if (op2 == '*') result *= c;
else if (op2 == '/') result /= c;
else if (op2 == '+') result += c;
else if (op2 == '-') result -= c;
}
return result;
}
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
char operators[] = {'+', '-', '*', '/'};
bool found = false;
// Ispitujemo sve kombinacije dve operacije
for (char op1 : operators) {
for (char op2 : operators) {
// Izbegavamo deljenje sa nulom
if ((op1 == '/' && b == 0) || (op2 == '/' && c == 0)) continue;
int result = calculate(a, b, c, op1, op2);
if (result == d) {
cout << op1 << " " << op2 << endl;
found = true;
}
}
}
if (!found) {
cout << "nemoguce" << endl;
}
return 0;
}
using namespace std;
// Funkcija koja računa rezultat izraza sa zadatim operacijama
int calculate(int a, int b, int c, char op1, char op2) {
int result;
if (op1 == '*' || op1 == '/') {
if (op1 == '*') result = a * b;
else if (op1 == '/') result = a / b;
// Nakon što izračunamo a op1 b, primenjujemo op2 sa c
if (op2 == '+') result += c;
else if (op2 == '-') result -= c;
else if (op2 == '*') result *= c;
else if (op2 == '/') result /= c;
} else {
// Ako su op1 + ili -, prvo računamo a op1 b, pa op2 sa c
if (op1 == '+') result = a + b;
else if (op1 == '-') result = a - b;
if (op2 == '*') result *= c;
else if (op2 == '/') result /= c;
else if (op2 == '+') result += c;
else if (op2 == '-') result -= c;
}
return result;
}
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
char operators[] = {'+', '-', '*', '/'};
bool found = false;
// Ispitujemo sve kombinacije dve operacije
for (char op1 : operators) {
for (char op2 : operators) {
// Izbegavamo deljenje sa nulom
if ((op1 == '/' && b == 0) || (op2 == '/' && c == 0)) continue;
int result = calculate(a, b, c, op1, op2);
if (result == d) {
cout << op1 << " " << op2 << endl;
found = true;
}
}
}
if (!found) {
cout << "nemoguce" << endl;
}
return 0;
}
Objašnjenje:
- Ulazni podaci: Program čita četiri broja: aaa, bbb, ccc, i ddd.
- Operatori: Koriste se operatori: sabiranje (+), oduzimanje (-), množenje (*), i celobrojno deljenje (/). Kombinujemo dve operacije između aaa, bbb, i ccc.
- Provera deljenja: U slučaju da je jedan od operanada u operaciji deljenja jednak 0, taj slučaj preskačemo kako bismo izbegli grešku.
- Računanje: Koristeći funkciju calculate, proveravamo rezultat za sve kombinacije operatora i ispitujemo da li rezultat odgovara ddd.
- Ispis: Ako nađemo validnu kombinaciju, ispisujemo operatore, a ako ne nađemo nijednu, ispisujemo "nemoguce".