Clasa a VI-a lecția 4 - 11 oct 2018

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

Comentarii temă

Comentarii problema tir1

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Chivu, Grecu, Ilie, Voicu.
  • Repetarea de cod nu este bună. Ea nu se referă doar la instrucțiuni copiate cu copy/paste. Se referă și la teste repetate. Mulți dintre voi ați folosit condiții compuse, repetînd multe din condițiile simple. Aceasta duce nu doar la o ineficiență a programului, ci și la o dezordine algoritmică. Nu veți fi siguri că ați acoperit toate cazurile. Iată un exemplu:
  ok=0;
  if(h==0 && d==0)
    ok=0;
  else if(h==0 && f>0 && g==0)
    ok=0;
  else if(d==0 && f==0 && g>0)
    ok=0;
  else if(h==0 || f==0 || d==0 || g==0)
    ok=1;

Cum puteam scrie mai elegant? Testînd o singură variabilă la un moment dat, luînd în calcul cele două variante, dacă este zero sau diferită de zero, cum veți vedea în soluția de mai jos. Observați și o inutilitate a codului, deoarece ok este zero la început, iar trei dintre ramurile if-urilor o setează din nou la zero, inutil.

  • Unii dintre voi s-au prins că pot compara produsele d*g și h*f dar nu s-au prins că vor da depășire la înmulțire.
  • La fel, unii nu s-au prins că comparația produselor nu acoperă unele cazuri speciale cînd vitezele sînt zero.
  • Unii din voi au făcut împărțiri pe double. Pe lîngă că nu am predat așa ceva, deci nu v-aș fi cerut, ele nu funcționează, deoarece nu fac împărțiri exacte. Soluțiile au luat puncte deoarece testele nu acoperă acest caz, dar soluția aceasta este greșită.
  • Unii din voi trimiteți surse la arhivă în timpul temei, la rînd, deci nu este o greșeală ci este intenționat. Consider acest lucru un mod de a trișat și îl tratez cu toată seriozitatea. Este motiv de plecat de la IQ Academy, deci mare atenție unde trimiteți sursele de acum înainte.
  • Unii din voi nu v-ați prins că trebuia să folosiți algoritmul lui Euclid pentru cmmdc, deși în lecția trecută am vorbit atît de mult despre el, iar cealaltă problemă nu îl folosea. Asta arată un pic de naivitate din partea celor ce nu s-au prins.
  • Unii din voi nu s-au prins că împărțind numerele de la intrare între ele pot obține împărțiri la zero.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Dumitrescu, Simon
  • Avertismente pentru pescarii programatori prin aproximări succesive și testare la varena: Benescu, Petcu, Rughiniș, cu Petcu cîștigînd locul întîi pentru că a încercat trei idei diferite.

Comentarii individuale

Grupa de dimineață

  • Aizic: ai declarat variabilele de intrare ca int, deși enunțul spune clar că sînt long long. Altfel ideea e interesantă, de a te folosi de rezolvarea problemei fracție. Este însă greu de implementat și nu merge cu vectori de trei elemente.
  • Badea: ai trimis surse cînd la temă, cînd la arhivă. Nu mai trimite la arhivă. Matematica este buna. Nu tratezi corect cazurile particulare. Folosești împărțire pe double, care are erori deoarece nu păstrează toate zecimalele. Soluție foarte incorectă, dar care ia punctaj bun deoarece testele nu sînt suficient de bune.
  • Benescu: ai trimis multe surse, și la arhivă. Nu mai trimite surse la arhivă în timpul temei, ne supărăm! Soluția ta este extrem de simplistă. Ai dus bine la cap matematica, dar apoi faci împărțiri pe întregi, care îți este foarte clar că au erori. Tu poți mai mult de atît. Ai încercat tot soiul de variante care știai că nu merg, doar pentru a testa efectul la varena. Nu asta facem noi aici, ci construim soluții, nu încercăm să vedem cu care din ele luăm mai mult la evaluatorul automat. Foarte urît.
  • Burac: ideea pare bună, de a compara fracții folosind cmmdc. Dar codul este foarte dezlînat și necitibil. Folosești ca variabile primele litere ale alfabetului, total necitibil. Apoi faci tot felul de transferuri și atribuiri de la o variabilă la alta, foarte greu de urmărit. Te antrenezi pentru concursul 'most obfuscated program'? Dacă nu, încearcă să îți "piepțeni" programele. Un cod dezordonat arată o gîndire dezordonată.
  • Calotă: ai o idee, e ceva cu cmmdc. Dar de ce calculezi în aceeași buclă cmmdc a patru numere? Nu are sens. Ai declarat variabilele tip unsigned long long (nu era necesar, long logn era OK), dar la citire le citesti cu %lld in loc de %llu.
  • Cemârtan: te-ai prins de matematică, dar nu ai făcut nimic la partea de informatică. Ai depășire la înmulțire. Program simplist, nu tratezi cazurile particulare.
  • Chivu: o soluție foarte bună, bravo! Matematica corectă și implementare bună. Cazurile particulare tratate ordonat. Singurul lucru care se poate îmbunătăți este numărul mare de teste de la început. De exemplu, dat fiind că setezi nimerit=0 la început ai putea să nu mai tratezi decît cazurile în care nimerit devine 1.
  • Cojocariu: matematica este foarte bună, implementarea calcului este iar foarte bună, te-ai prins cum să compari fracții. Dar nu tratezi nici un caz particular drept care faci împărțiri la zero.
  • Cojocaru: te-ai prins de matematică, dar nu ai făcut nimic la partea de informatică. Ai depășire la înmulțire. Program simplist.
  • Coman: e preferabil să trimiți rezolvarea problemei suma chiar la problema suma, nu la tir1 :) M-am uitat pe penultima submisie. Codul arată o idee promițătoare, cea de calcul cmmdc. Dar if-urile sînt dezordonate și din această cauză nu pare că acoperi toate cazurile. Păcat că ideea este bună, căci în final compari produse ce duc la depășire de long long. Trebuia să compari direct numărătorii și numitorii.
  • Dragomir: ideea este bună. Matematica este bună. Testele puțin dezordonate, e neclar dacă acoperi toate cazurile particulare. Ai depășire de long long la înmulțire.
  • Dumitrescu: nimic? Serios?
  • Grecu: ideea este bună, codul este un pic dezordonat. Îmi este greu să urmăresc hățișul de if-uri. Ar fi fost bine să pui niște comentarii în cod. Oricum, felicitări, ideea este de 100p!
  • Hossu: ideea este bună, matematica este bună. Însă nu te-ai gîndit la două lucruri: ai cazuri particulare cînd "fluturele" nu funcționează. Și doi, înmulțirea la comparația de produse produce depășire pe long long! O soluție prea simplistă pentru nivelul tău, tu poți mai mult.
  • Iordache: matematica este bună, informatica slabă. Nu ai tratat cazurile particulare, cînd vei împărți la zero. Ai folosit tipul double care are erori la împărțire deoarece nu are cum să stocheze toate zecimalele.
  • Mocanu: Este ok și chiar foarte indicat să citești mai multe variabile într-un singur fscanf, decît să faci mai multe fscanf-uri. La citirile în bucle mari poți depăși limita de timp. Mi-e greu să urmăresc programul, cîteva comentarii cheie m-ar fi ajutat. Cumva pare că merge, deci nu este greșit. Dar trebuie să îl ordonezi puțin. Încearcă să gîndești problema înainte să te apuci de codare. Du matematica pînă la capăt!
  • Mușat: 5 surse trimise, din care trei la arhivă. Ideea descrisă în comentariu este bună, dar programul greu de urmărit deoarece denumirile variabilelor nu au legătură cu enunțul. Pare bine, felicitări! Nu mai trimite soluții la arhivă, te rog!
  • Nicola: matematica bună, ideea bună. Două probleme, una de algoritm, nu tratezi cazurile particulare cînd vitezele sînt zero, iar a doua de implementare, ai depășire la produsele calculate. Bănuiesc că sții deja aceste lucruri și că nu ți-a venit nici o idee cum să le rezolvi.
  • Petcu: nici măcar nu pot să comentez prea mult la soluția ta. Ai cinci surse trimise în care încerci trei idei diferite. Ana, asta este definiția pescuitului. Dacă vrei să încerci să vezi care din sursele tale este cîștigătoare, încearcă la loto. Ca informaticieni nu putem face așa ceva. Asta înseamnă că nu ai siguranța algoritmilor creați de tine, sau, mai rău, știi că nu funcționează dar încerci să iei cît mai multe puncte. Avertisment. Dacă continui așa ne supărăm. Fă-ți te rog teste, cum fac tot ceilalți, nu folosi varena drept sclavul tău de testare.
  • Rebengiuc: Prefect! Bravo!
  • Rughiniș: șapte surse este absolut excesiv. Prea multe aproximări. Folosește creierul, nu tastele! Nu pare că acoperi corect cazurile particulare, ai inclusiv comentarii care contrazic codul, de genul if(g==0)//si viteza glontelui nu e zero. Dar ai probleme grave, cum ar fi că declari variabilele de intrare ca int deși enunțul spune că depășesc int. Apoi compari rezultatul unor împărțiri pe întregi, inexacte, și încerci să compensezi uitîndu-te la resturi, ceea ce nu funcționează, precum ai văzut. Partea bună este că te-ai prins de matematică.
  • Stoian: ideea este foarte bună, bravo! Matematica este corectă. Nu acoperi, însă, toate cazurile particulare. Și comparația produselor poate da depășire de long long. Trebuia să compari direct numitorii și numărătorii. O sursă bună, bravo.
  • Ștefănescu: idee bună, felicitări! Ultimele două cmmdc-uri sînt inutile. Nu ai luat 100p deoarece poți să împarți la zero. Matematica, ai grijă!
  • Togan: idee bună, implementare bună, bravo! Ai folosit multe variabile nenecesare care fac greu de urmărit codul. Ai un test în plus pentru partea întreagă a fracțiilor, nu este necesar, poți compara și fracții supraunitare. Codul este cam dezordonat, dar se vede că progresezi. Continuă să gîndești algoritmul cît mai în detaliu înainte să te apuci de program.
  • Voicu: o soluție foarte frumoasă, bravo! Te-ai prins de matematică, ai implementat corect comparația fracțiilor și ai tratat cu succes toate cazurile particulare. Ceea ce mai poți îmbunătăți este numărul de if-uri. Cam repeți condiții pe acolo.

Grupa de după-amiază

  • Asgari: ideea bună, matematica bună, implementare rezonabilă, bravo! Nu te-ai prins că nu era necesar să compari produse. Chiar și simplificate ele pot da depășire, dacă, de exemplu, fracțiile sînt raport de numere mari dar prime între ele.
  • Cadîr: simpatică ideea de a folosi tipul double. Ți-e clar că nu aș fi cerut așa ceva, deoarece nu l-am predat. Nu funcționează deoarece double are erori la împărțire.
  • Dobre: nu mi-e clar de ce ai trimis atîtea surse la arhivă. Bun, la temă ai două submisii. Prima e clară, funcționează pe teste mici, la teste mari depășești înmulțirea pe long long. Ultima sursă nu o înțeleg pentru că e lungă și complexă. Pune te rog comentarii asupra metodei folosite măcar, în situații din acestea.
  • Fares: matematica bună și cazurile particulare tratate ordonat și corect. Partea de calcul este greșită, deoarece împărțirea va fi cu erori, pentru că folosești tipul double. Cu toate acestea ai luat punctele. varena te place :)
  • Ilie: foarte bine, bravo! Ai tratat toate cazurile cu atenție, nu ți-a scăpat nimic, iar matematica este foarte bună. Vezi o mică simplificare în soluția de mai jos.
  • Ipate: matematica bună. Informatica slabă. Ai atît cazuri particulare pe care formula nu este valabilă nici matematic, cît și depășire la înmulțirile de long long. Nici măcar nu ai încercat să mergi mai departe, te-ai mulțumit cu 50p. O sursă simplistă, fără efort. Tu poți mai mult.
  • Marcu: tu faci calcule care știi de la bun început că dau depășire, apoi încerci să compensezi pentru asta. Nu face asta niciodată. Este o aproximare demnă de cei care dau cu for-ul, nu de un informatician. În lipsă de idei se acceptă, dar ține minte că e greșit :)
  • Nicu: matematica este bună, dar nu acoperi corect cazurile particulare. Împărțirea pe double nu funcționează, are erori deoarece nu poate păstra toate zecimalele. Nu pare că ai încercat serios să rezolvi problema, tu poți mai mult de atît.
  • Simon: nimic? Serios?
  • Stancu: bravo, ai rezolvat matematica bine și ți-ai dat seama că există cazuri particulare, dar ai depășire de long long la înmulțire. Ideea de a compara produsele nu funcționează informatic. Nu cred că ai acoperit bine cazurile particulare, trebuie să ai o ordine.
  • Tatomir: ideea este bună. Codul foarte încîlcit. Arată a cod peticit. Modificat pe măsură ce ți se schimbau ideile. Nu așa. Odată ce ți-ai format un algoritm în cap rescrie codul pentru a urmări, ordonat, acel algoritm. Tu faci patru calcule de cmmdc, necesare sînt doar două.
  • Teodorescu: te-ai prins de matematică și de faptul că ai cazuri particulare. Atenție, la cazurile particulare, al treilea if if (f==0 || g==0) acoperă și al doilea if if (f==0 && g==0). Al doilea if este, deci, inutil. Matematica este bună, însă nu pare că acoperi toate cazurile particulare în mod corect.

Tema - rezolvări

Rezolvări aici [1]

Lecție

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

Debug rapid

Să ne remaintim cum putem să facem debugarea programelor noastre mai rapidă și mai ușoara: printf-uri cu if ( D ):

#define D 1
...
if ( D ) {
  ... secvență de tipărire de debug ...
}

Iar la final redefiniți D ca fiind 0 pentru a elimina printf-urile de debug. În felul acesta puteți să activați sau să dezactivați mesajele de debug foarte rapid.

Sortare

Despre sortare (ordonare). Am predat anul trecut sortarea prin selecție. Nu am reluat-o, ci doar am vorbit despre complexitate: ea are complexitate este O(n2). Pentru cei care îl știți, nu folosiți algoritmul de sortare bubble sort. Este tot un algoritm O(n2), dar cu o constantă mult mai rea. În practică este de circa zece ori mai lent decît select sort.

// avem vectorul v de n elemente
for ( u = n – 1; u > 0; u-- ) { // pozitia ultimului element din subvector
  max = v[0];
  p = 0;                        // p este poziția maximului
  for ( i = 1; i <= u; i++ )
    if ( v[i] > max ) {         // memoram noul maxim si pozitia lui
      max = v[i];
      p = i;
    }
  // interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia u
  v[p] = v[u];
  v[u] = max;
}

Există un algoritm Quicksort care este O(n log n) pe cazul mediu. Sortarea optimală este O(n log n), deci nu se poate mai bine. Nu îl vom învăța anul acesta. Atenție! Nu folosiți funcția de bibliotecă! Sînteți la vîrsta cînd învățați să scrieți sortări, nu cînd le folosiți.

Ciurul lui Eratostene

Vă rog să recitiți explicațiile detaliate ale algoritmului în lecția de anul trecut. Reamintim aici doar algoritmul:

char ciur[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 2; d * d <= n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Nu uitați:

  • Vectorul ciur[] este de tip caracter și nu întreg!
  • În final vectorul ciur[i] este 0 dacă numărul este prim sau 1 în caz contrar.

Complexitate? Matematica este complexă, dar rețineți că metoda este aproximativ O(n) pentru valorile lui n cu care vom lucra noi. Pentru cei interesați, complexitatea este de fapt O(n∙log log n).

Variante și aplicații

Ciurul lui Eratostene poate fi folosit pentru a calcula și alte valori decît primalitatea:

  • Numărul de divizori primi ai tuturor numerelor pînă la n
  • Suma divizorilor primi ai tuturor numerelor pînă la n
  • Numărul de divizori ai tuturor numerelor pînă la n
  • Suma divizorilor tuturor numerelor pînă la n
  • Numărul de numere prime cu fiecare din numerele pînă la n

Toate aceste variante au o complexitate ușor mai mare și anume O(n log n)

Pentru a calcula aceste ciururi speciale vom aplica unele variații implementării clasice:

  • Vom folosi sau nu testul if ( ciur[d] == 0 ) - de exemplu nu vom folosi acest test cînd calculăm numărul de divizori, deoarece vrem să luăm în calcul toți divizorii, nu doar pe cei primi.
  • Vom porni în for de la diverse valori: d, d+d, d*d
  • Vom modifica valorile vectorului în diverse feluri: +1, +ciur[d], etc.

Căutare binară

Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.

Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Aceasta înseamnă o complexitate de O(n). Putem să rezolvăm această problemă mai rapid?

Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.

Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:

stinga = 0;
dreapta = n;
while ( dreapta - stinga > 1 ) {
  mijloc = (stinga + dreapta) / 2;
  if ( v[mijloc] > e )
    dreapta = mijloc;
  else
    stinga = mijloc;
}
if ( e == v[stinga] ) {
  // ... găsit, procesare aici ...
}

Observație importantă: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat.

Ce complexitate are căutarea binară? Să observăm că la fiecare iterație a buclei while diferența dintre dreapta și stinga se reduce la jumate. Ne vom opri atunci cînd ea devine 1. Bucla se va executa, deci, de cîte ori putem împărți diferența la doi, deci O(log n) unde n este numărul de elemente pe care se face căutarea.

Varianta de program de mai sus găsește ultima apariție a lui e. Ea poate fi adaptată să găsească prima apariție, gîndiți-vă cum. De asemenea, căutarea binară poate fi adaptată să găsească poziția la care s-ar putea insera un element e în vector.

Atenție! Căutarea binară este faimoasă pentru ușurința cu care o puteți greși. Pentru a vă asigura că nu veți avea greșeli la implementare respectați următoarele reguli:

  1. Intervalul de căutare să fie închis la un capăt și deschis la celălalt, iar testul de oprire să fie ca diferența dintre capete să fie strict mai mare ca unu. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
  2. Comparația cu elementul să fie totdeauna de tip strict (mai mic sau mai mare, nu mai mic sau egal).
  3. Cînd comparația este adevărată se va muta în mijloc capătul deschis al intervalului.

Temă

Tema 4 clasa a 6a

  • prâslea - dată la oni 2014 clasa a șasea - rezolvată cu sortare prin selecție
  • divprimi - dată la olimpiada pe școală 2017, clasa a 10a
  • cautbin - problemă exercițiu de căutare binară


Rezolvări aici [2]