Nr maxim

[alexandru27 0]

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..

[Paul Brahtl 466]

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

[alexandru27 0]

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 466]

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

[alexandru27 0]

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)

[Paul Brahtl 466]

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)

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 0]

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 0]

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 5]

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 466]

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 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

 

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