Clasa a VI-a lecția 2 - 29 sep 2015

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Discuție despre temă, cu analiza complexității timpului:

Rezolvări aici [1]

Lecție

Constante in C

Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc. Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:

#define D 1
...
if ( D )
  printf( "x=%d   y=%d   a=%d\n", x, y, a )
...

La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:

#define D 0

Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.

Instrucțiunea switch

Precum ştim instrucţiunea if implementează structura alternativă. Uneori avem nevoie de decizii multiple, de exemplu cînd vrem să ştim dacă o variabilă are valoarea 1, 2 sau 3. În aceste cazuri putem folosi o combinaţie de instrucţiuni if:

if ( n == 1 ) {
  cod pentru cazul 1;
} else if ( n == 2 ) {
  cod pentru cazul 2;
} else if ( n == 3 ) {
  cod pentru cazul 3;
}

Deoarece situaţiile cînd vrem să executăm diverse acţiuni în funcţie de valoarea unei variabile limbajul C se oferă instrucţiunea switch a cărei formă este:

switch ( n ) {
case constantă1:
  cod de executat dacă n este egal cu constantă1;
  break;
case constantă2:
  cod de executat dacă n este egal cu constantă2;
  break;
  .
  .
  . 
default:
   cod de executat dacă n nu este egal cu nici una din constante;
}

Exemplu: se citesc pe aceeaşi linie, în ordine, un caracter şi apoi două numere întregi, toate separate printr-un spaţiu. Dacă caracterul este una din operaţiile +, -, * sau / să se afişeze rezultatul acelei operaţii pe cele două numere. În caz contrar să se afişeze cuvîntul eroare.

Rezolvare:

#include <stdio.h>

int main() {
  int a, b;
  char ch;

  ch = fgetc( stdin );
  scanf( "%d%d", &a, &b );
  switch ( ch ) {
  case '+':
    printf( "%d\n", a + b );
    break;
  case '-':
    printf( "%d\n", a - b );
    break;
  case '*':
    printf( "%d\n", a * b );
    break;
  case '/':
    printf( "%d\n", a / b );
    break;
  default:
    printf( "eroare\n" );
  }
  return 0;
}

De menţionat că nu este obligatoriu să avem o variabilă testată în switch, putem avea o expresie, cu condiţia ca ea să aibă o valoare întreagă, nu reală. 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;
}

Ciurul lui Eratostene

Acest algoritm se studiază la matematică. El procedează astfel:

  1. Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n].
  2. Caută primul număr netăiat din listă (inițial nici un număr nu e tăiat). Fie p acel număr.
  3. Mergi din p în p prin listă, începînd cu 2*p și taie toate numerele întîlnite (unele vor fi deja tăiate)
  4. Reia de la pasul 2, pînă ce depășim n.

În final numerele rămase netăiate sînt prime.

Cum implementăm acest algoritm, care la origine se executa manual, cu hîrtie și creion? Pentru a simula tăierea numerelor vom folosi un vector de frecvență, ciur, care pentru fiecare număr între 2 și n ne va spune dacă este tăiat sau nu. Inițial vectorul ciur va fi inițializat cu zero, care semnifică că toate numerele sînt prime, iar pe măsură ce tăiem numere, ele vor fi marcate cu unu. În final ciur[x] va fi zero dacă numărul este prim, sau unu în caz contrar. Deoarece elementele lui ciur sînt zero sau unu nu are rost să folosim întregi pentru ele, ci vom folosi caractere, văzute ca numere mici. Să ne reamintim că un caracter ocupă un octet (opt biți), pe cînd un întreg ocupă 4 octeți (32 de biți). Astfel, memoria folosită va fi de patru ori mai mică. (Vom vedea, în viitor, că memoria se poate reduce în continuare dacă ținem doar un bit pe element.)

Iată implementarea acestei idei. Programul următor calculează vectorul ciur pentru numerele pînă la n, cu n maxim două milioane:

char ciur[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 2; 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;

Programul e poate optimiza dacă facem următoarele observații:

  1. În a doua buclă for variabila i ia valorile 2∙d, 3∙d, 4∙d, ..., k∙d. Pentru k < d toate valorile de forma k∙d au fost deja tăiate de valorile k anterioare, drept pentru care nu are rost să le mai parcurgem. Putem să pornim cu i de la d∙d.
  2. Conform observației anterioare i pornește de la d∙d. De aceea nu are rost să mergem cu d mai departe de sqrt(n), deoarece nu vom mai găsi i astfel încît i ≤ n.

Iată implementarea optimizată, bazată pe aceste două observații:

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

Temă

Tema 2 clasa a 6a

Rezolvări aici [2]