Clasa a VI-a lecția 6 - 25 oct 2018

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

  • Unii din voi nu închideți fișiere. Aceasta arată că voi de fapt scrieți programul cu freopen și apoi îl convertiți. Foarte foarte rău: Cemârtan, Cojocaru, Mușat, Dobre, Nicu, Teodorescu. Dacă la double K se acceptă, la IQ Academy nu. A nu respecta o cerință banală înseamnă că nu ai nici o șansă să înveți ceva elevat, deci nu ai ce căuta printre noi.

Monsters

Problema monsters

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Badea, Calotă, Chivu, Cojocariu, Coman. Dragomir, Dumitrescu, Grecu, Hossu, Iordache, Rebengiuc, Voicu, Fares, Ilie.
  • Unii din voi au verificat dacă c este diferit de '0', caz în care l-au transformat în '1'. Foarte simpatic :)
  • Unii din voi au folosit vectori. Nu e grav, dar se poate fără, iar programul rezultat este mai simplu și mai scurt.
  • Unii din voi au calculat cea mai mare putere a lui 10 care încape în număr într-un mod complicat și care poate da depășiri. Pentru a evita depășirea de long long ați folosit tipul unsigned long long. Ceea ce nu veți putea mereu, acum a funcționat șmecheria, dar pentru viitor învățați metoda folosită în lecția anterioară, în care pornim cu cea mai mare putere a lui 10 și o împărțim la 10 pînă ce încape în număr.
  • Unii din voi nu s-au prins că rezultatul final nu este un long long ci este un întreg: poate fi maxim 1 cu 18 zero în baza doi, adica 218 adică aproximativ 250000.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Simon.

Comentarii individuale

Grupa de dimineață

  • Aizic: rezolvare foarte bună, bravo! Ca idee, nu era necesar să declari n de tip long long, int era suficient. Dacă în loc de if(ch!=0) scriai if(ch!='0') luai 100p.
  • Badea: rezolvare foarte bună, bravo!
  • Benescu: rezolvare corectă, dar complicată și lunguță. Tu ai trei etape: calcul număr cifre și al puterii lui 10, apoi pe baza numărului de cifre și a puterii lui 10 extragi cifrele numărului în ordine într-un vector, apoi calculezi numărul transformat pe baza acelui vector. Puteai să calculezi totul într-o etapă. Dar fiecare etapă este complicată în parte: cînd ai avut vreodată nevoie de numărul de cifre al unui număr? Nici aici nu ai nevoie decît de puterea lui 10. Pe care o puteai calcula mai ușor, fără să îți faci griji de depășire, cu metoda de la curs, pornind invers, cu cea mai mare putere a lui 10 posibilă, 1018. În etapa a doua pui cifrele în vector, de la stînga la dreapta. Era mult mai simplu să le pui de la dreapta la stînga, caz în care nici nu mai aveai nevoie de puterea lui 10 calculată la etapa întîi. Apoi aveai grijă să parcurgi vectorul în sens invers. Vezi te rog mai jos rezolvarea de o singură etapă, fără vectori.
  • Burac: rezolvare foarte corectă. Ar fi fost și mai drăguță dacă o rezolvai fără vectori, vezi soluția de mai jos.
  • Calotă: rezolvare foarte corectă și bună, bravo! De ce ai renunțat la prima variantă? Ar fi mers perfect și aceea dacă în loc de if ( n % 10 > 1 ) scriai if ( n % 10 > 0 ).
  • Cemârtan: nu închizi fișiere. Rămășițe de la freopen. Ai declarat toate variabilele de tip long long, pînă și vectorul de cifre binare. Neglijență mare. Ai inițializări de variabile la declarare. Vector declarat în interiorul lui main. Ai avertismente de compilare, setează opțiunile -O2 și -Wall în CodeBlocks. Avertismentul este unul serios, afișezi un long long cu %d în loc de %lld. Cel mai probabil de aceea pici testul 7. Soluția ta este corectă, dar foarte complicată, are patru etape: 1 - calculezi numărul de cifre, 2 - extragi cifrele în vector cu modificare la 0/1, 3 - recompui numărul original dar cu cifrele modificate, 4 - din acel număr calculezi numărul în baza doi. Primele două etape se puteau face împreună, nu? Și ultimele două la fel, de ce ai nevoie să recompui un număr în baza zece, puteai să calculezi numărul direct în baza doi din vector.
  • Chivu: o soluție foarte bună, bravo! Te-ai prins că nu ai nevoie de long long pentru numărul de afișat, bravo! Ce înseamnă să ratezi un semn =, nu-i așa? ;-) Genul acesta de buguri e bine să nu îl faci pentru că este foarte greu de prins. Trebuia să îți creezi teste care să conțină toate cifrele zecimale, inclusiv '1'.
  • Cojocariu: rezolvare foarte bună, bravo!
  • Cojocaru: Nu închizi fișiere. Rămășițe de la freopen. Ai lăsat un printf de debug în cod, nu mai face asta te rog. Rezolvare corectă, dar complicată. Ai trei etape: 1 - calculezi un număr în baza zece cu cifre 0/1, 2 - răstorni acel număr în baza zece, 3 - pe baza răsturnatului calculezi numărul în baza 2. Puteai folosi doar etapa 1 în care calculai un număr în baza 2, în loc de baza 10. Vezi mai jos o soluție într-o singură etapă. Însă adevăratul motiv pentru care nu îți funcționează e faptul că n și r sînt int în loc de long long. Mai clar decît enunțul care îți spune că numărul este maxim 1018 nu văd cum se poate. Mai multă atenție te rog, ești clasa a șasea.
  • Coman: rezolvare foarte bună, bravo!
  • Dragomir: rezolvare foarte bună, bravo!
  • Dumitrescu: rezolvare foarte bună, bravo!
  • Grecu: rezolvare foarte bună, bravo! Cine este Mike? :)
  • Hossu: rezolvare foarte bună, bravo! Atenție, nu era necesar să declari n ca long long, int era suficient.
  • Iordache: rezolvare foarte bună, bravo!
  • Mocanu: o soluție bună, dar din trei etape: 1 - calcul putere a lui 10, 2 - calcul număr modificat cu cifre 0/1, 3 - calcul număr baza 2. În realitate puteai foarte bine să compui ultimele două etape, pe măsură ce calculai cifrele zecimale să le aduni ca puteri ale lui doi la rezultat. Dacă nu făceai citirea aia ciudată cu test de feof ți-ar fi mers din prima, aplică ceea ce știi, nu te mai aventura în necunoscut, mai ales cînd nu e o soluție mai bună. Nu te-ai prins că puterea lui 10 este și ea long long, neglijent. Iar la final, ca să fii sigur, le-ai făcut pe toate long long, cînd rezultatul final, este int, iarăși neglijent. Mai multă atenție te rog.
  • Mușat: o rezolvare bună și corectă, dar complicată. Ai trei etape, 1 - citire cifre în vector, 2 - transformare cifre vector la cifre binare, 3 - calcul număr baza doi. În realitate cele trei etape se puteau combina și nu mai aveai nevoie de vector, programul fiind mai scurt și mai eficient. Atenție, nu închizi fișiere, rămășiță de freopen.
  • Nicola: o rezolvare bună, bravo. Te-ai prins de problema de depășire, bravo! Ai făcut conversia la unsigned long long. Și mai elegant era să pornești invers, cu cea mai mare putere a lui 10, cum am făcut la ore, și nu mai aveai nevoie de unsigned long long. Te-ai prins și că rezultatul final este int, bravo. Dar ai două etape, era suficientă una. Puteai să extragi cifrele în ordine inversă, de la coadă la cap, și să le aduni înmulțite cu o putere a lui doi care tot creștea. Vezi soluția de mai jos.
  • Petcu: rezolvare foarte bună, bravo! Neatenție mare la enunț: spunea clar că numărul de la intrare poate fi maxim 1018. Neglijență mare la prima sursă. La fel de mare și la a doua sursă, unde nu ai observat că rezultatul este int, nu long long. Ai preferat să nu riști și să pui totul long long.
  • Rebengiuc: rezolvare foarte bună, bravo! Einstein ar fi mîndru!
  • Rughiniș: rezolvare foarte bună, bravo! Atenție la finețuri, numărul rezultat nu este un long long ci un întreg.
  • Stoian: rezolvare foarte bună, bravo! Atenție la finețuri, numărul rezultat nu este un long long ci un întreg.
  • Ștefănescu: rezolvare foarte bună, bravo! Atenție la finețuri, numărul rezultat nu este un long long ci un întreg.
  • Togan: Trei trimiteri. Ultima este cea în care ai eliminat încîlcelile specifice ție. Dacă nu scriai încîlcit încă de la început ai fi reușit din prima. Oricum, se vede că progresezi, bun! Atenție la finețuri, numărul rezultat nu este un long long ci un întreg.
  • Voicu: rezolvare foarte bună, bravo!

Grupa de după-amiază

  • Asgari: o rezolvare bună, bravo. Dar ai două etape, care pot fi ușor comasate în una singură. De asemenea ai un cod neglijent, ai un test if ( a % 10 != 0) iar pe ramura else scrii x = x + ( a % 10 ) * put;. Adică înmulțești put cu zero, frumos. În plus nu te-ai prins că rezultatul final este un întreg, nu un long long.
  • Cadîr: o rezolvare bună și corectă, bravo! Însă ai două etape care se pot foarte ușor combina în una singură, dacă te uiți la codul tău. Caz în care nici nu mai ai nevoie de vector. În plus nu te-ai prins că rezultatul final este un întreg, nu un long long.
  • Dobre: o rezolvare bună, dar lungă și destul de încîlcită. Tu ai 4 etape: 1 - calcul puterea cea mai mare a lui 10 care încape în număr, 2 - refacere număr astfel încît să aibă doar cifre 0/1, 3 - calcul număr cifre ale numărului, 4 - calcul număr final în baza doi. E puțin excesiv, puteai încă din etapa doi, pe măsură ce extrăgeai cifrele numărului, să și calculezi numărul în baza doi folosind acele cifre. De asemenea fii atent la eficiență: în ultima etapă, în bucla while, tu recalculezi puterea lui doi pornind de la 1, întotdeauna. Puteai să te folosești de vechea putere a lui doi și doar să o înmulțești cu doi, nu? Nu te-ai prins că rezultatul final este un întreg, nu un long long.
  • Fares: rezolvare foarte bună, bravo!
  • Ilie: rezolvare foarte bună, bravo! Sfat: inițializează variabilele cît mai "jos" posibil. Adică, preferabil, chiar înainte ca ele să fie folosite. Astfel codul devine mai ușor de citit. Mă refer la acel int n=0;. În general nu e o idee bună să inițializezi variabilele la declarare, tocmai din motive de citire ușoară a codului.
  • Ipate: rezolvare bună. Dar din două etape: 1 - citire cifre în vector, 2 - parcurgere vector și calcul rezultat final. Se vede de la distanță că poți combina cele două etape, ceea ce înseamnă că scapi de vector. Atenție: ultimul while este de fapt un for, nu-i așa? Atenție: ai declarat foarte neglijent vectorul cif[60]. El poate avea maxim 19 cifre, nu-i așa? Rezultă direct din enunț.
  • Marcu: rezolvare bună. Precum ai remarcat, ignorarea avertismentelor de compilare te poate duce la a lua scor zero la o problemă, grav! La fel și calculul neglijent al depășirilor, problema sursei doi. De ce nu calculezi puterea lui 10 așa cum am făcut la curs, pornind de la puterea maximă în jos? Acea variantă nu are cum să depășească. De data asta a mers șmecheria cu unsigned long long, dar următoarea problemă s-ar putea să îți dea limita mai mare și să nu mai poți face asta. Tu ai trei etape: 1 - calcul putere a lui 10, 2 - extragere cifre în vector de la stînga la dreapta, 3 - calcul număr în baza doi din vector. Prima și a doua etapă se combină banal, dacă extragi cifrele numărului de la dreapta la stînga, iar în a trei etapa parcurgi invers vectorul. De ultima etapă scapi parcurgînd normal vectorul și folosind o putere a lui doi care tot crește. În acest fel nu mai ai nevoie de vector, vezi te rog soluția de mai jos. Faci o copie a lui n, dar ulterior nu mai ai nevoie de el, puteai să nu îl copiezi. Eleganța, Ilinca, unde este ea? :) Te-ai prins că rezultatul final este int, bravo.
  • Nicu: rezolvare bună, dar lungă, încîlcită și neelgantă. Tu ai trei etape: 1 - calcul putere a lui 10, 2 - transformare număr astfel încît să conțină doar cifre 0/1, 3 - calcul număr în baza doi din numărul anterior. Etapa unu este neelegantă pentru că eviți depășirea folosind tipul unsigned long long, în loc să scrii metoda din lecția trecută, în care nu ai această problemă deloc. Etapa 2 este OK, doar că se putea combina cu etapa 1: extragi cifrele de la coadă și aduni în noul număr puteri ale lui zece pe care le crești. Etapa trei este remarcabil de încîlcită. Tu scrii r=r+(p2-((nr2%2+1)%2)*p2); cînd puteai să scrii mult mai simplu r=r+nr2%10*p2). Din nou, ultima etapă putea fi combinată cu primele două dacă adunai în noul număr puteri ale lui doi în loc de ale lui 10. Vezi te rog o soluție mult mai simplă mai jos.
  • Simon: nimic?
  • Stancu: o rezolvare bună, bravo. Dar ai două etape, 1 - extragere cifre număr în vector avînd grijă să fie doar 0/1, 2 - calcul rezultat pe baza acelui vector. Etapele puteau fi combinate dacă foloseai o putere a lui doi care tot creștea. Dar ai și alte probleme: de exemplu nu te-ai prins că rezultatul nu este long long ci int. Folosești vectorul de la 1 și nu de la zero fără nici un motiv bun. Mai mult, greșești dimensiunea acelui vector, deoarece ai rezervat loc pentru doar 19 cifre. Dar dacă pornești de la 1 vei avea nevoie de un element în plus, adică 20 de cifre. Mai multă atenție și disciplină, te rog!
  • Tatomir: o rezolvare bună, bravo! Puteai să o faci puțin mai simplă dacă extrăgeai cifrele în ordine inversă și foloseai o putere a lui doi pentru a le aduna. Te-ai prins că rezultatul este întreg, nu long long, bravo!
  • Teodorescu: Nic, tu trebuie să îți corectezi stilul, dacă vrei să fii aici cu noi. Enumăr mai jos toate problemele și te rog ca pe viitor să nu mai faci aceste greșeli, sau ne supărăm: ignori avertismente de compilare! Setează te rog -Wall și -O2 în CodeBlocks. Inițializezi variabilele la declarare, nu! Inițializează-le cît mai "jos" posibil, aproape de locul unde vor fi folosite. Uiți să închizi fișiere, te rog să scrii încă de la început atît deschiderea cît și închiderea de fișier. Declari toate variabilele long long sau unsigned long long, nu! Declararea se face pe tipul corect, calculînd valoarea lor maximă. Este absolut urît, neelegant și ineficient să ai inclusiv indicii unui for declarați ca long long. Niciodată nu ai voie să ai return 0; undeva în mijlocul lui main(). Doar la final! Cînd programul are mai multe etape, te rog să îmi scrii un mic comentariu în legătură cu ce face acea etapă. Soluția ta este una foarte lungă, imprecisă și neelegantă, opusul a ceea ce ne propunem noi aici. Gîndește bine algoritmul înainte să te apuci să scrii în CodeBlocks. La final dă-ți cît mai multe teste înainte de a trimite la varena. Acestea fiind zise, iartă-mă, am făcut eforturi, dar nu am reușit să înțeleg ce faci acolo. Comentariile ar fi ajutat. Este extrem de lung, vezi te rog o soluție banală mai jos.

Suprapuneri

Problema suprapuneri

Comentarii generale

  • Felicitări celor ce au reușit să rezolve problema: Chivu, Cojocariu, Grecu, Hossu, Mușat, Nicola, Petcu, Rebengiuc, Ștefănescu, Voicu, Asgari, Fares, Ilie, Ipate, Marcu, Tatomir.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Aizic, Calotă, Cemârtan, Cojocaru, Coman, Dumitrescu, Mocanu, Simon, Stancu

Comentarii individuale

Grupa de dimineață

  • Aizic: nimic?
  • Badea: opt surse trimise. Programare aproximativă. Ignori avertismente de compilare foarte importante, %d în loc de %lld. Ideea este bună. Nu ai luat 100p pentru că ai considerat doar cazul cînd n e mai mare ca n. Dacă luai numărul de cifre și puterea lui doi ca maxim între cele două numere programul lua 100p.
  • Benescu: mai întîi partea "tehnică": ai declarat toate variabilele de tip long long, absolut neglijent și neelegant! Nu mai face asta, calculează tipul variabilelor luînd valoarea maximă ca reper. Mai departe, calculezi numărul de cifre zero și unu într-un mod neeficient, parcurgînd cifrele de la stînga la dreapta. Era mai ușor de la dreapta la stînga, nu mai aveai nevoie de puterile lui 2. Ca algoritm, nu mi-e clar cum ți-a venit o asemenea idee. Ce legătură are cmmdc dintre numărul de cifre binare zero și unu cu soluția? E deajuns să iei un exemplu, gen 10 și 12, ale căror reprezentări binare sînt 1010 și 1100, care nu au nici o suprapunere, dar al căror numere de cifre zero și unu sunt 2 și 2, cu cmmdc 2. E surprinzător cîte puncte ai luat cu o aiureală :)
  • Burac: codul tău calculează numărul de cifre binare unu din numărul mai mare dintre cele două de la intrare. Ce legătură are asta cu ceea ce se cerea, anume numărul de egalități între rotații? Nu ai încercat să faci rotațiile, e uimitor că ai luat puncte cu trăznaia asta.
  • Calotă: nimic?
  • Cemârtan: nimic?
  • Chivu: o rezolvare foarte bună, bravo! Te-ai complicat puțin calculînd numărul de cifre, cînd nu aveai nevoie decît de puterea lui doi. Iar la generarea rotațiilor folosești un mrot inutil, puteai să lucrezi chiar cu m. Altfel foarte bine!
  • Cojocariu: o soluție care funcționează, complicată, dar inedită, interesant! Te-ai descurcat într-un cod deloc ușor. Calculezi la fiecare iterație numărul x care este rotația lui m, pe care îl ții neschimbat. Codul ar fi fost mai simplu dacă calculai x pe baza x-ului anterior. Oricum, felicitări pentru că l-ai dus pînă la capăt. Singurul test pe care îl pici este un caz particular, cînd ambele numere sînt zero.
  • Cojocaru: nimic?
  • Coman: nimic?
  • Dragomir: algoritmul tău folosește vectori, de aceea a fost respins de varena. Însă ai și greșeli de logică, ai un singur vector de cifre, în care scrii cînd n cînd x. Ideea ar putea să funcționeze, dar nu cred că ți-ai dat teste pe acel program.
  • Dumitrescu: nimic?
  • Grecu: o rezolvare bună, felicitări! Te-ai complicat puțin calculînd numărul de cifre, cînd nu aveai nevoie decît de puterea lui doi. Ai grijă, codul e un pic greu de urmărit, deoarece tu nu calculezi numărul de cifre, ci numărul de cifre minus unu. La fel și la final, tratezi una din comparații separat. Acestea sînt mici încîlceli de care e bine să scapi.
  • Hossu: felicitări pentru rezultat! E în regulă să încerci lucruri noi, dar asta nu te absolvă de cele vechi. De exemplu, fscanf (fin, "%lld %lld", &m, &n);, unde lași un spațiu între %d și %d. V-am repetat de multe ori, nu se lasă spațiu. Este un obicei periculos. Pentru că folosești lucruri noi le folosești ineficient. De exemplu:
  a = 1
  for (i = 0; i < (nrCif - 1); i++)
    a = a << 1;

se scrie mult mai simplu 

a = 1 << (nrCif - 1);

. Mai mult, dacă vrei să calculezi în a cea mai mare putere a lui 2 care încape în max aceasta se poate face mai simplu în mod clasic. Ideile tale sînt bune și experimentează cu operații pe biți, dar programul tău a ieșit mai lung și mai complicat decît dacă nu le foloseai, vezi soluția de mai jos.

  • Iordache: drăguț că măcar ai încercat ceva. La olimpiadă conta faptul că ai luat 30p. Dar la temă pescuitul e aiurea. Dacă te-ai împotmolit trebuia să ceri ajutorul, mie sau pe listă.
  • Mocanu: nimic?
  • Mușat: nu închizi fișiere, rămășițe freopen, ne supărăm! Nu mai inițializa variabile la declarare, inițializează-le înainte de bucla care le folosește! Nu lăsa printf-uri de depanare în cod! Soluția ta este foarte bună, altfel, felicitări! Dar se vede din ea că încă nu conștientizezi foarte bine ideea de baza doi. Oare dacă aveai de numărat suprapunerile în baza zece ai fi procedat la fel? Comparai numerele cifră cu cifră? Era mai simplu să execuți rotațiile, compunînd numerele, iar apoi făcînd direct comparații de numere. Vezi soluția de mai jos.
  • Nicola: simpatică soluția :) Felicitări că ai reușit pînă la urmă. Însă folosind lucruri noi le folosești greșit. De exemplu testul if ( ( a ^ b ) == 0 ) se scrie mai simplu if ( a == b ). Cînd ai un ciocan în mînă toate obiectele din jur par cuie, nu-i așa? Iar codul
    b1 = ( ( a & put ) > 0 )? 1 : 0;
    if ( b1 == 1 )
      a -= put;
    a <<= 1;
    if ( b1 == 1 )
      a ^= 1;

se scrie banal 

a = (a >> (x - 1)) + (a << 1)

. În schimb tratezi una din comparații în afara buclei de rotații, neelegant, de ce? Nu mai bine mai făceai o rotație?

  • Petcu: rezolvare foarte, foarte bună, bravo! În fapt atît de bună și din prima submisie încît am mari dubii că este făcută de tine.
  • Rebengiuc: o soluție foarte bună! Felicitări!
  • Rughiniș: Remus, ideea ta ar putea funcționa. Dar se vede că încă nu înțelegi bine conceptul de baza doi. Tu construiești un număr în baza zece care are ca cifre cifrele din baza doi. De ce ai face asta? Pentru că ții să lucrezi în baza zece. Puteai să faci toate acele rotații direct în baza doi, fără să mai treci prin zece. Pe lîngă că e inutil și deci ineficient, mai ai o problemă: numerele în baza doi au circa 60 de cifre, deci nu vor încăpea pe long long atunci cînd le vei trece la numere cu 60 de cifre în baza zece. Altfel programul este corect.
  • Stoian: rezolvarea ta nu e corectă, dar bănuiesc că știi asta. Nu calculezi ceea ce ți se cere, ci niște aproximări care nu au legătură cu calculul. La olimpiadă e OK, la temă nu. Dacă te împotmolești cere ajutorul, te rog.
  • Ștefănescu: rezolvare foarte bună. Pici un singur test, cînd ambele numere sînt zero. Ca idei de eleganță: poți calcula în același timp și puterea lui doi, cît și numărul de cifre binare. Mai mult, dacă te uiți la codul tău, tu nici nu ai nevoie de numărul de cifre. Ultima buclă și penultima se execută de același număr de ori, ai fi putut să pui corpul ultimei bucle în interiorul penultimei bucle.
  • Voicu: ai trimis cod la arhivă, te rog nu mai greși. Ți-am ajustat scorul în mod corect. O rezolvare foarte bună, felicitări! Păcat că ai cam ajustat-o de multe ori.

Grupa de după-amiază

  • Asgari: Armin, pescuitul interzis în zona IQ Academy! Ce-i cu programarea aia aproximativă? Șase surse trimise? Fă-ți te rog teste! Ne supărăm! Comentariile sînt la ultima sursă. Ai văzut avertismentul? Ai declarat o constantă ca int cînd ea era unsigned long long. De ce îl ignori? Mai ales că e destul de clar că nu ai nevoie de unsigned long long. Altfel, rezolvarea ta este foarte bună, felicitări.
  • Cadîr: ideea ta ar putea funcționa. Dar se vede că încă nu înțelegi bine conceptul de baza doi. Tu construiești un număr în baza zece care are ca cifre cifrele din baza doi. De ce ai face asta? Pentru că ții să lucrezi în baza zece. Puteai să faci toate acele rotații direct în baza doi, fără să mai treci prin zece. Pe lîngă că e inutil și deci ineficient, mai ai o problemă: numerele în baza doi au circa 60 de cifre, deci nu vor încăpea pe long long atunci cînd le vei trece la numere cu 60 de cifre în baza zece. Altfel programul este corect.
  • Dobre: nu închizi fișiere! Rămășițe freopen, ne supărăm! Nu am o problemă să înveți și de la K, însă nu rele și în nici un caz nu ceea ce am interzis în mod explicit. Ideea ta este bună, felicitări! Problema este că testezi greșit înmulțirea lui n cu doi. Tu pui condiția while ( m / n > 1) care nu e corectă, tu trebuie să compari cu p2 nu cu m. Corect era while ( n * 2 < p2 ). De asemenea nu tratezi cazul particular cînd ambele numere sînt zero.
  • Fares: rezolvare foarte bună, bravo! Ai grijă la codul duplicat, cele două ramuri ale primului if sînt identice, mai puțin inițializarea variabilei copie.
  • Ilie: important: nu inițializa variabilele la declarare! Inițializează-le chiar înainte de bucla care le folosește sau le calculează. Altfel codul devine necitibil. Soluția ta este foarte bună, felicitări! Dar se vede din ea că încă nu conștientizezi foarte bine ideea de baza doi. Oare dacă aveai de numărat suprapunerile în baza zece ai fi procedat la fel? Comparai numerele cifră cu cifră? Era mai simplu să execuți rotațiile, compunînd numerele, iar apoi făcînd direct comparații de numere. Vezi soluția de mai jos.
  • Ipate: soluție foarte bună, bravo! Codul ieșea încă și mai scurt dacă te prindeai de două chestii: primele două while-uri se puteau combina punînd condiția while( p2 > n && p2 > m ). Și ca să calculezi prima cifră a numărului, zero sau unu, împarțeai numărul la p2.
  • Marcu: rezolvare foarte bună, bravo! Cred că ai făcut-o cînd erai obosită, sau pe grabă, căci codul tău are mărunțișuri greșite. De exemplu variabila n2 nu are nici un rost, puteai să calculezi totul direct în n. De asemenea, a doua buclă unde ajustezi p2 este inutilă, nu se va intra niciodată în ea. Ceea ce este foarte bine, căci nu ai voie să schimbi p2 în timpul rotațiilor!
  • Nicu: nu închizi fișiere! Rămășițe freopen. Ne supărăm! Ideea de rezolvare este bună. Cred că nu ia toate testele pentru că nu ai luat în considerare cazul cînd m<n. Modul în care calculezi nr din m este complicat. Era mai simplu să calculezi nr pe baza nr din bucla anterioară. Vezi soluția de mai jos.
  • Simon: nimic?
  • Stancu: nimic?
  • Tatomir: rezolvare foarte bună, bravo! Mulțumesc pentru comentarii, au ajutat. Vezi și soluția de mai jos care este puțin mai simplă.
  • Teodorescu: nu inițializa variabilele la declarare. Inițializează-le înainte de bucla unde le vei folosi, altfel codul devine necitibil. Ai grijă și la indentare, din același motiv. Ideea ta ar putea funcționa. Dar se vede că încă nu înțelegi bine conceptul de baza doi. Tu construiești un număr în baza zece care are ca cifre cifrele din baza doi. De ce ai face asta? Pentru că ții să lucrezi în baza zece. Puteai să faci toate acele rotații direct în baza doi, fără să mai treci prin zece. Pe lîngă că e inutil și deci ineficient, mai ai o problemă: numerele în baza doi au circa 60 de cifre, deci nu vor încăpea pe long long atunci cînd le vei trece la numere cu 60 de cifre în baza zece. Altfel programul pare corect.

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2018-10-25-clasa-6-lectie-info-06-720p.mp4</html5media>

Baze de numerație - continuare

Exercițiu: submulțimile unei mulțimi

Aceasta este o problemă clasică în matematică și informatică.

Rezolvați în clasă următorul exercițiu: să se afișeze toate submulțimile nevide ale mulțimii { 1, 2, 3, ..., n }.

Cum abordăm această problemă? La prima vedere pare foarte grea. Va trebui, probabil, să afișăm toate submulțimile de un element. Aceasta e simplu. Apoi cele de două elemente. Tot simplu, vom selecta perechile cu două bucle for. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle for. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de n. Dar stai! Nu putem scrie un număr variabil de bucle for una într-alta!

Ne trebuie o altă abordare. Vom codifica mulțimile. Cum? Foarte simplu: folosind vectorul lor caracteristic. Pentru fiecare element al mulțimii, de la 1 la n, vom avea un element în vectorul v. Pentru o submulțime dată v[i] este 1 dacă elementul i apare în submulțime.

Acest mod de codificare demonstrează un lucru interesant: numărul de submulțimi al unei mulțimi, incluzînd mulțimea vidă, este 2n. Interesant!

Cum vom folosi acest vector? Destul de neclar. Ne-ar trebui un mod în care să variem toate elementele sale de la zero la unu. Și iar ne întoarcem la buclele for una într-alta. Dar există un mod natural în care elementele pot trece prin toate combinațiile posibile de 0 și 1: dacă în loc să folosim un vector cu n elemente folosim un număr binar cu n cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele n cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

În concluzie, care este algoritmul? Iată-l descris mai jos: 

1. Pentru i de la 1 la 2^n - 1
    1.1 Descompune i în baza 2
    1.2 Pentru fiecare cifră binară 1 care se află pe poziția j
        1.2.1 Afișează j
    1.3 Sfîrșit de submulțime, treci la linia următoare

Remarcați că algoritmul nu folosește vectori! Vă invit să rezolvați problema submulțimi1 la vianuarena, folosind acest algoritm. După ce o rezolvați, pentru verificare, iată codul complet mai jos: 

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, m, i, p2max, p;

  fin = fopen( "submultimi1.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  p2max = 1; // calculam 2^n, numarul pina unde trebuie sa numaram
  for ( i = 0; i < n; i++ )
    p2max *= 2;

  fout = fopen( "submultimi1.out", "w" );
  for ( i = 1; i < p2max; i++ ) {  // numaram de la 1 la 2^n exclusiv
    m = i;                         // copiem contorul, sa nu il pierdem
    for ( p = 1; p <= n; p++ ) {   // obtinem pe rind cifrele binare
      if ( m % 2 == 1 )            // 1 inseamna ca pozitia apartine multimii
        fprintf( fout, "%d ", p ); // afisam pozitia cifrei 1, p
      m /= 2;
    }
    fprintf( fout, "\n" );         // am afisat o submultime, linie noua
  }
  fclose( fout );

  return 0;
}

Alte baze

Pînă acum am vorbit numai despre baza 10 și baza 2. Există însă o infinitate de baze. Orice număr întreg poate fi folosit ca bază pentru scrierea numerelor. Exemple:

  • Baza 8 este folosită în sisteme de operare pentru exprimarea drepturilor utilizatorilor asupra resurselor
  • Baza 16 este folosită în calculatoare pentru descrierea succintă a numerelor

Lucrul cu alte baze este similar cu lucrul în baza 2 sau baza 10 așa încît nu avem ce menționa în plus. Nu uitați: principiul de conversie de la baza 10 la baza 2 și invers funcționează și în conversiile de la baza 10 la alte baze și invers. De asemenea funcționează și analogia bazelor.

Să vedem acum folosirea unei baze importante, baza 16.

Baza 16

Baza 16 folosește 16 cifre hexazecimale. Primele 10 cifre sînt cele cunoscute. Următoarele 6 cifre sînt primele litere ale alfabetului latin: A, B, C, D, E și F. A are valoarea 10, B are valoarea 11 și așa mai departe pînă la F care are valoarea 15. De exemplu:

B9A(16) = B×162 + 9×16 + A = 11×162 + 9×16 + 10 =
= 11×256 + 9×16 + 10 = 2816 + 144 + 10 = 2970(10)

Conversia de la baza 2 la baza 16

Pentru a converti un număr de la baza 2 la baza 16 nu este nevoie să trecem prin baza 10. Putem proceda astfel:

  • Grupăm cifrele numărului binar cîte patru, începînd de la dreapta către stînga. Ultima grupă poate să aibă mai puțin de patru cifre binare.
  • Fiecare grup va fi un număr binar între 0 și 15, adică echivalentul unei cifre hexazecimale. Înlocuim aceste grupuri cu cifra echivalentă în baza 16.

Exemplu:

1010110110010110111(2) = 101 0110 1100 1011 0111(2) = 5 6 12 11 7 = 56CB7(16)

Conversia de la baza 16 la baza 2

Pentru a converti rapid un număr de la baza 16 la baza 2 vom proceda în sens invers: vom exprima fiecare cifră hexa ca patru cifre binare, făcînd conversia la baza 2 a valorii cifrei hexa. Exemplu:

56CB7(16) = 5 6 12 11 7 = 101 0110 1100 1011 0111(2) = 1010110110010110111(2)

Constante hexazecimale în C

La problema dublă conversie am avut nevoie să calculăm 260. Avem mai multe variante de a face acest lucru:

  • Putem să calculăm acest număr cu un calculator de buzunar și să îl introducem în program
  • Putem să îl scriem în program ca produsul 1048576LL * 1048576LL * 1048576LL. 'LL' adăugat la finalul unei constante o transformă în constantă de tip long long.
  • Putem să îl calculăm în program într-o buclă for.

Nici una din aceste metode nu este prea elegantă. De aceea limbajul C ne permite folosirea constantelor hexazecimale. Acestea sînt numere scrise în baza 16. Pentru ca compilatorul să își dea seama că sînt numere și nu nume de variabile aceste constante trebuie precedate de '0x'. Exemplu: 0x56CB7. Pentru cifrele mai mari ca 9 puteți folosi litere mici sau mari, nu are importanță.

Astfel:

260 = 1000...(60 zerouri)...000(2) =
1 0000 0000 0000 ...(15 grupe)... 0000(2) = 1000000000000000(16)

Acum avem încă o metodă, mai simplă, de a calcula 260: folosind conversia rapidă de la baza 2 la baza 16 și apoi scriind o constantă hexa:

  • Putem folosi direct constanta hexa 0x1000000000000000LL. Avem 15 cifre 0 hexa, echivalentul a 60 de cifre 0 binare. Observați că numărul se termină cu 'LL' deoarece este o constantă long long.

Vom vedea cu altă ocazie că există o metodă și mai scurtă de a folosi această constantă.

Exerciții cu alte baze

Baza ascunsă

Discuție în legătură cu problema baza ascunsă la varena.

Temă

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_VI-a_lecția_6_-_25_oct_2018&oldid=18077"