Clasa a VI-a lecția 3 - 9 oct 2014

Tema - rezolvări

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

Rezolvări aici [1]

Lecție

Recapitularea materiei (continuare)

Am parcurs ceea ce ne-a rămas din lecţia trecută. Apoi am vorbit despre următoarele probleme, cu discuţii despre complexitatea ca timp şi ca memorie.

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 - calcul

#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 - numărare

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

Temă

Tema 3 clasa a 6^a

• Bancomat dată la OMI Iasi 2012
• Suma dată la .campion 2006

Rezolvări aici [2]