Clasa a VI-a lecția 3 - 6 oct 2015

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Debug rapid

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

Recapitulare - continuare

Numere palindrom

Cum aflăm dacă un număr este palindrom (simetric)? Discuție despre algoritmul clasic, prin răsturnarea numărului, care poate depăși întregul maxim. Discuție despre un alt algoritm care nu dă depășire, care compară prima cifră cu ultima, apoi le elimină si reia. 

#include <stdio.h>

int main() {
  int n, nc, p10;

  scanf( "%d", &n );
  nc = n;
  p10 = 1;
  // Calculam 10 la puterea nr. cifre - 1
  while ( nc > 9 ) {
    p10 = p10 * 10;
    nc = nc / 10;
  }

  // cita vreme mai avem macar doua cifre si prima cifra este egala cu ultima
  while ( p10 > 1 && (n / p10 == n % 10) ) {
    n = n % p10;     // Taiem prima si ultima cifra din numar
    n = n / 10;
    p10 = p10 / 100; //Actualizam puterea
  }

  if ( p10 <= 1 ) // daca am ajuns la o cifra sau nici una este palindrom
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

Secvență crescătoare prin rotație

Verificare secvență crescătoare prin rotație. O secvență este crescătoare prin rotație dacă fie este crescătoare (nedescrescătoare, include mai mic sau egal), fie poate fi făcută crescătoare prin rotații succesive (permutări circulare). Am discutat despre rezolvarea liniară, care nu necesită vectori. 

#include <stdio.h>

int main() {
  int n, i, a, b, primul, caderi;
  scanf( "%d%d", &n, &a );
  primul = a;

  caderi = 0; // de cite ori gasim un numar mai mic ca cel din-naintea lui
  i = 1;
  while ( i < n && caderi < 2 ) {
    scanf( "%d", &b );
    if ( a > b )
      ++caderi;
    a = b;
    ++i;
  }

  if ( caderi == 0 ) // daca e complet crescatoare, OK
    printf( "DA\n" );
  else if ( caderi > 1 ) // daca descreste de doua ori, nu este crescatoare
    printf( "NU\n" );
  else if ( primul >= b ) // daca creste o data depinde de capete
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

Elemente minime

Să calculăm nrmin, numărul de elemente minime într-un vector. Prima idee, probabil cea mai simplă, este să executăm doi pași. În prima trecere găsim minimul, în cea de-a doua numărăm de cîte ori apare. Iată această soluție: 

  min = v[0];
  for ( i = 1; i < n; i++ )
    if ( v[i] < min )
      min = v[i];
  nrmin = 0;
  for ( i = 0; i < n; i++ )
    if ( v[i] == min )
      nrmin++;

O idee care duce la o soluție mai bună este să facem o singură trecere. Atunci cînd găsim un element mai mic decît minimul, îl păstrăm cu un număr de apariții 1. Atunci cînd găsim un element egal cu minimul, pur și simplu incrementăm numărul de apariții. Iată programul: 

  min = v[0];
  nrmin = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] < min ) {
      min = v[i];
      nrmin = 1;
    } else if ( v[i] == min ) {
      nrmin++;
    }

De ce este această soluție mai bună? Deoarece:

  • face o singură trecere prin vector.
  • poate să rezolve problema fără să aibă nevoie de stocarea elementelor într-un vector.
  
  fscanf(fin,"%d",&min);
  nrmin = 1;
  
  for ( i = 1; i < n; i++ )
    fscanf(fin,"%d",&a);
    if ( a < min ) {
      min = a;
      nrmin = 1;
    } else if ( a == min ) {
      nrmin++;
    }

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.

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

Atenție: stînga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. 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ă. 

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

Temă

Tema 3 clasa a 6a

  • Bitonă: verificare secvență bitonă prin rotație. O secvență este bitonă dacă mai întîi crește și apoi, eventual, descrește. O secvență bitonă prin rotație este o secvență care fie este bitonă, fie poate fi făcută bitonă prin rotații succesive. Încercați să o rezolvați fără a folosi vectori, similar cu problema secvenței crescătoare prin rotație.
  • Majoritar: dat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin n/2 + 1 ori. Încercați să dați o soluție mai bună decît sortarea.

Opțional (grea): Selecție: dat un șir de n numere și o poziție k în acel șir să se spună ce element s-ar afla pe acea poziție dacă șirul ar fi sortat.

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_VI-a_lecția_3_-_6_oct_2015&oldid=12634"