[alexandru27]

Am de facut urmatoarea problema :scrieti un program care citeste un numar natural n si un numar de k cifre(mai mic decat numarul de cifre ale nr n) si determina numarul maxim care se poate obtine prin eliminarea a k cifre.Cifrele numarului rezultat isi vor pastra ordinea in numar.
Iata la ce m'am gandit referitor la problema asta(varianta in pseudocod):
subalgoritm construieste (nr,p,rezultat)
daca p>0 atunci
max=1
pentr i=2 ,(lungimea nr nr) -p+1 executa
daca nr[i]>nr[max] atunci max=i
sfarsit daca
sfarsit pentru
rezultat=rezultat+nr[max]
construieste (nr,p-1,rezultat)



nr este numarul dat sub forma de sir de caractereă
rezultat este nr care se cauta
p tine evidenta numarului care se pot alege.




Ce parere aveti..despre varianta mea?(pseudocod) ..Eu trebuie sa rezolv aceasta problema in C++ ...in mod RECURSIV :naughty: Va rog mult sa ma ajutati in rezolvarea acestei probleme..Astept cu nerabdare sfaturile voastre .MULTUMESC ANTICIPAT!!


ps:cele 2 numere naturale se vor citi intr-un fisier..

[Paul Brahtl]

E total aiurea. Care e logica?
nr[i]>nr[max] atunci max=i ->identifici pozitia celei mai mari cifre din sir, la cel mai mare index, de ce?
problema iti cere sa determini cel mai mare numar, asta inseamna sa elimini cele mai mici cifre

rezultat=rezultat+nr[max] -> cu asta chiar m-ai bagat in ceata, de ce faci suma celor mai mari cifre rezultate?

dat fiind ca trebuie sa rezolvi problema recursiv inseamna ca trebuie sa faci functia pentru eliminarea unei cifre si apoi o aplici
algoritmul tau trebuie sa elimine cea mai mica cifra de pe cea mai putin semnificativa pozitie. asa ca o sa parcurgi sirul dar cu
nr[i]<nr[min] atunci min=i
iar la final copiezi sirul initial in rezultat (care va fi tot un sir, nu un numar), exceptand pozitia i determinata

Bafta

P.S. Erata
nr[i]<=nr[min] atunci min=i

[alexandru27]

consideram prima cifra ca fiind maxima..asta inseamna acest lucru...p:s m'ati putea ajuta scriindu'mi o secventa de cod in C++ la programul meu(facut in pseudocod ) folosind recursivitatea...Astept sfaturile voastre in continuare...MULTUMESC ANTICIPAT!!

da cred ca ai dreptate paul...referitor la cifrele ramase..nu stiu cum sa formez o functie care sa elimine cifrele inaintea ,,cifrei maxime gasite''...poate ma puteti ajuta voi

[Paul Brahtl]

Posteaza tu algoritmul CORECT in pseudocod pentru problema ta si apoi discutam si de traducerea in C++.

[alexandru27]

daca p>0 atunci
max=1
pentr i=2 ,(lungimea nr nr) -p+1 executa
daca nr[i]>nr[max] atunci max=i
sfarsit daca
sfarsit pentru
rezultat=rezultat+nr[max]
//se sterg cifrele care nu mai pot face parte din rezultat
construieste (nr,p-1,rezultat)

[Paul Brahtl]

alexandru27, la Nov 30 2007, 05:43 PM, a spus:

daca p>0 atunci
max=1
pentr i=2 ,(lungimea nr nr) -p+1 executa
daca nr[i]>nr[max] atunci max=i
sfarsit daca
sfarsit pentru
rezultat=rezultat+nr[max]
//se sterg cifrele care nu mai pot face parte din rezultat
construieste (nr,p-1,rezultat)

de-aia am si trecut CORECT cu majuscule, ca sa pricepi ca algoritmul tau nu este corect dpdv logic.
sa-ti dau un exemplu: se alege numarul 98031 si k=2
conform algoritmului tau rezultatul este 17 (=9+
conform cerintei din problema rezultatul este 983 (se elimina 0 si 1)

[alexandru27]

paul...te rog frumos sa ma ajuti si pe mine...in rezolvarea acestei probleme....te rog scrie'mi si mie secventa principala a programului...am ramas fara idei..MULTUMESC ANTICIPAT!

[banuj]

alexandru27, la Dec 5 2007, 03:43 PM, a spus:

paul...te rog frumos sa ma ajuti si pe mine...in rezolvarea acestei probleme....te rog scrie'mi si mie secventa principala a programului...am ramas fara idei..MULTUMESC ANTICIPAT!

alg e urmatorul:

1)se retin pozitiile cifrelor 9,8,7,6,5,4,3,2,1,0
2)se completeaza noul numar in modul urmator:


se pun toti 9( daca sunt mai multi decat nrcifre-k at nr cerut e 99999)
se completeaza de la dreapta la stanga noul numar cu cati mai multi de 8( intercalandu-se printre 9, fara a se pune in fata lui 9) samd

3)daca la sfarsit numarul rezultat are mai putine cifre decat nrcifre-k at se pun toti 8 ( cei din fata numarului deja format) si se continua cu pasul anterior.

din pacate alg rezultat foloseste o memorie mult prea mare, dar complexitatea lui este O(nrcifre).

Pentru retinerea pozitiilor se pot fol listele alocate dinamic( pt o alocare eficienta)

pentru nrcifre rezonabil (10 pt n long int) at se poate folosi si alg banal: se elimina toate combinatiile de k cifre si se vede care e nr cel mai mare posibil.



Am notat cu nrcifre numarul cifrelor din nr n.

[argv]

Zici ca trebuie facut recursiv; probabil solutia ceruta este parcurgerea completa a multimii de numere obtinuta prin eliminarea celor K retinand maximul. De ex daca k=2 si numarul este 398 vei avea 39, 38, 98 .. Evident se pot pune conditii de eliminare a unor ramuri care nu pot duce la o solutie, dar probabil nu e in scopul acestei probleme de scoala

[Paul Brahtl]

sugestia de rezolvare ti-am dat-o in primul post

Paul Atreides, la Nov 30 2007, 02:56 PM, a spus:

algoritmul tau trebuie sa elimine cea mai mica cifra de pe cea mai putin semnificativa pozitie. asa ca o sa parcurgi sirul dar cu
nr[i]<=nr[min] atunci min=i
iar la final copiezi sirul initial in rezultat (care va fi tot un sir, nu un numar), exceptand pozitia i determinata

subalgoritm elimin(nr,n,k)
daca k>0 atunci
min=0
index=0
pentru i=0 la n
daca min>=nr[i] atunci
min=nr[i]
index=i
sfarsit daca
sfarsit pentru
j=0
pentru i=0 la n
daca i<>index atunci
rezultat[j]=nr[i]
j=j+1
sfarsit daca
sfarsit pentru
elimin(rezultat, n-1, k-1)
altfel
afisez nr
sfarsit daca
sfarsit subalgoritm

Aceasta postare a fost editata de Paul Atreides: 10 December 2007 - 03:05 PM