alexandru27 0 Raportează post Postat Noiembrie 30, 2007 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>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.. Partajează acest post Link spre post Distribuie pe alte site-uri
Paul Brahtl 466 Raportează post Postat Noiembrie 30, 2007 E total aiurea. Care e logica? nr>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<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<=nr[min] atunci min=i Partajează acest post Link spre post Distribuie pe alte site-uri
alexandru27 0 Raportează post Postat Noiembrie 30, 2007 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 Partajează acest post Link spre post Distribuie pe alte site-uri
Paul Brahtl 466 Raportează post Postat Noiembrie 30, 2007 Posteaza tu algoritmul CORECT in pseudocod pentru problema ta si apoi discutam si de traducerea in C++. Partajează acest post Link spre post Distribuie pe alte site-uri
alexandru27 0 Raportează post Postat Noiembrie 30, 2007 daca p>0 atunci max=1 pentr i=2 ,(lungimea nr nr) -p+1 executa daca nr>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) Partajează acest post Link spre post Distribuie pe alte site-uri
Paul Brahtl 466 Raportează post Postat Decembrie 3, 2007 daca p>0 atuncimax=1 pentr i=2 ,(lungimea nr nr) -p+1 executa daca nr>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) Partajează acest post Link spre post Distribuie pe alte site-uri
alexandru27 0 Raportează post Postat Decembrie 5, 2007 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! Partajează acest post Link spre post Distribuie pe alte site-uri
banuj 0 Raportează post Postat Decembrie 7, 2007 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. Partajează acest post Link spre post Distribuie pe alte site-uri
argv 5 Raportează post Postat Decembrie 7, 2007 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 Partajează acest post Link spre post Distribuie pe alte site-uri
Paul Brahtl 466 Raportează post Postat Decembrie 10, 2007 (editat) sugestia de rezolvare ti-am dat-o in primul post algoritmul tau trebuie sa elimine cea mai mica cifra de pe cea mai putin semnificativa pozitie. asa ca o sa parcurgi sirul dar cunr<=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 atunci min=nr index=i sfarsit daca sfarsit pentru j=0 pentru i=0 la n daca i<>index atunci rezultat[j]=nr j=j+1 sfarsit daca sfarsit pentru elimin(rezultat, n-1, k-1) altfel afisez nr sfarsit daca sfarsit subalgoritm Editat Decembrie 10, 2007 de Paul Atreides Partajează acest post Link spre post Distribuie pe alte site-uri