Se citeste un numar cu n cifre. Sa se afiseze cel mai mic numar par care se poate forma cu cifrele acestui numar.
Multumesc anticipat
diana.boncoiuser (0)
AniDeȘcoală.ro
Inregistrati-va pentru a beneficia de cunostintele comunitatii, a pune intrebari sau a a raspunde la intrebarilor celorlalti.
Suntem o comunitate care incurajeaza educatia si in care se intalnesc know-how-ul si experienta cu perspective inovative de abordare a problemelor.
Autentificati-va pentru a pune intrebari, a raspunde la intrebarilor celorlalti sau pentru a va conecta cu prietenii.
V-ati uitat parola ? Introduceti adresa de email si veti primi o noua parola.
Please briefly explain why you feel this question should be reported.
Va rugam explicate, pe scurt, de ce credeti ca aceasta intrebare trebuie raportata.
Motivul pentru care raportezi utilizatorul.
Se citeste un numar cu n cifre. Sa se afiseze cel mai mic numar par care se poate forma cu cifrele acestui numar.
Multumesc anticipat
Problema nu pare grea, dar necesita totusi atentie, ca orice alte probleme.
Cel mai mic numar care poate fi format din cifrele unui numar, este de fapt numarul format din cifrele numarului considerat, ordonate crescator.
Spre exemplu, daca avem x = 43251, cel mai mic numar ce poate fi format cu cifrele lui x este 12345.
Cam asta ar fi ideea de rezolvare. Mai concret, o „spargere” a numarului, o stocare a cifrelor numarului intr-un vector, urmata de o sortare a vectorului si apoi de o construire a numarului nou format (sau o afisare directa a numarului)
Cu acest procedeu ar trebui sa incepi. Apoi, ne uitam la conditia impusa de problema. Spune ca trebuie determinat cel mai mic numar par. Asta inseamna ca ultima cifra a numarului cel mai mic (format din cifrele lui n, cum am explicat mai sus) trebuie neaparat sa fie para.
Acest lucru se poate intampla „de sus”, adica daca ai un numar format doar din cifre pare, sau cea mai mare cifra sa fie para, imediat faci numarul minim, si sigur numarul e par.
Daca numarul minim nu e par, el sigur trebuie sa aiba o cifra para, altfel nu ar mai avea sens cerinta. Pentru a obtine numarul par cautat, trebuie interschimbata ultima cifra (care e impara) cu cea mai mare cifra para a numarului. Deci mergi inapoi in vector pana cand intalnesti o cifra para. Evident, vectorul e sortat si prima cifra para pe care o intalnesti e si cea mai mare, deci o interschimbi cu ultima.
Concret:
x-ul de mai sus, devine prin sortare: 12345, ultima cifra e impara, deci suntem pe cazul „nashpa”, in care evident, interschimbam 4 (cea mai mare cifra para) cu 5, si obtinem 12354, care convine.
Alt exemplu: 123034. Aici…avem acel zero, deci o sa puna probleme la sortare, pentru ca va deveni 012334. Va trebui interschimbat acel zero, cu prima cifra nenula din vector, pentru ca putem avea 00001234, deci daca o interschimbam doar cu a doua cifra, era posibil sa fie aceeasi situatiune.
Nu stiu exact ce cazuri ar mai putea fi…dar in principal, asta ar fi ideea de rezolvare, sau cel putin asa as rezolva eu.
Implementarea efectiva a programului se va realiza pe baza observatiilor de mai sus, de catre dvs.
Cum a zis xor_NTG
Cel mai mic numar pe care il poti forma cu numarul tau => cifrele lui sortate crescator.
Ca sa fie par => ultima cifra para permutata cu ultima cifra.
+Rearanjarea zerourilor de la inceput dupa ce vectorul a fost sortat=> primul element nenul de la inceputul vectorului pus in pozitia 0 a vectorului si egalam cu 0 acest numar pe pozitia pe care se afla anterior.
Programul arata asa:
In principiu, cam asa ar arata. Dar ce iti afisaza pentru 14098?
My bad. Am uitat de 0-uri. Am rectificat. Multumesc!
Acum e perfect. Felicitari! Hai sa mergem mai departe, si sa vedem ce putem optimiza la acest algoritm.
Sugestii?
Daca avem de aplicat procedeul asupra unui numar imens de elemente putem folosi quicksort sau heapsort in loc de bubblesort pentru ca in principiu functia de sortare consuma cele mai multe resurse iar solutia bubblesort a fost una simpla si mai usor de inteles desi avea complexitatea O(n^2) in toate cazurile cu exceptia cazului in care vectorul era deja sortat si avea complexitatea O(n).
In rest pentru functia „nrfinal” de reconstruire a unui integer dupa elementele vectorului putem face nr=nr*10+v; ca sa nu facem o atribuire in plus cum am facut anterior, atribuire care este o operatie critica in cadrul functiei nrfinal.
Evident ca putem ca in cadrul functiei main sa afisam numarul direct prin apelul functiei nrfinal fara sa atribuim variabilei nr valoarea returnata de functie si apoi sa afisam nr. Cu toate astea am vrut sa fie mai clar ca rezultatul va fi stocat in acea variabila declarata la inceput, fapt care nu aduce decat o operatie necritica in plus si consuma putina memorie in plus.
Puteam de asemenea sa folosim alocare dinamica pentru vectorul v[].
Daca mai sunt si alte modificari euristice ce pot fi aduse la programul facut dupa abordarea propusa de xor_NTG va rog, postati.
As fi curios totusi sa vad si o alta abordare mai interesanta si mai directa a problemei daca gaseste cineva.
Un inceput excelent…acea functie de sortare trebuie transformata intr-una mai rapida.
La procedeul de interschimbare (folosit de 2 ori in cadrul programului), putem folosi un xor-swap: http://en.wikipedia.org/wiki/XOR_swap_algorithm
Un fel de optimizare ar putea fi considerata afisarea directa a vectorului, care prin unirea elementelor componente ar forma numarul cautat (deci practic evitarea functiei nrfinal). Daca problema spune „sa se afiseze…”, atunci da, asta ar putea fi o metoda de optimizare, pentru ca se afisaza numarul (chiar daca e disociat in componentele unui vector). Daca insa spune: „sa se construiasca numarul obtinut si sa se afiseze”, atunci in mod inevitabil trebuie utilizata acea functie.
Cam asa as face eu…
Depinde cum este interpretat enuntul.
Intr-adevar daca este afisat vectorul direct, el pare a fi un numar. Cu toate astea se zice a afisa un numar si nu elementele unui vector.
Dar evident rezultatul vizual va fi identic deci da, se poate renunta si la reconstituire.