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

From Algopedia
Jump to: navigation, 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

Problema tir 1

Problema tir 1 a fost dată la olimpiada pe școală 2014 clasa a 6a, la liceul Tudor Vianu. Ea este una de eficiență a calculului și de atenție la cazurile particulare.

Întrebare: care este timpul în care glontele ajunge la Înălțimea farfuriei? Deoarece el avansează cu G metri pe secundă, rezultă că îi va lua H/G secunde. Atenție, acest număr nu este neapărat întreg.

Similar, timpul necesar farfuriei să ajungă la distanța orizontală a glontelui este D/F. Pentru ca glontele și farfuria să se întîlnească trebuie ca ele să ajungă la întîlnire în același timp. Putem, deci, să testăm dacă cele două fracții sînt egale:

H/G = D/F

Pînă aici este simplu. Ar putea să pară că tot ce avem de făcut este să calculăm produsele H×F și D×G și să le comparăm. Desigur că nu este așa, deoarece:

  • Avem cazuri particulare
  • Produsul depășește long long

Tratarea cazurilor particulare

Atunci cînd oricare din viteze este zero fracția originală nu poate fi calculată (împărțire la zero). Vom avea deci trei cazuri particulare, cînd una din viteze este zero, sau cealaltă, sau ambele. Nu le vom detalia aici, de exemplu dacă ambele viteze sînt zero este clar că glontele și farfuria trebuie să se afle chiar în origine (distanță zero) pentru a se întîlni. Dimpotrivă, dacă una din viteze este zero și cealaltă nu trebuie ca distanța corespunzătoare vitezei non-zero să fie zero.

Tratarea depășirii long long

Cum procedăm în cazul cînd ambele viteze sînt diferite de zero, deci putem compara fracțiile? Nu putem face împărțirea. Nu putem calcula nici produsele. Am putea încerca diverse idei:

  • Facem produsele și sperăm să luăm cît mai multe teste.
  • Descompunere în factori primi a numerelor și comparare factor cu factor. Funcționează fără depășire de întreg. Ce complexitate are? Descompunerea în factori primi știm că este {\sqrt  {n}}. În cazul nostru N poate fi aproximativ 1018, deci radicalul său va fi aproximativ 109, adică un miliard. Vom depăși timpul.
  • Efectuarea înmulțirii cu numere mari, memorate într-un vector de cifre ale numerelor. O soluție de nivel mai înalt decît ceea ce am predat pînă acum. Va funcționa, dar va fi laborioasă.

Din fericire, ca în multe alte cazuri, matematica ne salvează. Cum putem compara două fracții, D/F și H/G? Avem două variante posibile în care două fracții sînt egale:

  1. Fie sînt ireductibile (nesimplificabile) și D = H și F = G
  2. Fie una sau ambele fracții sînt reductibile, caz în care, după simplificare, vom ajunge la situația anterioară

Putem deci să simplificăm fracțiile și apoi să comparăm numărătorii și numitorii. Pentru simplificare vom calcula cel mai mare divizor comun dintre numărător și numitor folosind algoritmul lui Euclid.

Iată o soluție bazată pe aceste idei.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  long long dg, vg, hf, vf, cmmdc, a, r;

  fin = fopen( "tir1.in", "r" );
  fscanf( fin, "%lld%lld%lld%lld", &dg, &vg, &hf, &vf );
  fclose( fin );

  fout = fopen( "tir1.out", "w" );
  if ( vg == 0 )
    if ( vf == 0 ) // ambele viteze zero, trebuie ca dg = hf = 0
      if ( dg == 0 && hf == 0 )
        fprintf( fout, "da\n" );
      else
        fprintf( fout, "nu\n" );
    else // vg = 0, vf > 0, trebuie ca hf = 0
      if ( hf == 0 )
        fprintf( fout, "da\n" );
      else
        fprintf( fout, "nu\n" );
  else
    if ( vf == 0 ) // vg > 0, vf = 0, trebuie ca dg = 0
      if ( dg == 0 )
        fprintf( fout, "da\n" );
      else
        fprintf( fout, "nu\n" );
    else { // ambele viteze sint diferite de zero, comparam fractii
      // hf/vg = timpul in care glontele ajunge la intilnire
      // calculam cmmdc intre hf si vg si apoi simplificam fractia
      cmmdc = hf;
      a = vg;
      while ( a > 0 ) {
        r = cmmdc % a;
        cmmdc = a;
        a = r;
      }
      hf /= cmmdc;
      vg /= cmmdc;
      // dg/vf = timpul in care farfuria ajunge la intilnire
      // calculam cmmdc intre dg si vf si apoi simplificam fractia
      cmmdc = dg;
      a = vf;
      while ( a > 0 ) {
        r = cmmdc % a;
        cmmdc = a;
        a = r;
      }
      dg /= cmmdc;
      vf /= cmmdc;
      // farfuria si glontele se intilnesc numai daca dg = hf si vf = vg
      if ( dg == hf && vf == vg )
        fprintf( fout, "da\n" );
      else
        fprintf( fout, "nu\n" );
    }
  fclose( fout );

  return 0;
}

Observăm că soluția nu produce depășiri de întregi. Ce complexitate are această soluție? Este clar că va fi totuna cu complexitatea calculului cmmdc, adică O(log max(H+G, D+F)). Observăm, de asemenea, că matematica este importantă.

Problema suma

Problema suma a fost dată la .campion 2006. Este o problema uşoară dacă o rezolvăm cu vectori. Ea devine mai interesantă fără vectori.

Pentru a rezolva problema să observăm asemănarea din calculul cifrelor celor două numere cerute. Pentru un număr citit n:

  • Numărul minim va fi 10...0r99...9, unde suma r + 9 + 9 + ... + 9 = n - 1
  • Numărul maxim va fi 99...9r00...0, unde suma r + 9 + 9 + ... + 9 = n

Să observăm că în ambele cazuri r este strict mai mic ca 9, dar poate fi și zero.

Va rezulta, desigur, un calcul similar. Să începem cu numărul maxim. Putem calcula numărul de cifre 9 de la început ca fiind
 n / 9;

În acest caz r va fi restul împărțirii lui n la 9. Iar numărul de cifre 0 va fi diferența n - n / 9 - 1 (1 pentru cifra r).

Numărul minim se calculează similar, cu observația că avem un caz particular cînd n este 1, deoarece n - 1 va fi zero.

Iată o soluţie bazată pe aceste idei simple:

#include <stdio.h>

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

  fin = fopen( "suma.in", "r" );
  fout = fopen( "suma.out", "w" );
  fscanf( fin, "%d", &n );

  // afisam numarul minim
  fprintf( fout, "1" );              // prima cifra va fi 1
  for ( i = 0; i < (n - (1 + (n-1) / 9 + 1)); i++ ) // scadem nr de cifre 9, prima cifra 1 si cifra rest si aflam numarul zerouri
    fprintf( fout, "0" );
  if( n - 1 > 0 )
    fprintf( fout, "%d", (n-1) % 9 );  // afisam cifra mai mica ca noua (poate fi si 0); atentie la cazul particular n=1
  for ( i = 0; i < (n-1) / 9; i++ )         // afisam cifrele de 9
    fprintf( fout, "9" );
  fprintf( fout, "\n" );

  // afisam numarul maxim
  for ( i = 0; i < n / 9; i++ )         // afisam cifrele 9
    fprintf( fout, "9" );
  fprintf( fout, "%d", n % 9 );      // afisam cifra mai mica ca noua (poate fi si 0)
  for ( i = 0; i < (n -(1 + n / 9)); i++ ) // restul cifrelor pana la n sunt zerouri
    fprintf( fout, "0" );
  fprintf( fout, "\n" );
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Ea este proporțională cu numărul de cifre afișate, deci O(N).

Rezolvări aici [1]

Lecție

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]