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.
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 operacije
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 (celobrojno deljenje ima veći prioritet)
- / je rešenje jer važi 2 - 3 / 4 = 2 (celobrojno deljenje ima veći prioritet)
Primer 2:
Ulaz:
8
3
2
12
Izlaz:
* /
Primer 3:
Ulaz:
2
2
9
3
Izlaz:
nemoguce
*/
Rešenje
Program posle unosa vrednosti za a, b, c i d menja moguće operacije kroz dve for petlje,
kombinujući četiri osnovne aritmetičke operacije.
Prva petlja određuje prvu operaciju (između a i b), dok druga kombinuje drugu (između b i c).
Korišćenjem switch naredbi i logičkih promenljivih (posle, minus, nemoguce)
program pravilno primenjuje prioritete operacija i pronalazi sve kombinacije koje daju tačan rezultat.
#include <iostream>
using namespace std;
int main() {
int a, b, c, d, r;
bool nemoguce = true;
cin >> a >> b >> c >> d;
char x, y;
x = '+';
y = '+';
r = a;
for (int i = 0; i < 4; i++) {
bool posle = false;
bool minus = false;
int rMinus = a;
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;
}
int r1 = r;
bool posle2 = posle;
for (int j = 0; j < 4; j++) {
switch (j) {
case 0:
if (minus) posle2 = false;
if (posle2) r = b + c;
else if (minus) r = rMinus - b + c;
else r = r + c;
y = '+';
break;
case 1:
if (minus) posle2 = false;
if (posle2) r = b - c;
else if (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;
}
if (posle2 && x == '+') r = a + r;
else if (posle2 && x == '-') r = a - r;
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 koristi kombinaciju for petlji i switch naredbi da generiše sve moguće kombinacije
dvе aritmetičke operacije između brojeva a, b i c kako bi dobio zadati rezultat d.
1. Unos podataka:
Program čita brojeve a, b, c i d i postavlja promenljivu nemoguce na true.
Ako ne pronađe nijedno rešenje, na kraju će ispisati "nemoguce".
2. Prva for petlja:
Određuje prvu operaciju između a i b.
Ako je to + ili -, izračunavanje se odlaže zbog prioriteta, dok se * i / odmah računaju.
3. Druga for petlja:
Određuje drugu operaciju između b i c i izračunava rezultat u skladu sa prethodnom operacijom.
4. Naknadna primena prve operacije:
Ako je prva operacija + ili -, ona se izvršava nakon što se druga završi.
Ovim se poštuje matematički prioritet operacija.
5. Provera rešenja:
Ako rezultat odgovara zadatoj vrednosti d, operacije se ispisuju.
Ako nijedna kombinacija ne odgovara, ispisuje se "nemoguce".
Zaključak:
Ovo rešenje je efikasno i pregledno jer proverava sve kombinacije aritmetičkih operacija i poštuje redosled njihovog izvršavanja.
Zahvaljujući logičkim promenljivima, program jasno razlikuje situacije u kojima treba naknadno izvršiti prvu operaciju.
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;
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;
}
}
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;
}
}
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;
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;
}
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:
- Prioritet operacija: Sabiranje i oduzimanje imaju niži prioritet od množenja i deljenja. Zato se sabiranje ili oduzimanje primenjuju naknadno, ako su prve u izrazu.
- Celobrojno deljenje: Rezultati deljenja su celobrojni, tj. zaokruženi na niži ceo broj.
Zaključak:
Ovo rešenje je efikasno jer pokriva sve kombinacije operacija i vodi računa o prioritetu operacija.
Program proverava sve moguće operacije za prvi i drugi operand, a zatim proverava da li kombinacija daje traženi rezultat.
Ako nijedna kombinacija nije tačna, program ispisuje "nemoguce".
Komentar na rešenje
Rešenje demonstrira praktično znanje C++ jezika, posebno u kombinovanju for petlji i switch naredbi za generisanje svih mogućih kombinacija aritmetičkih operacija.
Logičke promenljive poput posle i minus omogućavaju pravilno poštovanje prioriteta operacija, što pokazuje razumevanje osnovnih matematičkih pravila unutar programskog konteksta.
Efikasnost rešenja je solidna za zadati opseg brojeva, jer se sve četiri osnovne operacije testiraju sistematski. Međutim, kod je prilično proceduralan i pomalo opširan zbog velikog broja switch slučajeva, što otežava održavanje i čitljivost. Za veće zadatke ili proširenje funkcionalnosti, moglo bi se razmotriti korišćenje matrice operacija ili funkcija za evaluaciju izraza radi smanjenja dupliranja koda.
Pored toga, rešavanje zadatka uključuje važno razumevanje celobrojnog deljenja i prioritetnih operacija, što pruža dobar uvid u logičko razmišljanje i upravljanje kontrolnim tokovima. Čitaoci mogu videti kako kombinacija jednostavnih kontrola toka i aritmetike može rešiti kompleksan problem, ali i gde bi se kod mogao unaprediti u smislu modularnosti i čitljivosti.
Moguća poboljšanja
- Korišćenje funkcija ili lambda izraza za evaluaciju izraza kako bi se smanjilo dupliranje koda.
- Zamena switch naredbi strukturiranim pristupom, npr. korišćenjem matrice operacija ili niza funkcija.
- Poboljšanje čitljivosti i održivosti koda kroz modularizaciju i jasnije imenovanje promenljivih.
- Dodavanje provere deljenja sa nulom kako bi se izbegle greške pri celobrojnom deljenju.
- Mogućnost proširenja na veći broj operacija ili brojeva korišćenjem rekurzije ili generatora kombinacija.
Rešenje 2 - Tačan izraz
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.
Na ulazu imamo četiri broja a, b, c i d, gde izraz a ? b ? c = d treba biti tačan.
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.
Kod:
#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;
}
Objašnjenje:
- Ulazni podaci: Program čita četiri broja:
aaa,bbb,ccciddd. - Operatori: Koriste se operatori sabiranja (+), oduzimanja (-), množenja (*) i celobrojnog deljenja (/). Kombinujemo dve operacije između
aaa,bbbiccc. - Provera deljenja: Ako je jedan od operanada u deljenju 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 odgovaraddd. - Ispis: Ako nađemo validnu kombinaciju, ispisujemo operatore, a ako ne nađemo nijednu, ispisujemo "nemoguce".
Komentar na rešenje:
Ovo rešenje je čitko i modularno, jer koristi funkciju calculate za evaluaciju izraza, što smanjuje dupliranje koda.
Ispitivanje svih kombinacija operacija kroz for petlje je jednostavno i logično, a provera deljenja sa nulom dodaje sigurnost.
Efikasnost je dobra za zadati opseg brojeva, a kod je lakše održiv od prve varijante sa switch naredbama.
Prioritet operacija je pravilno implementiran unutar funkcije calculate, što pokazuje razumevanje matematičkih pravila i logike kontrolnog toka.
Moguća poboljšanja uključuju:
- Dalja modularizacija, npr. kreiranje funkcije za generisanje svih kombinacija operatora.
- Korišćenje rekurzije ili backtracking pristupa za fleksibilnije proširenje na više operatora ili brojeva.
- Proširenje provere validnosti izraza kako bi se obuhvatili slučajevi celobrojnog deljenja sa ostatkom i veći brojevi.
Rešenje 3 - Tačan izraz (rekurzija / backtracking, sa poštovanjem prioriteta operatora)
Na ulazu imamo četiri cela broja a, b, c i d.
Potrebno je da proverimo da li postoji izbor dve operacije op1 i op2 iz skupa +, -, *, /
tako da izraz a op1 b op2 c = d bude tačan. Ako postoji rešenje, ispisuje se odgovarajući izraz (npr. 1+2*3=7),
a ako nema rešenja — ispisuje No solution.
Ideja ove varijante je da generišemo sve kombinacije dvaju operatora rekurzivno (backtracking pristup),
pri čemu se sada vodi računa o prioritetu operatora. Ako drugi operator ima viši prioritet od prvog,
prvo se računa izraz u zagradi (b op2 c). U suprotnom, računanje ide redom (a op1 b) op2 c.
Kod:
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
// applyOp: izvrši operaciju x op y, vrati pair(valid, value)
pair<bool, long long> applyOp(long long x, char op, long long y) {
if (op == '+') return {true, x + y};
if (op == '-') return {true, x - y};
if (op == '*') return {true, x * y};
if (op == '/') {
// zaštita: deljenje sa nulom
if (y == 0) return {false, 0};
// zahtevamo tačno celobrojno deljenje bez ostatka
if (x % y != 0) return {false, 0};
return {true, x / y};
}
return {false, 0}; // nepoznat operator
}
// prioritet operatora
int priority(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
vector<char> ops = { '+', '-', '*', '/' };
bool found = false;
vector<char> chosen(2);
// dfs bira operatore rekurzivno
void dfs(int pos, long long a, long long b, long long c, long long d) {
if (found) return; // prekid ako je već pronađeno
if (pos == 2) {
if (priority(chosen[0]) >= priority(chosen[1])) {
// (a op1 b) op2 c
auto p1 = applyOp(a, chosen[0], b);
if (!p1.first) return;
auto p2 = applyOp(p1.second, chosen[1], c);
if (!p2.first) return;
if (p2.second == d) {
cout << a << chosen[0] << b << chosen[1] << c << "=" << d << '\n';
found = true;
}
} else {
// a op1 (b op2 c)
auto p3 = applyOp(b, chosen[1], c);
if (!p3.first) return;
auto p4 = applyOp(a, chosen[0], p3.second);
if (!p4.first) return;
if (p4.second == d) {
cout << a << chosen[0] << "(" << b << chosen[1] << c << ")" << "=" << d << '\n';
found = true;
}
}
return;
}
for (char o : ops) {
chosen[pos] = o;
dfs(pos + 1, a, b, c, d);
if (found) return;
}
}
int main() {
long long a, b, c, d;
if (!(cin >> a >> b >> c >> d)) return 0;
dfs(0, a, b, c, d);
if (!found) cout << "No solution" << '\n';
return 0;
}
Objašnjenje:
Ulazni podaci: Program čita četiri broja: a, b, c, i d.
Operatorima: sabiranje (+), oduzimanje (-), množenje (*), i celobrojno deljenje (/).
Prioritet operacija: ako je drugi operator višeg prioriteta (npr. * ima prednost nad +), prvo se računa deo u zagradi.
Provera deljenja: u slučaju deljenja sa nulom ili necelobrojnog rezultata, izraz se preskače.
Ispis: ako postoji kombinacija operatora koja daje tačan rezultat, ispisuje se izraz; ako ne — ispisuje se No solution.
Komentar na rešenje:
Ova verzija koristi rekurziju i jasnu podelu slučajeva na osnovu prioriteta operatora. Time se dobija ponašanje identično matematičkom sistemu evaluacije izraza u C++ jeziku. Kod je čitljiv i precizno razdvaja logiku za situacije sa i bez zagrada, čime se izbegava višestruko računanje i nepotrebne kombinacije.
Moguća poboljšanja:
- Proširenje na više operatora i operanada uz rekurzivno računanje prioriteta.
- Čuvanje svih mogućih tačnih izraza umesto samo prvog.
- Dodavanje automatskog formatiranja izraza radi preglednijeg ispisa.