View source for Clasa VII/VIII lecția 24 - 10 mar 2015

= Lecţie =
== Numere mari ==
Unele probleme necesită lucrul cu numere mai mari decît ne permite tipul long long (cu aproximație 18 cifre zecimale, mai exact 2<sup>64</sup>). Ce facem în acest caz? Stocăm aceste numere în vectori, cîte o cifră în fiecare element al vectorului. În continuare voi prezenta cîteva probleme clasice cu astfel de numere.

=== Reprezentare ===
Numerele mari se reprezintă într-un vector, ultima lor cifra pe prima poziție a vectorului, penultima pe a doua poziție, și așa mai departe, precum se vede în figură.

[[Image:nr-mare-1.gif|frame|none|Reprezentarea în vector a unui număr mare]]

Observați că am reprezentat vectorul invers, de la dreapta la stînga, pentru ușurința citirii numărului.

Observăm că vectorul v are ca elemente cifre, adică întregi cuprinși între 0 și 9. Pentru a folosi cît mai puțină memorie vom folosi cel mai mic întreg existent în limbajul C și anume tipul caracter. Să nu uităm că tipul caracter poate fi văzut atît ca și caracter cît și ca un întreg pe opt biți, cuprins între -128 și 127. Această reprezentare se numește reprezentarea numerelor în ''zecimal despachetat'':

 <nowiki>char v[100];</nowiki>

Pentru cei curioși există și reprezentarea zecimal împachetat, în care reprezentăm două cifre zecimale pe caracter, respectiv o cifră pe primii 4 biți și o cifră pe ultimii patru biți. În această lecție nu vom vorbi despre această reprezentare.

De asemenea, pentru un număr mare trebuie să ținem minte și numărul său de cifre. În exemplul nostru acesta este 5. Ca ultimă mențiune, trebuie să avem grijă ca cifrele nefolosite din vector să fie zero. Acest lucru este foarte important atunci cînd numărul poate să crească, cum ar fi la adunare, sau înmulțire.

=== Adunarea unui număr mic la unul mare ===
Fie v un număr mare cu n cifre. Dorim să adunăm la el un număr "mic", a. Pentru aceasta vom proceda similar cu procedura de adunare "de mînă": vom aduna a la prima cifră a numărului, vom stoca pe prima poziție ultima cifră a acestui număr, apoi vom calcula transportul prin împărțire la zece. Acest transport se adună la a doua cifră, stocînd ultima cifră a rezultatului pe a doua poziție și calculînd noul transport prin împărțire la zece. Diferența față de adunarea "de mînă" este că transportul poate fi mai mare decît 9. Iată secvența de cod care adună numărul mare (n, v) cu numărul a:

<syntaxhighlight>  i = 0;
  while ( a > 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    i++;
  }
  if ( i > n )
    n = i;</syntaxhighlight>
=== Scăderea unui număr mic din unul mare ===
Scăderea unui număr mic din unul mare este similară cu adunarea. Transportul va fi negativ. Trebuie însă să fim atenți la un lucru: operația % (modulo) în C nu se comportă ca la matematică. La matematică restul împărțirii a două numere este pozitiv sau zero. În C restul împărțirii unui număr negativ la unul pozitiv este negativ sau zero. De aceea codul trebuie modificat față de adunare pentru a calcula restul pozitiv al împărțirii la zece. De asemenea trebuie să avem grijă să scădem numărul de cifre, dacă este cazul. Vom păstra în nn poziția ultimei cifre diferite de zero. Iată secvența de cod care scade numărul mic a din numărul mare (n, v):

<syntaxhighlight>  a = -a;
  nn = i = 0;
  while ( a < 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    if ( v[i] < 0 ) {
      v[i] += 10;
      a--;
      nn = i;
    }
    i++;
  }

  if ( i >= n )
    n = nn + 1;</syntaxhighlight>

Atenție: programul de mai sus presupune că numărul mic este mai mic sau egal cu numărul mare.

=== Adunarea a două numere mari ===
Adunarea a două numere mari este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport și vom aduna cifră cu cifră cele două numere mari. În final vom testa dacă mai avem transport. Dacă avem el este maxim o cifră (demonstrați). Iată secvența de cod care adună numărul mare (n2, v2) la (n1, v1) depunînd rezultatul tot în (n1, v1):

<syntaxhighlight>  n1 = n1 < n2 ? n2 : n1;
  t = 0;
  for ( i = 0; i < n1; i++ ) {
    t = t + v1[i] + v2[i];
    v1[i] = t % 10;
    t /= 10;
  }
  if ( t > 0 ) {
    v1[i] = t;
    n1++;
  }</syntaxhighlight>
=== Scăderea a două numere mari ===
Scăderea a două numere mari este similară cu scăderea unui număr mare din unul mic. Vom folosi un transport negativ și vom scădea cifră cu cifră cele două numere mari. După ce se termină cifrele numărului de scăzut vom continua scăderea pînă ce transportul devine zero. Ca și la scăderea unui număr mic va trebui să avem grijă să scădem numărul de cifre dacă este cazul. Iată secvența de cod care scade numărul mare (n2, v2) din numărul mare (n1, v1):

<syntaxhighlight>  nn = t = i = 0;
  while ( i < n2 || t < 0 ) {
    t = t + v1[i] - v2[i];
    v1[i] = t % 10;
    t /= 10;
    if ( v1[i] < 0 ) {
      v1[i] += 10;
      t--;
      nn = i;
    }
    i++;
  }

  if ( i >= n1 )
    return n1 = nn + 1;</syntaxhighlight>

Atenție: programul de mai sus presupune că numărul (n2, v2) este mai mic sau egal cu numărul (n1, v1).

=== Înmulțirea unui număr mare cu unul mic ===
Înmulțirea unui număr mare cu unul mic este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport la care adunăm cifra curentă înmulțită cu numărul mic. Ultima cifră a transportului se stochează în cifra curentă, iar transportul se împarte la zece, apoi trecem la cifra următoare. După ce se termină cifrele numărului mare vom continua procedura pînă ce transportul devine zero. Trebuie să avem grijă să actualizăm numărul de cifre dacă este cazul. Iată secvența de cod care înmulțește numărul mic a cu numărul mare (n, v):

<syntaxhighlight>  t = i = 0;
  while ( i < n || t > 0 ) {
    t = t + a * v[i];
    v[i] = t % 10;
    t /= 10;
    i++;
  }

  if ( i > n )
    n = i;</syntaxhighlight>

Cu aceasta am încheiat capitolul de numere mari. Vă las ca exercițiu împărțirea unui număr mare prin unul mic, precum și înmulțirea a două numere mari. Cei ce se simt curajoși pot să codeze împărțirea a două numere mari, dar aceasta este ceva mai grea. Iată, în final, un program care demonstrează folosirea acestor operații.

<syntaxhighlight>#include <stdio.h>

char v1[100] = { 7, 3, 5, 4, 2 };
char v2[100] = { 4, 6, 4, 5, 7 };

int adunaNn( int n, char *v, int a ) {
  int i;

  i = 0;
  while ( a > 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    i++;
  }

  if ( i < n )
    return n;
  return i;
}

int scadeNn( int n, char *v, int a ) {
  int i, nn;

  a = -a;
  nn = i = 0;
  while ( a < 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    if ( v[i] < 0 ) {
      v[i] += 10;
      a--;
      nn = i;
    }
    i++;
  }

  if ( i < n )
    return n;
  return nn + 1;
}

int adunaNN( int n1, char *v1, int n2, char *v2 ) {
  int i, max, t;

  max = n1 < n2 ? n2 : n1;
  t = 0;
  for ( i = 0; i < max; i++ ) {
    t = t + v1[i] + v2[i];
    v1[i] = t % 10;
    t /= 10;
  }
  if ( t > 0 ) {
    v1[i] = t;
    return i + 1;
  }

  return max;
}

int scadeNN( int n1, char *v1, int n2, char *v2 ) {
  int i, t, nn;

  nn = t = i = 0;
  while ( i < n2 || t < 0 ) {
    t = t + v1[i] - v2[i];
    v1[i] = t % 10;
    t /= 10;
    if ( v1[i] < 0 ) {
      v1[i] += 10;
      t--;
      nn = i;
    }
    i++;
  }

  if ( i < n1 )
    return n1;
  return nn + 1;
}

int inmultesteNn( int n, char *v, int a ) {
  int i, t;

  t = i = 0;
  while ( i < n || t > 0 ) {
    t = t + a * v[i];
    v[i] = t % 10;
    t /= 10;
    i++;
  }

  if ( i < n )
    return n;
  return i;
}

void printN( int n, char *v ) {
  int i;

  for ( i = n - 1; i >= 0; i-- )
    printf( "%d", v[i] );
  printf( "\n" );
}

int main () {
  int n1 = 5, n2 = 5;

  n1 = adunaNn( n1, v1, 75464 );
  printN( n1, v1 );
  n1 = scadeNn( n1, v1, 75464 );
  printN( n1, v1 );
  n1 = adunaNN( n1, v1, n2, v2 );
  printN( n1, v1 );
  n1 = scadeNN( n1, v1, n2, v2 );
  printN( n1, v1 );

  n1 = inmultesteNn( n1, v1, 75464 );
  printN( n1, v1 );

  return 0;
}</syntaxhighlight>

== Discuţie despre problemele date la olimpiadă ==
Am discutat despre rezolvări optime la problemele:

* [http://varena.ro/problema/ech ech] dată la OJI 2015 clasa a 7<sup>a</sup>
* [http://varena.ro/problema/dominant dominant] dată la OJI 2015 clasa a 8<sup>a</sup>

= Temă =
== Clasa a 7-a ==
* [http://varena.ro/runda/2015-03-10-clasa-7-tema-23 Tema 24 clasa a 7<sup>a</sup>]
* '''Opţional''': tema de clasa a 8<sup>a</sup>

== Clasa a 8-a ==
* [http://varena.ro/runda/2015-03-10-clasa-8-tema-23 Tema 24 clasa a 8<sup>a</sup>]
* '''Opţional''': tema de clasa a 7<sup>a</sup>

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_24_-_10_mar_2015]