Clasa a VI-a lecția 5 - 20 oct 2015

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]


Lecție

Baze de numerație - continuare

Exercițiu: submulțimile unei mulțimi

Aceasta este o problemă clasică în matematică și informatică.

Rezolvați în clasă următorul exercițiu: să se afișeze toate submulțimile nevide ale mulțimii { 1, 2, 3, ..., n }.

Cum abordăm această problemă? La prima vedere pare foarte grea. Va trebui, probabil, să afișăm toate submulțimile de un element. Aceasta e simplu. Apoi cele de două elemente. Tot simplu, vom selecta perechile cu două bucle for. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle for. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de n. Dar stai! Nu putem scrie un număr variabil de bucle for una într-alta!

Ne trebuie o altă abordare. Vom codifica mulțimile. Cum? Foarte simplu: folosind vectorul lor caracteristic. Pentru fiecare element al mulțimii, de la 1 la n, vom avea un element în vectorul v. Pentru o submulțime dată v[i] este 1 dacă elementul i apare în submulțime.

Acest mod de codificare demonstrează un lucru interesant: numărul de submulțimi al unei mulțimi, incluzînd mulțimea vidă, este 2n. Interesant!

Cum vom folosi acest vector? Destul de neclar. Ne-ar trebui un mod în care să variem toate elementele sale de la zero la unu. Și iar ne întoarcem la buclele for una într-alta. Dar există un mod natural în care elementele pot trece prin toate combinațiile posibile de 0 și 1: dacă în loc să folosim un vector cu n elemente folosim un număr binar cu n cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele n cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

În concluzie, care este algoritmul? Iată-l descris mai jos:

1. Pentru i de la 1 la 2^n - 1
    1.1 Descompune i în baza 2
    1.2 Pentru fiecare cifră binară 1 care se află pe poziția j
        1.2.1 Afișează j
    1.3 Sfîrșit de submulțime, treci la linia următoare

Remarcați că algoritmul nu folosește vectori! Vă invit să rezolvați problema submulțimi1 la vianuarena, folosind acest algoritm. După ce o rezolvați, pentru verificare, iată codul complet mai jos:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, m, i, p2max, p;

  fin = fopen( "submultimi1.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  p2max = 1; // calculam 2^n, numarul pina unde trebuie sa numaram
  for ( i = 0; i < n; i++ )
    p2max *= 2;

  fout = fopen( "submultimi1.out", "w" );
  for ( i = 1; i < p2max; i++ ) {  // numaram de la 1 la 2^n exclusiv
    m = i;                         // copiem contorul, sa nu il pierdem
    for ( p = 1; p <= n; p++ ) {   // obtinem pe rind cifrele binare
      if ( m % 2 == 1 )            // 1 inseamna ca pozitia apartine multimii
        fprintf( fout, "%d ", p ); // afisam pozitia cifrei 1, p
      m /= 2;
    }
    fprintf( fout, "\n" );         // am afisat o submultime, linie noua
  }
  fclose( fout );

  return 0;
}

Alte baze

Pînă acum am vorbit numai despre baza 10 și baza 2. Există însă o infinitate de baze. Orice număr întreg poate fi folosit ca bază pentru scrierea numerelor. Exemple:

  • Baza 8 este folosită în sisteme de operare pentru exprimarea drepturilor utilizatorilor asupra resurselor
  • Baza 16 este folosită în calculatoare pentru descrierea succintă a numerelor

Lucrul cu alte baze este similar cu lucrul în baza 2 sau baza 10 așa încît nu avem ce menționa în plus. Nu uitați: principiul de conversie de la baza 10 la baza 2 și invers funcționează și în conversiile de la baza 10 la alte baze și invers. De asemenea funcționează și analogia bazelor.

Să vedem acum folosirea unei baze importante, baza 16.

Baza 16

Baza 16 folosește 16 cifre hexazecimale. Primele 10 cifre sînt cele cunoscute. Următoarele 6 cifre sînt primele litere ale alfabetului latin: A, B, C, D, E și F. A are valoarea 10, B are valoarea 11 și așa mai departe pînă la F care are valoarea 15. De exemplu:

B9A(16) = B×162 + 9×16 + A = 11×162 + 9×16 + 10 =
= 11×256 + 9×16 + 10 = 2816 + 144 + 10 = 2970(10)

Conversia de la baza 2 la baza 16

Pentru a converti un număr de la baza 2 la baza 16 nu este nevoie să trecem prin baza 10. Putem proceda astfel:

  • Grupăm cifrele numărului binar cîte patru, începînd de la dreapta către stînga. Ultima grupă poate să aibă mai puțin de patru cifre binare.
  • Fiecare grup va fi un număr binar între 0 și 15, adică echivalentul unei cifre hexazecimale. Înlocuim aceste grupuri cu cifra echivalentă în baza 16.

Exemplu:

1010110110010110111(2) = 101 0110 1100 1011 0111(2) = 5 6 12 11 7 = 56CB7(16)

Conversia de la baza 16 la baza 2

Pentru a converti rapid un număr de la baza 16 la baza 2 vom proceda în sens invers: vom exprima fiecare cifră hexa ca patru cifre binare, făcînd conversia la baza 2 a valorii cifrei hexa. Exemplu:

56CB7(16) = 5 6 12 11 7 = 101 0110 1100 1011 0111(2) = 1010110110010110111(2)

Constante hexazecimale în C

La problema dublă conversie am avut nevoie să calculăm 260. Avem mai multe variante de a face acest lucru:

  • Putem să calculăm acest număr cu un calculator de buzunar și să îl introducem în program
  • Putem să îl scriem în program ca produsul 1048576LL * 1048576LL * 1048576LL. 'LL' adăugat la finalul unei constante o transformă în constantă de tip long long.
  • Putem să îl calculăm în program într-o buclă for.

Nici una din aceste metode nu este prea elegantă. De aceea limbajul C ne permite folosirea constantelor hexazecimale. Acestea sînt numere scrise în baza 16. Pentru ca compilatorul să își dea seama că sînt numere și nu nume de variabile aceste constante trebuie precedate de '0x'. Exemplu: 0x56CB7. Pentru cifrele mai mari ca 9 puteți folosi litere mici sau mari, nu are importanță.

Astfel:

260 = 1000...(60 zerouri)...000(2) =
1 0000 0000 0000 ...(15 grupe)... 0000(2) = 1000000000000000(16)

Acum avem încă o metodă, mai simplă, de a calcula 260: folosind conversia rapidă de la baza 2 la baza 16 și apoi scriind o constantă hexa:

  • Putem folosi direct constanta hexa 0x1000000000000000LL. Avem 15 cifre 0 hexa, echivalentul a 60 de cifre 0 binare. Observați că numărul se termină cu 'LL' deoarece este o constantă long long.

Vom vedea cu altă ocazie că există o metodă și mai scurtă de a folosi această constantă.

Exerciții cu alte baze

Rezolvați în clasă următoarea problemă:

Baza ascunsă

Rezolvați în timpul cercului problema baza ascunsă la vianuarena.

Temă

Rezolvări aici [2]