Clasa VI/VII/VIII lecția 18 - 29 ian 2013

From Algopedia
Jump to: navigation, search

Clasa a șasea, a șaptea și a opta împreună

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

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:

char v[100];

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:

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

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

  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;

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

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

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

  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;

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

  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;

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.

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

Cei de a șasea: puteți lucra la tema, pentru a exersa numerele mari. Cei ce doresc pot urmări în continuare lecția de programare dinamică.

Clasa a șaptea și a opta

Programare dinamică

Introducere

Wikipedia definește programarea dinamică drept "... o metodă pentru rezolvarea unor probleme complexe prin descompunerea lor în subprobleme mai simple. Se poate aplica problemelor care prezintă proprietățile de suprapunere a subproblemelor și de substructură optimală. Atunci cînd se poate aplica, metoda ia mult mai puțin timp decît alte soluții naive.

Drumul cel mai scurt între două orașe poate fi rezolvat cu programare dinamică

Substructura optimală înseamnă că soluția unei problemei de optimizare date poate fi obținută prin combinarea unor soluții optimale ale subproblemelor. Ca atare, primul pas către găsirea unei rezolvări prin această metodă este verificarea dacă problema are proprietatea substructurii optimale. Astfel de substructuri optimale sînt în mod usual descrise prin recurență. De exemplu, date niște orașe și distanțele între ele, drumul cel mai scurt de la orașul u la orașul v are proprietatea de substructură optimală: să luăm orice oraș intermediar w pe drumul cel mai scurt, d. Dacă d este cu adevărat drumul cel mai scurt, atunci drumul d1 de la u la w și d2 de la w la v sînt cu adevărat cele mai scurte drumuri între orașele corespunzătoare. Dacă drumul de la u la w nu ar fi cel mai scurt posibil ar însemna că am avea un alt drum mai scurt, ceea ce ar duce la un drum total d, de la u la v, mai scurt decît cel original. Așadar, putem formula soluția problemei găsirii celui mai scurt drum într-o manieră recursivă, ceea ce fac algoritmii Bellman-Ford și Floyd-Warshall.

Suprapunerea subproblemelor înseamnă că ele nu sînt independente, adică subproblemele au în comun alte subprobleme. Nu vom insista pe această proprietate decît atît cît să menționăm că dacă subproblemele nu se suprapun dar prezintă substructură optimală atunci putem aplica tehnica de programare divide et impera (divide and conquer). De aceea quicksort și mergesort nu sînt clasificate ca probleme de programare dinamică.

Subșirul crescător de lungime maximă

Subsecvența continuă de sumă maximală

Subșirul comun maximal al două siruri - varianta continuu

Subșirul comun maximal al două siruri - varianta necontinuu

Distanța edit (Levenshtein)

Pe viitor

Înmulțirea optimală a unui șir de matrice

Problema rucsacului

Teme

Teme clasa a șasea

  • Terminați temele din urmă: nr la vianuarena și taste la campion
  • Problema muguri la campion.
  • Opțional: problema fib la campion.

Teme clasa a șaptea

  • Terminați temele din urmă: char și maraton1 la campion
  • Problema muguri la campion.
  • Implementați două probleme de programare dinamică: subșirul crescător de lungime maximă și subșirul comun maximal al două șiruri de caractere, varianta necontinuu.

Teme clasa a opta

  • Terminați temele din urmă: fracție1 și raze la campion
  • Problema muguri la campion
  • Implementați subșirul crescător de lungime maximă și subșirul comun maximal al două șiruri de caractere, varianta necontinuu.
  • Opțional: problema rucsacului. Se dă n și n greutăți numere naturale. Se dă s, capacitatea în kg a unui rucsac. Să se spună cît de bine putem umple rucsacul cu greutăți. Cu alte cuvinte care este capacitatea maximă pe care o putem încărca în rucsac fără a depăși rucsacul. O variantă a acestei probleme este rucsac, la vianuarena.