Clasa a VI-a lecția 3 - 30 sep 2013

Tema - rezolvări

Am discutat despre soluțiile la cele două probleme, Numărare și Fracție.

Soluții aici [1]

Lecție

Recapitularea materiei (continuare)

Recapitulare probleme de bază:

Algoritmul lui Euclid

Algoritmul lui Euclid pentru cmmdc. Complexitate: O(log max(a, b)). Atenție! Circulă printre voi un algoritm pe bază de scăderi repetate. Este un algoritm ineficient care are complexitate O(max(a, b)). Nu-l folosiți.

#include <stdio.h>

int main() {
  int a, b, r;

  scanf( "%d%d", &a, &b );
  while ( b > 0 ) {
    r = a % b;
    a = b;
    b = r;
  }
  printf( "%d\n", a );

  return 0;
}

Calcul divizori

Calculul divizorilor unui număr. Putem avea nevoie doar să îi număram, sau chiar să îi calculăm pentru un calcul ulterior sau pentru afișare. Similar cu descompunerea în factori primi.

Varianta 1 - numărare

#include <stdio.h>

int main() {
  int n, p, div, nrdiv;

  scanf( "%d", &n );
  nrdiv = 1;
  div = 2;
  while ( div * div <= n ) {
    p = 0;
    while ( n % div == 0 ) {
      ++p;
      n = n / div;
    }
    nrdiv = nrdiv * (p + 1);
    ++div;
  }
  if ( n > 1 )
  nrdiv = nrdiv * 2;
  printf( "%d\n", nrdiv );

  return 0;
}

Varianta 2 - calcul

Această soluție poate fi folosită pentru afișarea sau lucrul cu divizorii numărului.

#include <stdio.h>

int main() {
  int n, div, nrdiv;

  scanf( "%d", &n );
  nrdiv = 2;
  div = 2, 

  while ( div * div < n ) {
    if ( n % div == 0 )
      nrdiv = nrdiv + 2;
    ++div;
  }
  if ( div * div == n )
    ++nrdiv;

  printf( "%d\n", nrdiv );

  return 0;
}

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

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(n²). Pentru cei care îl știți, nu folosiți algoritmul de sortare bubble sort. Este tot un algoritm O(n²), 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.

Temă

• 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: 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]