View source for Clasa a VI-a lecția 7

= Tema - rezolvări =

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_4_-_16_oct_2014]

= Lecție =
== Baze de numerație ==
Un ''sistem de numerație'' este un mod de a exprima numerele. Cu alte cuvinte o notație matematică pentru a reprezenta numerele folosind cifre sau alte simboluri într-o manieră consecventă. Sistemul de numerație este cel care face ca simbolurile "11" să fie interpretate ca simbolul binar al lui trei, simbolul zecimal al lui unsprezece, sau simbolul altor numere în diferite baze.

Un sistem de numerație:

* Reprezintă o mulțime utilă de numere (de ex. toți întregii, sau numerele raționale)
* Reprezintă unic fiecare număr
* Ideal, ar trebui să reflecte structura algebrică și aritmetică a numerelor

=== Sistemul pozițional zecimal ===
Denumit și scrierea arabă, a fost în fapt inventat în India undeva în secolele 5 și 6. Arabii, care aveau legături comerciale atît cu India cît și cu lumea vestică au preluat această scriere și au modificat-o. Chiar și în ziua de azi arabii denumesc scrierea lor zecimală "Rakam Al-Hind", sau sistemul de numerație Hindu. Lumea vestică a preluat această scriere și a denumit-o sistemul de numerație arab, deoarece au învățat-o de la ei.

Notația pozițională se distinge de alte notații (cum ar fi cea romană) prin faptul că același simbol reprezintă valori diferite în funcție de poziția pe care se află (de exemplu poziția unităților, a zecilor, sau a sutelor). Poziția unei cifre semnifică puterea lui zece cu care acea cifră trebuie înmulțită. De exemplu:

''304 = 3×100 + 0×10 + 4×1 = 3×10<sup>2</sup> + 0×10<sup>1</sup> + 4×10<sup>0</sup>''

Această notație a simplificat enorm aritmetica ceea ce a dus la răspîndirea sa rapidă în lume.

Deoarece folosește zece cifre, iar puterile cu care se înmulțesc pozițiile sînt puterile lui zece spunem că sistemul de numerație arab folosește ''baza 10''.

=== Sistemul pozițional binar ===
Sistemul pozițional binar este similar cu cel zecimal, cu diferența că baza lui este doi. Aceasta înseamnă că folosește doar două cifre, 0 și 1, iar puterile cu care se înmulțesc cifrele pe diferite poziții sînt puterile lui doi. Astfel:

''11010 = 1×2<sup>4</sup> + 1×2<sup>3</sup> + 0×2<sup>2</sup> + 1×2<sup>1</sup> + 0×2<sup>0</sup>''

adică

''11010 = 1×16 + 1×8 + 0×4 + 1×2 + 0×1 = 26''

=== Conversia de la baza 10 la baza 2 ===
Pentru a converti un număr ''n'' din baza 10 în baza 2 îl vom împărți la 2 în mod repetat, pîna ce obținem cîtul zero. Apoi vom colecta resturile obținute de la ultimul către primul. Aceste resturi sînt cifrele numărului în baza doi, de la stînga la dreapta.

==== Exemplul 1 ====
Să convertim numărul ''26'' la baza 2:

''26 = 2×13 + 0''<br/>
''13 = 2×6 + 1''<br/>
''6 = 2×3 + 0''<br/>
''3 = 2×1 + 1''<br/>
''1 = 2×0 + 1''<br/>
<br/>
''26<sub>(10)</sub> = 11010<sub>(2)</sub>''

==== Exemplul 2 ====
Să convertim numărul ''37'' la baza 2:

''37 = 2×18 + 1''<br/>
''18 = 2×9 + 0''<br/>
''9 = 2×4 + 1''<br/>
''4 = 2×2 + 0''<br/>
''2 = 2×1 + 0''<br/>
''1 = 2×0 + 1''<br/>
<br/>
''37<sub>(10)</sub> = 100101<sub>(2)</sub>''

=== Conversia de la baza 2 la baza 10 ===
Această conversie se poate face direct, scriind fiecare cifră binară explicit înmulțită cu puterea corespunzătoare a lui 2.

==== Exemplul 3 ====
Să convertim numărul ''100101'' din baza 2 în baza 10:

''100101<sub>(2)</sub> = 1×2<sup>5</sup> + 0×2<sup>4</sup> + 0×2<sup>3</sup> + 1×2<sup>2</sup> + 0×2<sup>1</sup> + 1×2<sup>0</sup>''<br/>
''100101<sub>(2)</sub> = 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 1×1''<br/>
''100101<sub>(2)</sub> = 32 + 4 + 1''<br/>
''100101<sub>(2)</sub> = 37<sub>(10)</sub>''<br/>

Deși această metodă a evaluării directe prin dezvoltarea numărului cu puterile lui doi este mai simplu de înțeles, există un algoritm ceva mai rapid. Începînd cu rezultatul ''0'', parcurgem cifrele binare de la stînga la dreapta. Pentru fiecare cifră a numărului de la intrare vom înmulți rezultatul cu doi și vom aduna cifra la rezultat.

==== Exemplul 4 ====
Să convertim numărul ''11010'' din baza 2 în baza 10 folosind acest algoritm:

''0×2 + 1 = 1''<br/>
''1×2 + 1 = 3''<br/>
''3×2 + 0 = 6''<br/>
''6×2 + 1 = 13''<br/>
''13×2 + 0 = 26''<br/>
<br/>
''11010<sub>(2)</sub> = 26<sub>(10)</sub>''<br/>

Acesta este algoritmul pe care îl vom prefera pentru conversia numerelor din baza 2 în baza 10.

=== Analogia bazelor ===
Cum ținem minte acești algoritmi de conversie? Există un mod foarte simplu: atunci cînd vrem să facem o operație în baza doi ne întrebăm cum am face-o în baza zece. În calculul care rezultă vom înlocui apariția bazei, respectiv oriunde apare 10 vom pune 2.

De exemplu, dat numărul ''n'' în baza 10, cum putem afla ultima cifră din reprezentarea lui în baza 2? Dacă ne-am dori să aflăm ultima cifră din reprezentarea lui ''n'' în baza 10 vom calcula restul împărțirii lui ''n'' la 10. Prin analogie, ultima cifră din reprezentarea în baza 2 va fi restul împărțirii lui ''n'' la 2.

Mai departe, dacă ne dorim să obținem numărul din care am tăiat ultima lui cifră din reprezentarea în baza doi cum vom proceda? În baza zece, pentru a tăia ultima cifră vom folosi împărțirea la 10. Deci, în baza 2, vom împărți numărul la doi.

==== Exemplul 5 ====
Acum, să scriem un program care afișează cifrele reprezentării în baza 2 numărului ''n'', în ordine inversă. Să scriem programul pentru a afișa cifrele numărului ''n'' în baza 10:

<syntaxhighlight>while ( n > 0 ) {
  printf( "%d ", n % 10 );
  n = n / 10;
}</syntaxhighlight>

Pentru a obține cifrele în baza 2 vom înlocui peste tot în program 10 cu 2:

<syntaxhighlight>while ( n > 0 ) {
  printf( "%d ", n % 2 );
  n = n / 2;
}</syntaxhighlight>

Observați că exact aceasta este metoda descrisă mai sus, în exemplele 1 și 2! Pentru a afișa numărul în baza doi tot ce avem de făcut este să memorăm cifrele într-un vector și la final să le afișăm în ordine inversă.

==== Exemplul 6 ====
Să scriem un program care convertește un număr din baza 2 în baza 10, pornind de la cifrele în baza 2. Cifrele se află pe o singură linie, fără spații, într-un fișier. Să pornim cu programul care reconstruiește numărul pornind de la cifrele sale în baza 10:

<syntaxhighlight>n = 0;
ch = fgetc( fin );
while ( ch != '\n' ) {
  n = n * 10 + (ch - '0');
  ch = fgetc( fin );
}
printf( "%d", n )</syntaxhighlight>

Pentru a obține programul care convertește ''n'' de la baza 2 la baza 10 vom înlocui aparițiile lui 10 cu 2 în programul anterior:

<syntaxhighlight>n = 0;
ch = fgetc( fin );
while ( ch != '\n' ) {
  n = n * 2 + (ch - '0');
  ch = fgetc( fin );
}
printf( "%d", n )</syntaxhighlight>

=== Exerciții ===
==== Conversie de la baza 10 la baza 2 ====
Se citește <tt>n</tt> de maxim 18 cifre. Să se afișeze reprezentarea lui în baza 2.

Varianta clasică, despre care am vorbit mai sus, este cea în care reținem resturile împărțirii repetate la doi și apoi le afișăm în ordine inversă:

<syntaxhighlight>#include <stdio.h>

int cifre[60]; // 60 de cifre binare = 18 cifre zecimale

int main() {
  FILE *fin, *fout;
  int m, i;
  long long n; // 18 cifre inseamna long long

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

  m = 0;
  while ( n > 0 ) {
    cifre[m] = n % 2; // extragem pe rind resturile impartirii la 2
    m++;
    n /= 2;
  }

  fout = fopen( "b10b2.out", "w" );
  for ( i = m - 1; i >= 0; i-- ) // afisam resturile in ordine inversa
    fprintf( fout, "%d", cifre[i] );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}</syntaxhighlight>

Să ne aducem acum aminte de analogia bazelor: să ne imaginăm că am vrea să afișăm nu cifrele numărului în baza doi ci chiar cele în baza zece. Cum am putea proceda? Fie ca mai sus, prin împărțiri repetate la zece. Dar am putea proceda și altfel: să calculăm <tt>p10</tt>, cea mai mare putere a lui 10 mai mică sau egală cu numărul <tt>n</tt>. Prima cifră zecimală a lui <tt>n</tt> este <tt>n/p10</tt>. Apoi tăiem prima cifră calculînd <tt>n = n%p10;</tt> Apoi împărțim <tt>p10</tt> la zece și reluăm.

Putem proceda exact la fel și în baza 2! Vom înlocui <tt>p10</tt> cu <tt>p2</tt>, iar toate împărțirile vor fi la doi. Iată această variantă, care nu folosește vectori:

<syntaxhighlight>#include <stdio.h>

#define MAXP2 (1048576LL * 1048576LL * 1048576LL)

int main() {
  FILE *fin, *fout;
  long long n, p2; // 18 cifre inseamna long long

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

  p2 = MAXP2;      // 2^60 este mai mare ca 10^18
  while ( p2 > n ) // cautam cea mai mare putere a lui 2 mai mica sau egala cu n
    p2 /= 2;

  fout = fopen( "b10b2.out", "w" );
  while ( p2 > 0 ) {
    fprintf( fout, "%lld", n / p2 ); // afisam prima cifra a numarului n
    n %= p2;                         // o taiem din numarul n
    p2 /= 2;                         // trecem la urmatoarea cifra, micsoram p2
  }
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}</syntaxhighlight>

==== Conversie de la baza 2 la baza 10 ====
La intrare avem o înșiruire de caractere 0 și 1, neseparate de spații și terminate cu final de linie. Ele reprezintă un număr în baza 2 de cel mult 60 de cifre binare. Să se convertească acest număr la baza 10 și să se afișeze.

Vom proceda precum am discutat mai sus. Vom citi cifrele binare una cîte una și le vom adăuga la coada lui <tt>n</tt>, înmulțindu-l pe acesta cu doi și apoi adunînd cifra. Iată programul:

<syntaxhighlight>#include <stdio.h>

int main() {
  FILE *fin, *fout;
  long long n; // 18 cifre inseamna long long
  char ch;

  fin = fopen( "b2b10.in", "r" );
  n = 0;
  ch = fgetc( fin );
  while( ch != '\n' ) {
    n = n * 2 + ch - '0';
    ch = fgetc( fin );
  }
  fclose( fin );

  fout = fopen( "b2b10.out", "w" );
  fprintf( fout, "%lld\n", n );
  fclose( fout );

  return 0;
}</syntaxhighlight>

==== Numărul de cifre binare 1 ====
Se dă un număr zecimal <tt>n</tt> cu proprietatea că <tt>n &le; 10<sup>18</sup></tt>. Să se afișeze numărul de cifre binare 1 din reprezentarea lui în baza 2.

Știm să extragem cifre binare de la coada reprezentării în baza doi a lui <tt>n</tt>. Drept pentru care le vom extrage pe toate văzînd care sînt unu:

<syntaxhighlight>#include <stdio.h>

int main() {
  FILE *fin, *fout;
  long long n; // 18 cifre inseamna long long
  int nr1;

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

  nr1 = 0;
  while ( n > 0 ) {
    if ( n % 2 == 1 )
      nr1++;
    n /= 2;
  }

  fout = fopen( "nr1b2.out", "w" );
  fprintf( fout, "%d\n", nr1 );
  fclose( fout );

  return 0;
}</syntaxhighlight>

Folosind operatorii pe biti, putem folosi o masca care sa extraga pe rand fiecare bit din reprezentarea numarului in baza 2. Aceasta masca va fi initial 2<sup>0</sup> adica 1, pentru a extrage ultimul bit, apoi 2<sup>1</sup> pentru a extrage al doilea bit, etc pana cand parcurgem toti bitii din reprezentarea interna a numarului, in cazul nostru cei 63 de biti avand in vedere ca n este long long. Iata implementarea acestei idei:  

<syntaxhighlight>#include <stdio.h>

int main() {
  FILE *fin, *fout;
  long long n, i; // 18 cifre inseamna long long
  int nr1;

  fin = fopen( "nr1b2.in", "r" );
  fscanf( fin, "%lld", &n );
  fclose( fin );
  contor = 0;
  while (n>0){
    if( n & 1) 
      contor++;
    n = n >> 1;  //scap de ultimul bit prin deplasarea la dreapta a tuturor bitilor lui n. Echivalent cu n = n / 2;
  }
  fout = fopen( "nr1b2.out", "w" );
  fprintf( fout, "%d\n", nr1 );
  fclose( fout );

  return 0;
}</syntaxhighlight>

Aceasta metoda este echivalenta cu prima, avand aceeasi complexitate O(log n), parcurgand toate cifrele binare ale numarului. Putem optimiza aceasta solutie daca am putea sari peste cifrele de 0 si numara direct cifrele de 1. Prin exemplul de mai jos putem vedea ca daca efectuam n & (n-1) vom elimina ultima cifra de 1 din n. 

 
11011101010000 = n

11011101001111 = n - 1

11011101000000 = n & (n - 1)


Vom folosi acest truc pentru a elimina pe rand cifrele binare 1 pana cand numarul n devine 0.
<syntaxhighlight>#include <stdio.h>
int main() {
  FILE *fin, *fout;
  long long n, i; // 18 cifre inseamna long long
  int nr1;

  fin = fopen( "nr1b2.in", "r" );
  fscanf( fin, "%lld", &n );
  fclose( fin );
  contor = 0;
  while (n>0){
    contor++;        //daca n> 0 sigur avem o cifra de 1 
    n = n & (n-1);   //scap de ultimul bit 1 
  }
  fout = fopen( "nr1b2.out", "w" );
  fprintf( fout, "%d\n", nr1 );
  fclose( fout );

  return 0;
}</syntaxhighlight>

==== Complementul unui număr ====
Se definește complementul unui număr <tt>n</tt> astfel: se convertește <tt>n</tt> la baza 2, apoi fiecare cifră binară a reprezentării se neagă: dacă era 1 este transformată în 0 și invers. Ceea ce rezultă se convertește înapoi în baza 10 și numărul rezultat este complementul lui <tt>n</tt>. Se dă un număr <tt>n</tt>, <tt>n &le; 2 000 000 000</tt> să se afișeze complementul lui. Exemplu: <tt>45<sub>(10)</sub></tt> se reprezintă în baza doi ca <tt>101101<sub>(2)</sub></tt>, a cărui negare este <tt>010010<sub>(2)</sub></tt>, care convertită înapoi la baza 10 este <tt>18<sub>(10)</sub></tt>, deci se va afișa <tt>18</tt>.

Vom calcula complementul astfel: vom extrage, pe rînd cîte o cifră binară de la coada reprezentării lui <tt>n</tt>. Scăzînd-o din 1 vom obține negarea acelei cifre. Adunăm această negare la complement, după ce o înmulțim cu puterea corectă. Apoi tăiem ultima cifră a lui <tt>n</tt> împărțindu-l la doi și mărim puterea înmulțind-o cu doi. Continuăm pînă ce <tt>n</tt> nu mai are cifre (este zero).

<syntaxhighlight>#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, c, p2;

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

  c = 0;
  p2 = 1; // puterea lui doi este initial 1
  while ( n > 0 ) { // mai avem cifre in n?
    // extragem ultima cifra, o negam si o adunam la complement inmultita cu
    // puterea corecta
    c = c + p2 * (1 - n % 2);
    n /= 2;  // taiem ultima cifra
    p2 *= 2; // avansam la urmatoarea putere
  }

  fout = fopen( "complement.out", "w" );
  fprintf( fout, "%d\n", c );
  fclose( fout );

  return 0;
}</syntaxhighlight>

==== Palindrom binar ====
Se dă un numar <tt>n</tt>. Să se spună dacă reprezentarea lui în baza 2 este un palindrom. De exemplu <tt>45<sub>(10)</sub></tt> este un număr palindrom binar deoarece se reprezintă în baza doi ca <tt>101101<sub>(2)</sub></tt>, care este palindrom.

Din nou, am putea fi tentați să procedăm ca la conversia clasică: să extragem resturile împărțirilor repetate la doi într-un vector, apoi să testăm că vectorul este simetric. Vă las pe voi să faceți așa.

Noi vom proceda altfel, folosindu-ne iarăși de analogia bazelor: în baza zece calculam răsturnatul numărului zecimal și apoi comparam cele două numere. Așa vom proceda și aici, doar că vom calcula răsturnatul binar al numărului, înlocuind aparițiile bazei zece cu doi. Iată programul (extrem de simplu):

<syntaxhighlight>#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, nc, p;

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

  nc = n;
  p = 0;
  while ( n > 0 ) {
    p = p * 2 + n % 2;
    n /= 2;
  }

  fout = fopen( "palindrom2.out", "w" );
  if ( nc == p )
    fprintf( fout, "DA\n" );
  else
    fprintf( fout, "NU\n" );
  fclose( fout );

  return 0;
}</syntaxhighlight>

==== Dublă conversie ====
Rezolvați în timpul cercului problema [http://varena.ro/problema/dconv dublă conversie] la vianuarena.

O dublă conversie a unui număr zecimal la baza doi se calculează astfel: convertim numărul la baza doi. Apoi numărul rezultat, format numai din zero și unu, îl considerăm număr zecimal. Convertim acest număr zecimal la baza doi și obținem rezultatul dublei conversii.

'''Exemplu''': <tt>45<sub>(10)</sub></tt> se reprezintă în baza doi ca <tt>101101<sub>(2)</sub></tt>. Drept pentru care vom considera numărul <tt>101101<sub>(10)</sub></tt> (în baza 10) și-l vom converti la baza doi obținînd <tt>11000101011101101<sub>(2)</sub></tt>.

Se citește la intrare un număr zecimal <tt>n</tt> (<tt>1 &le; n &le; 200 000</tt>) să se calculeze și să se afișeze dubla lui conversie la baza 2.

= Temă =
** Problema [http://varena.ro/problema/dconv dublă conversie]
** Problema [http://varena.ro/problema/monsters monsters]
** Problema [http://varena.ro/problema/suprapuneri suprapuneri]]

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_4_-_13_oct_2015]