Clasa a VI-a lecția 10 - 22 nov 2018

From Algopedia
Revision as of 10:30, 19 March 2021 by Cristian (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Tema - rezolvări

Matrix

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Badea, Burac, Cojocariu, Hossu, Mocanu, Petcu, Rebengiuc, Rughiniș, Voicu, Dobre, Ipate, Marcu.
  • Mulți dintre voi ați folosit un vector suplimentar la rotații. El nu era necesar.
  • Mulți dintre voi ați folosit o a doua matrice! Extrem de rău, la olimpiadă s-ar putea să nu aveți spațiu.
  • Destul de mulți dintre voi ați avut probleme cu citirea caracterelor. Vedeți vă rog mai jos citirea elegantă.
  • Destul de mulți dintre voi ați făcut rotațiile prin interschimburi. Foarte ineficient, trei atribuiri în loc de una singură. Reveniți la baze, recitiți lecția de rotație din clasa a cincea.
  • Avertismente: Cojocaru pentru temă copiată și fentată (!), Dumitrescu pentru greșeli de bază.

Comentarii individuale

Grupa de dimineață

  • Aizic: Te-ai complicat la rotații, vezi mai jos soluția mai simplă.
  • Badea: Bun!
  • Benescu: Bun, dar ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Burac: Bun!
  • Calotă: Te-ai complicat la flip. Folosești variabilele j și j2 care au mereu aceeași valoare, j2 e în plus. Și la rotații te-ai complicat foarte mult, mai și folosești un vector suplimentar. Vezi te rog soluția de mai jos.
  • Chivu: Bun, dar ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Cojocariu: Bun!
  • Cojocaru: Tema ta este clar rezolvată de altcineva. Mai mult, soluția fentează problema, nu execută operații în matrice ci se folosește de o observație pentru a executa operațiuni pe vector.
  • Coman: Bun! Însă: avertisment important de compilare, nu ignora. Citire neelegantă.
  • Dragomir: Bun! Ai grijă la if-uri, ele trebuiau puse unul pe else-ul celuilalt.
  • Dumitrescu: Destul de bine. Ignori reguli de baza: ai declarat matricea in main. Ai declarat matricea de dimensiuni variabile, in loc sa o declari pe maxim, 100. If-urile trebuiau înlănțuite, unul pe else-ul celuilalt. Nu închizi fișiere.
  • Grecu: Ai folosit o matrice suplimentară la rotații. O soluție foarte risipitoare. De ce copiezi matricea în copia ei, la citire? Oricum o suprascrii la rotații. Vezi te rog soluția de mai jos, fără matrice suplimentară.
  • Hossu: Bun!
  • Iordache: ignori reguli de bază: citești c numai pentru a îl transfera în cc, while-ul e de fapt un if (se execută în mod clar o singură dată), nu înlănțuiești if-urile unul pe else-ul altuia. Ideea e interesantă, dar nu funcționează tocmai din cauza greșelii de while versus if, condiția de %2>0, care e corectă pentru flip, nu și pentru rotație.
  • Mocanu: Bun!
  • Mușat: Bun. Rotația ta este ineficientă, face multe interschimburi nenecesare. Copy/paste-ul te-a trădat, ultima rotație este greșită, ai pus incorect limitele de for.
  • Nicola: Bun. Dar ți-ai dat seama că ai o citire ciudată? Doar una din două bucle face ceva util, din cauză că tu citești doar un caracter per buclă, în loc de două. Vezi soluția de mai jos pentru o citire elegantă.
  • Petcu: Bun!
  • Rebengiuc: Bun!
  • Rughiniș: Bun! Dacă făceai și programul ăsta cu while-uri cred ca înnebuneam :)
  • Stoian: Bun! Ai uitat să închizi fișierele! Greșeală de începător, te rog să nu o mai faci.
  • Ștefănescu: Bun! Ai folosit un vector suplimentar. Se poate și fără, vezi mai jos.
  • Togan: Citire foarte urîtă. Dacă testezi un caracter în while nu ai voie ca prima instrucțiune din while să fie o citire a acelui caracter! Am discutat chiar data trecută despre asta, cît de greu e să reții? Rotații ineficiente, prin interschimburi. Nu este necesar, vezi te rog soluția de mai jos.
  • Voicu: Bun!

Grupa de după-amiază

  • Asgari: Bun. Iar ai trimis la arhivă pînă ce ai luat 100p. Ți-am scăzut 10p. Rotații ineficiente, cu interschimburi. Ai uitat clasa a cincea deja? Din cauza lor a trebuit să declari matricea cu un element în plus pe fiecare dimensiune. Urît.
  • Cadîr: Bun! Test incorect de final, cu EOF, trebuia \n. Funcționează și așa, dar face o buclă în plus, degeaba.
  • Dobre: Bun!
  • Fares: Bun! Nu ai închis fișierul de ieșire, atenție! Rotații ineficiente, cu interschimburi. Ai declarat matricea cu un element în plus pe ambele dimensiuni, urît. Vezi te rog soluția de mai jos.
  • Ilie: Bun. Rotații ineficiente, cu interschimburi. Vezi te rog soluția de mai jos.
  • Ipate: Bun!
  • Marcu: Bun!
  • Nicu: Totul ar fi fost minunat dacă nu făceai ciudat ultima rotație. Foarte straniu faptul că ai făcut diferit cele două rotații. Folosești inutil o matrice suplimentară. Ai declarat matricea cu un element în plus pe ambele dimensiuni, urît. Vezi te rog soluția de mai jos.
  • Stancu: E OK, dar ai folosit o matrice suplimentară. Toată ideea era să faci aceste operații în matrice. Ce înseamnă "for(j = 0; j < 1; j++)"? Lenea minții, puteai să scrii doar codul din interiorul acelui for cu 0 în loc de j.
  • Tatomir: Bun! Dar ai o greșeală de bază: nu înlănțui if-urile pe else-uri. Citirea e nu e cea mai elegantă posibil și nici modul cum testezi operația, un pic ineficient.
  • Teodorescu: Bun, dar ai folosit o a doua matrice la rotații. Vezi te rog lecția de anul trecut despre rotații vectori.

Reorganizare

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Hossu, Iordache, Nicola, Petcu, Rebengiuc, Ștefănescu, Togan, Voicu, Asgari, Dobre, Fares, Ilie, Ipate, Tatomir, Teodorescu.
  • Problema este ușoară. Trebuia să luați cu toții scor mare.
  • Mulți dintre voi ați trimis soluția de anul trecut. Care este, evident, creată cu mintea voastră de anul trecut. Algoritmi ciudați, contorsionați, implementări care nu respectă reguli de bază, cum ar fi duplicarea de cod. Soluții chinuite, pe care le-ați trimis fără să gîndiți. IQ Academy este un loc al gîndirii. Dacă vreți să nu gîndiți locul vostru nu este aici.
  • Topul leneșilor care au copiat soluția urîtă de anul trecut, preferînd să scape, nu să facă tema: Aizic, Badea, Calotă, Chivu, Dumitrescu, Mușat.
  • Avertismente: Cojocaru (soluție rudimentară, incompletă), Coman (soluție complet nefuncțională), Dumitrescu (soluție nefuncțională cu copy/paste greșit)

Comentarii individuale

Grupa de dimineață

  • Aizic: Soluția de anul trecut. Repeți cod, scrii i-- pe ambele ramuri ale if-ului, etc. Ai vrut să scapi, nu să rezolvi tema.
  • Badea: Soluția de anul trecut. Atît de ciudată încît nu știu unde să încep să corectez. Folosești vectori, ba chiar mari. Depui cifrele numerelor pînă la 10000, independent de valoarea de la intrare a lui n. Compui și recompui numărul, inversîndu-l, cînd puteai să răstorni cifrele în vector. O soluție urîtă chiar și la nivelul clasei a 5a. Ai vrut să scapi, nu să rezolvi tema.
  • Benescu: Rar o ciudățenie mai mare. Matrice inutilă, algoritm ciudat. Iar varianta 2 este inacceptabilă, are 92KB. De circa nouă ori mai mult decît se permite la olimpiadă și de circa 100 de ori mai mult decît este necesar pentru o sursă decentă. Urît.
  • Burac: Soluție rezonabilă. Cod puțin dezorganizat, repeți cod dar nu la fel, cred că ai cam multe cazuri particulare. Nu lăsa pauză între literă și operator la 'i++' (nu 'i ++').
  • Calotă: Soluția de anul trecut. Folosești inutil un vector. Ai vrut să scapi, nu să rezolvi tema.
  • Chivu: Soluția de anul trecut. O forță brută nedemnă de tine. Ai vrut să scapi, nu să rezolvi tema. Apoi ai trimis exact același lucru la reorganizare2. Crezi că soluțiile tale se încadrează la categoria 'excelență', sau la IQ Academy?
  • Cojocariu: Soluția de anul trecut. Care ar fi foarte rezonabilă dacă nu ai folosi vectori. La nivelul tău să te mulțumești cu o soluție amărîtă, de anul trecut, fără a încerca să o îmbunătățești, înseamnă un singur lucru: ai vrut să scapi, nu să rezolvi tema.
  • Cojocaru: Soluție incompletă. Tratezi numerele cu maxim trei cifre. O solulție slabă chiar și pentru clasa a 5a.
  • Coman: Programul tău nu merge nici măcar pe testul din enunț. Ori problema a fost foarte grea, ori nu ți-ai dat silința. Cred că a doua variantă este cea adevărată.
  • Dragomir: O soluție bună. Care ar fi foarte rezonabilă dacă nu ai folosi vectori. Ai locuri unde programezi aproximativ, de exemplu:
            v[i] = m / p;
            if (v[i] > 9)
                v[i] = v[i] % 10;

Deci numai dacă este mai mare ca nouă îi calculezi ultima cifră? Dacă este chiar cifră nu poți să faci același lucru? Desigur, codul elegant era:

            v[i] = m / p % 10;

Acestea sînt greșeli de începător.

  • Dumitrescu: Soluția de anul trecut. Cu exact aceleași greșeli. Declari un vector de 10 milioane de întregi, serios? Nu închizi fișiere. Soluție simplistă, preferi să repeți cod decît să generalizezi într-o buclă. Mai mult, pare că și copy/paste este prea greu, programul ar funcționa dacă te țineai de regulă, dar începînd cu if(i<1000) sari instrucțiunea v[j+1]=... Folosești un vector, cînd se poate fără.
  • Grecu: Soluția de anul trecut. Folosești inutil un vector. Ai cam vrut să scapi, nu să rezolvi tema elegant. Însă ești iertat pentru că ai dat o soluție de 100p la reorganizare2, care ar fi mers și aici.
  • Hossu: Bun, frumos! O rezolvare de anul trecut, dar care funcționează pentru reorganizare2, foarte bine. Sper că este a ta în totalitate.
  • Iordache: o soluție interesantă. Te-au folosit de numere mari, aduni unu și folosești cifrele numărului. Ești sigur că ajung 4 cifre în vectorul v[]?
  • Mocanu: Soluția de anul trecut. Ea e OK pentru clasa a cincea. La a șasea, ea e destul de încîlcită, cu repetiție de cod, iar algoritmul nu e tocmai cel mai simplu.
  • Mușat: Soluția de anul trecut. Cu exact aceleași greșeli. Nu închizi fișiere. Soluție simplistă, preferi să repeți cod decît să generalizezi într-o buclă.
  • Nicola: O soluție bună și eficientă, chiar dacă e tot cea de anul trecut. Ideea funcționează și pentru reorganizare2. Funcția maschează o ineficiență: tu recalculezi numărul de cifre de la zero la i, apoi crești i și iar recalculezi de la zero la i. Ai fi putut să adaugi doar diferența de la i la i+1. Cu toate acestea rămîne o soluție bună. Ar fi fost interesant să nu duplici cod, vezi soluția de la reorganizare2, de mai jos.
  • Petcu: Bun, bravo! Mă bucur că ai refăcut programul fără vectori. O soluție bună și ordonată. Singura obiecție la cod neelegant:
            if( j == ( n * ( n + 1 ) / 2 ) - n )//daca este prima cifra
                fprintf( fout, "%d ", kc % 10 );//afisam
            if( j == ( n * ( n + 1 ) / 2 ) - 1 )//daca este ultima cifra
                fprintf( fout, "%d", kc % 10 );//afisam

În primul rînd că cele două if-uri se exclud, deci trebuiau înlănțuite. În al doilea rînd că puteau fi combinate cu sau:

            if( j == ( n * ( n + 1 ) / 2 ) - n || j == ( n * ( n + 1 ) / 2 ) - 1 )//daca este prima sau ultima cifra
                fprintf( fout, "%d ", kc % 10 );//afisam

Întrebare: de ce nu ai folosit același program de la reorganizare2, dacă tot l-ai scris?

  • Rebengiuc: Bun, bravo! Soluție matematică, comună cu reorganizare2. Singurul lucru pe care puteai să-l mai încerci ar fi fost să nu repeți cod :)
  • Rughiniș: Soluția de anul trecut. Nu este rea, dar e puțin copilăroasă, cu "while(m>-1)" în loc de "while(m>=0)", "n=0-n;" în loc de "n=-n;", etc. Aș fi vrut să treci din nou prin ea și să o readuci la zi. Dar te iert pentru că ai rezolvat reorganizare2 :)
  • Stoian: O soluție bună. Păcat că folosești vectori. Ei nu sînt necesari.
  • Ștefănescu: O rezolvare bună, bravo. Atenție, ai avertismente de compilare.
  • Togan: O soluție bună și rapidă, care merge și la reorganizare2. Este cam încîlcită, dar ideea și algoritmul sînt bune.
  • Voicu: O soluție bună și rapidă, care merge și la reorganizare2. Ca eleganță, ți-ai creat singur un caz particular atunci cînd testezi dacă r este zero. Trebuia să numerotezi cifrele în șir de la zero, ca în majoritatea dăților cînd numerotarea de la zero este mai bună.

Grupa de după-amiază

  • Asgari: Soluția de anul trecut. Nu este rea, dar nici elegantă. Apar constante ciudate prin ea, folosești vectori. Pe de altă parte ai rezolvat reorganizare2, de ce nu ai folosit acea soluție, mai bună? Care la rîndul ei este foarte încîlcită și neelegantă, dar măcar are complexitate mult mai bună.
  • Cadîr: O soluție rezonabilă. Compui și recompui numărul, inversîndu-l, cînd puteai să răstorni cifrele în vector, direct.
  • Dobre: O soluție rezonabilă. Nu cred că aveai neapărată nevoie de acel vector mic. Ce este neelegant: pentru a doua cifră refaci complet calculele, cînd puteai să continui de unde ai rămas după prima cifră. Repeți cod. Mai rău, repetiția arată un pic altfel decît originalul, foarte ciudat. Însă felicitări pentru soluția la reorganizare2. De ce nu ai folosit-o și la reorganizare?
  • Fares: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Un pic încîlcită, dar se iartă, căci problema e grea :)
  • Ilie: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Ți-ai creat singur cazuri particulare, pentru că nu ai numerotat cifrele de la zero.
  • Ipate: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Mulțumesc pentru comentarii!
  • Marcu: O soluție bună, matematică, care funcționează și la reorganizare2. E cumva hilar că ai făcut un "for" ca să nu repeți cod, dar restul codului este plin de repetiții. Toate acele if-uri, precum și ramurile switch-ului, sînt compactabile într-un for. Dacă vrei să nu repeți cod uită-te în direcția evidentă mai întîi :) Ești iertată pentru ca ai rezolvat reorganizare2.
  • Nicu: Soluția de anul trecut. O soluție corectă, dar încîlcită, cu multe cazuri particulare nereale. Nu închizi fișiere. Dar ești iertat pentru că ai rezolvat reorganizare2. Tot o soluție încîlcită, dar măcar are complexitate bună. De ce nu ai trimis acea soluție și la reorganizare?
  • Stancu: Idee bună, implementare bună, nu ai depanat pînă la capăt. Dacă ți-ai fi construit teste de mînă sigur o reparai. Lene?
  • Tatomir: Soluția de anul trecut. Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2. Un pic încîlcită, dar se iartă, căci problema e grea :)
  • Teodorescu: Bravo, o soluție eficientă, matematică, care funcționează și la reorganizare2.

Rezolvări aici [1]

Lecție

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

Matrice - continuare

Continuăm cu exerciții de bază cu matrice.

Parcurgerea pe diagonale a unei matrice

Rezolvați problema diagonal:

Se citește o matrice pătrată de caractere. Să se afișeze două linii de caractere, fiecare linie conținînd toate caracterele matricei. Prima linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala principală. A doua linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala secundară. Diagonala principală este din coțul stînga sus în colțul dreapta jos. Diagonala secundară este din colțul dreapta sus, în colțul dreapta jos. Atenție! Fișierul de intrare conține numai matricea de caractere, fiecare linie terminîndu-se cu '\n'. Nu se dă n, dimensiunea matricei, trebuie să o deduceți. Exemplu:

Parcurgerea pe diagonale paralele cu diagonala principală
Parcurgerea pe diagonale paralele cu diagonala secundară
Prima linie afișată: minejoafkpbglchd
A doua linie afișată: abecfidgjmhknlop

Zoom x 2

Rezolvați problema zoomx2:

Se citește o matrice pătrată de caractere. Să se construiască o altă matrice în care fiecare caracter apare de două ori pe orizontală și de două ori pe verticală (zoom ori 2). Exemplu:

Matricea inițială
Matricea finală

Am vorbit despre două variante de implementare: una prin parcurgerea matricei originale, care pentru fiecare element completează patru elemente in matricea finală și a doua variantă care parcurge matricea finală și pentru fiecare element calculează corespondentul în matricea originală.

Căutare submatrice în matrice

Rezolvați problema căutare:

Se dau două matrice pătrate, matricea a de dimensiune m și matricea b de dimensiune n. Se știe că 1 ≤ n ≤ m ≤ 100. Să se spună de cîte ori se regăsește matricea b în matricea a. Exemplu:

Matricea a
Matricea b

În acest caz matricea b apare de 13 ori în matricea a.

Aplicație: problema joc1

Am vorbit despre problema joc1 (ONI 2011 clasa a 7-a), care are o implementare ușoară cu condiția să țineți toate matricele de căutat, inclusiv rotațiile lor, într-un vector de 12 matrice cu elemente zero și unu. Astfel, va trebui să declarați un tablou tridimensional inițializat. Necesită atenție la declararea acestui tablou, dar programul se simplifică.

Temă

  • Terminați, la arhivă, problemele făcute în clasă: diagonal, zoomx2, căutare (la arhivă, în afara concursului-temă).
  • Tema 10 clasa a 6a
    • Ținta dată la ONI 2014 clasa a 6a.
    • Cartier dată la ONI 2012 clasa a 6a.
    • Opțională, dar în cadrul temei, Joc1 dată la ONI 2011 clasa a 7a. Atenţie, se rezolvă elegant cu tablou tridimensional (vectori de matrice).
  • Opțional, la arhivă, foarte grea: cartier2

Rezolvări aici: [2]