Să se scrie o funcție numită afisareSolutii care primește un număr întreg c și afișează pe ecran toate soluțiile ecuației
x+y+z=c cu proprietatea că x≤y≤z și 0≤x,y,z.
Semnătură funcție
Funcția trebuie să se numească afisareSolutii.
Funcția trebuie să primească un parametru întreg.
Funcția nu va returna nimic, doar va afișa pe ecran soluțiile cerute.
Precizări
Fiecare soluție va fi afișată o singură dată, iar soluțiile vor fi afișate în ordine lexicografică
Un sir veste mai mic lexicografic decât un șir wambele având N elemente dacă ∃i≤N astfel încât v1..i−1=w1..i−1 și vi
Pentru a compara soluțiile, putem să ne gândim că fiecare dintre soluții este un șir cu 3 elemente
Fiecare soluție va fi afișată pe o linie separată.
Restricții
Numărul dat va fi mai mare decât 0 și mai mic decât 501.
Exemplu
afisareSolutii(3) nu va returna nimic și va afișa
0 0 3
0 1 2
1 1 1
Tin sa precizez ca am testat codul de mai jos si am primit limita de timp depasita la un test si nu inteleg cum sa o rezolv , codul este :
#include
using namespace std;
int n;
void afisareSolutii(int c) {
int x, y, z;
for (x = 0; x < c; ++x) {
for (y = x; y < c; ++y) {
z = c - x - y;
if (z >= y) {
cout << x << " " << y << " " << z << endl;
}
}
}
}
int main() {
cin >> n;
afisareSolutii(n);
}
Răspunsuri la întrebare
Tinand cont ca x <= y <= z nu este necesar sa mergem cu x si y pana la valoarea c. Sa ne gandim pana unde putem merge cu fiecare valoare
x = x
y = x + k1
z = y + k2 = x + k1 + k2
unde k1 si k2 sunt numere naturale
x+y+z = c
x+x+k1+x+k1+k2 = c
3x + 2k1 + 2k2 = c
Deoarece toate sunt numere naturale rezulta ca 3x<=c. Deci x nu va putea depasi niciodata c/3. Deci putem optimiza mergand cu x pana la c/3.
E evident ca y+z <= c. Dar deoarece z=y+k2, iar k2 este natural rezulta ca 2y + k2 <= c, deci y nu poate fi mai mare decat c/2. Deci putem optimiza mergand cu y de la x pana la c/2.
► O varianta de cod optimizat ar fi aceasta:
#include <iostream>
using namespace std;
void afisareSolutii(int c) {
int x, y, z;
for (x = 0; x <= c/3; ++x) {
for (y = x; y <= c/2; ++y) {
z = c - x - y;
if (z >= y) {
cout << x << " " << y << " " << z << endl;
}
}
}
}
int main() {
int n;
cin >> n;
afisareSolutii(n);
}
►Nota:
Evita folosirea varibilelor globale atunci cand nu este nevoie.
Nu stiu daca imbunatatirea aceasta e suficienta pentru scor 100%.