Clasa a VI-a lecția 5 - 18 oct 2018

From Algopedia
Jump to: navigation, search

Comentarii temă

Avertisment celor ce nu au trimis surse la problemele cautbin sau divprimi: Cemârtan (cautbin), Grecu (divprimi), Hossu (divprimi), Stancu (cautbin liniar, divprimi), Teodorescu (divprimi)

Comentarii problema praslea

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: Tatomir.
  • Unii din voi au rezolvat partea a doua parcurgînd toate parcelele (maxim 500000) în loc să parcurgă doar parcelele speciale (maxim 10000).
  • Unii din voi nu s-au prins că lungimile parcelelor depășesc int. Trebuia să folosiți fie unsigned, fie long long
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Aizic, Cemârtan, Cojocaru, Coman, Dumitrescu, Mocanu, Mușat, Stoian, Simon, Stancu
  • Avertisment celor ce nu au rezolvat problema prin sortare prin selecție, ci cu sortare cu vectori de frecvență: Benescu, Dragomir, Grecu, Hossu, Iordache, Nicola, Rebengiuc, Rughiniș, Cadîr, Teodorescu. Tema era să exersăm sortarea prin selecție și v-am spus de multe ori acest lucru, ultima oară pe grup. Penalizarea e a voastră.
  • Avertismente pentru pescarii programatori prin aproximări succesive și testare la varena: Fares.

Comentarii individuale

Grupa de dimineață

  • Aizic: nimic?
  • Badea: rezolvare bună, bravo! Nu iei 100p din neatenție, uiți să iei în calcul primele parcele, pînă în parcela specială numărul 1. De asemenea pare că dacă pomul este la hotarul dintre două parcele ai probleme. Ca idee, ai parcurs toate parcelele. Era deajuns să le parcurgi doar pe cele speciale.
  • Benescu: nu ai folosit sortare prin selecție. Spui că nu știi cum să o folosești. Cu toate acestea tu faci o sortare prin vectori de frecvență. Pare că pe aceea ai știut să o folosești. Dacă nu ai nici o idee, întreabă pe listă sau pe mine personal. Ai declarat vectorul de 500002 elemente. Pot să înțeleg 500001, dar 500002 este neglijență. Declari lp ca unsigned, dar îl citești ca int. Posibil că de aceea pici teste.
  • Burac: ai avertisment de compilare, variabilă neinițializată. Setează -O2 și -Wall la build. Rezolvare bună, bravo! Ai grijă la sortare. Mergi cu i pînă la 1 inclusiv, ceea ce înseamnă că sortezi un vector cu un element. Iar max nu se inițializează cu zero, ci cu primul element al vectorului. Ai declarat toate variabilele long long. Ca să nu trebuiască să mai gîndești, că e periculos să gîndești, nu? În schimb nu ai declarat vectorul v2[] de long long, sau unsigned, exact cel care chiar trebuia să fie long long sau unsigned. Ca idee, ai parcurs toate parcelele. Era deajuns să le parcurgi doar pe cele speciale.
  • Calotă: ai avertisment de compilare. Setează -O2 și -Wall în proiectul CodeBlocks. Folosești vectorii ord[] și d[] de la unu și nu de la zero, de ce? De ce declari fiecare variabila pe linia ei? La sortare execuți min = 10001, nu e corect, confunzi indicii cu valoarea elementelor. Pozițiile parcelelor pot fi maxim 500000. Din păcate nu îți merge sortarea (ceea ce puteai să te prinzi) așa că pici multe teste.
  • Cemârtan: nimic?
  • Chivu: rezolvare bună, bravo! Eroarea principală e că nu ai declarat lungimile ca unsigned. Ca idee, ai parcurs toate parcelele. Era deajuns să le parcurgi doar pe cele speciale.
  • Cojocariu: tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. De aceea prima parte nu îți merge, iar a doua merge parțial. Ideea era să folosești doar sortarea prin selecție... Codul este rezonabil, poate fi făcut să meargă. La prima cerință calculezi maximul cu unu în plus.
  • Cojocaru: nimic?
  • Coman: nimic?
  • Dragomir: atenție la avertismentele de compilare, folosești o variabilă neinițializată. Setează -O2 și -Wall în CodeBlocks. Rezolvarea ta nu folosește sortare prin selecție, ci sortare prin vectori de frecvență. Te încurci în cei doi vectori, nu aveai nevoie decît de unul singur și nu trebuia să fie de unsigned long long ci doar de unsigned. De aceea depășești memoria. Ai grijă să o calculezi înainte!
  • Dumitrescu: nimic?
  • Grecu: rezolvare în regulă, dar nu folosești sortarea prin selecție, ci sortarea prin vectori de frecvență. În evaluatorul Windows ai fi depășit memoria, ai nevoie de 500000 de long long, adică 4MB. Programul unde mai încape?
  • Hossu: o soluție foarte bună, dar cu sortare prin vectori de frecvență, nu prin selecție.
  • Iordache: nu ai folosit sortarea prin selecție. Nu te-ai prins că lungimile parcelelor depășesc int, deci trebuia să folosești unsigned.
  • Mocanu: nimic?
  • Mușat: nimic?
  • Nicola: o soluție rezonabilă, dar cu sortare prin vectori de frecvență, nu prin selecție.
  • Petcu: o soluție rezonabilă, bravo! Atenție la vectori, lungimile parcelelor pot depăși int, trebuia să folosești unsigned. În prima parte nu pare că iei în considerare și parcelele din-nainte de prima parcelă specială (pi[0]). În partea a doua faci scăderi repetate, puteai să folosești înmulțiri sau împărțiri.
  • Rebengiuc: o soluție foarte bună, dar cu sortare prin vectori de frecvență, nu prin selecție. Einstein s-ar fi prins că nu asta am cerut :)
  • Rughiniș: o soluție foarte bună, dar cu sortare prin vectori de frecvență, nu prin selecție.
  • Stoian: nimic?
  • Ștefănescu: tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. De aceea prima parte nu îți merge, iar a doua merge parțial. Ideea era să folosești doar sortarea prin selecție... Ai grijă la memorie, vectorul dif[] nu este necesar, folosești elementele lui imediat ce le calculezi, iar apoi nu le mai refolosești. Lungimile parcelelor pot depăși int! Atenție te rog, cred că de aceea nu îți merg multe cazuri.
  • Togan: ai avertismente de compilare, din care unul serios, imax neinițializată. Programul tău este extrem de greu de urmărit. De ce sortezi de m ori? Pare că poate fi făcut să meargă, dar este de lung și greu de urmărit. Îmi pare rău, nu pot să îți spun prea multe despre el. Ordonează-ți gîndurile înainte de a începe să scrii programul.
  • Voicu: tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. Nu închizi fișiere. Rămășițe de la freopen. Din nou, faci cum știi tu lucrurile.

Grupa de după-amiază

  • Asgari: o soluție foarte bună, dar tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. Ideea era să folosești doar sortarea prin selecție.
  • Cadîr: o soluție foarte bună, dar cu sortare prin vectori de frecvență, nu prin selecție. Ai declarat vector aproximativ, de 500005 elemente. În caz că vine zîna indicilor și îți dă depășire. Ne supărăm!
  • Dobre: o soluție foarte bună, dar tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. Ideea era să folosești doar sortarea prin selecție. Atenție la lungimile parcelelor, ele pot depăși int. Trebuia să folosești unsigned.
  • Fares: pescuitul sportiv în floare! Ne supărăm! Rezolvare în regulă, dar tu ai făcut o combinație: ai sortat prin selecție pentru prima cerință, dar ai sortat prin vectori de frecvență pentru a doua cerință. Ideea era să folosești doar sortarea prin selecție. În evaluatorul Windows ai fi depășit memoria, ai nevoie de 500000 de long long, adică 4MB. Programul unde mai încape? Ai declarat vector aproximativ, de 500003 elemente. În caz că vine zîna indicilor și îți dă depășire. Ne supărăm!
  • Ilie: rezolvare bună, bravo! Ca idee, ai parcurs toate parcelele. Era deajuns să le parcurgi doar pe cele speciale. Nu treci toate testele pentru că ai mers cu analiza parcelelor pînă la m-2 în for-ul for(i=1; i<m-1; i++). Trebuia să mergi pînă la m-1.
  • Ipate: Ai declarat toate variabilele long long. Că doar nu dai de la tine. Să fie, mai bine mai mari decît prea mici. Și să nici nu facem prea multe calcule, căci obosim și nu mai sîntem apți de olimpiada de matematică. Altfel o rezolvare bună, bravo! Ca idee, ai parcurs toate parcelele. Era deajuns să le parcurgi doar pe cele speciale.
  • Marcu: rezolvare bună, bravo! Te-ai complicat la calcule, nu era așa greu. Dar îmi place că ai respectat cerința și că ai parcurs strict parcelele speciale, nu toate parcelele. Codul e un pic încîlcit, să te uiți și pe soluția de mai jos cum se putea face mai simplu.
  • Nicu: o rezolvare bună, bravo. Ai folosit sortarea prin selecție, dar ai folosit și un vector de frecvență care nu era necesar. Vezi soluția de mai jos.
  • Simon: nimic?
  • Stancu: nimic?
  • Tatomir: rezolvare perfectă. Foarte bine, bravo!
  • Teodorescu: rezolvare cu sortare prin vectori de frecvență, nu prin selecție. Înțeleg că ai o scuză, apreciez că mi-ai dat detalii. Dar dacă vrei să fii aici cu noi scuzele nu ajută. Iar la problema divprimi nu ai trimis nimic, deci cum e cu respectul? Programul are probleme de memorie, folosești 500000 de elemente long long, adica aproximativ 4MB.

Tema - rezolvări

Problema praslea

Problema prâslea a fost dată la ONI 2014 clasa a 6a. Ea se poate rezolva fără sortare prin selecție, dar a fost dată la temă ca aplicație a sortării prin selecție. Pentru a o rezolva să lămurim exemplul din enunț printr-o figură care ar fi fost tare bine dacă ar fi existat chiar în enunț:

Reprezentare grafică a exemplului din enunțul problemei

Parcelele speciale 1, 2 și 5 sînt desenate cu roșu, iar cele obișnuite cu albastru. Am figurat și poziția pomului.

Să presupunem că am avea parcelele speciale ordonate după poziția lor. În acest caz putem rezolva problema printr-o parcurgere a parcelelor speciale. Știm ce distantă se afla între două parcele speciale: vom avea diferența între pozițiile lor înmulțită cu lungimea unei parcele obișnuite. Astfel, la fiecare parcelă specială ne vom întreba:

  • Cîte parcele obișnuite se află între ea și parcela specială anterioară, actualizînd maximul dacă este nevoie
  • Dacă pomul se află în parcelele obișnuite din-naintea parcele curente speciale
  • Dacă pomul se află în parcela specială curentă

Desigur, pentru această rezolvare va trebui să ordonăm parcelele speciale după poziția lor. Iată o posibilă rezolvare cu aceste idei:

#include <stdio.h>

#define MAXM 10000

int p[MAXM];
unsigned int l[MAXM];

int main() {
  FILE *fin, *fout;
  int n, m, i, u, max, poz, lmax, ppom;
  unsigned int L, aux;
  long long d;

  fin = fopen( "praslea.in", "r" );
  fscanf( fin, "%d%d%u", &n, &m, &L );
  for ( i = 0; i < m; i++ )
    fscanf( fin, "%d%u", &p[i], &l[i] ); // citim perechile (p, l)
  fscanf( fin, "%lld", &d );
  fclose( fin );

  // sortam (p, l) crescator dupa p - ordinea parcelelor
  for ( u = m - 1; u > 0; u-- ) {
    max = p[0];
    poz = 0;
    for ( i = 1; i <= u; i++ )
      if ( p[i] > max ) {
        max = p[i];
        poz = i;
      }
    p[poz] = p[u];
    p[u] = max;
    aux = l[poz];
    l[poz] = l[u];
    l[u] = aux;
  }
  
  // calculam cerintele
  u = 0;
  lmax = 1;
  ppom = 0; // parcela pomului
  for ( i = 0; i < m; i++ ) {
    // cerinta a - numarul maxim de parcele alaturate de lungime L
    if ( p[i] - u > lmax )
      lmax = p[i] - u;

    // cerinta b - parcela pe care este pomul
    if ( ppom == 0 ) { // inca nu am gasit parcela pomului
      if ( (p[i] - u - 1) * (long long)L > d ) // pomul e pe parcele standard
        ppom = u + (d + L - 1) / L;
      else {
        d -= (p[i] - u - 1) * (long long)L; // ajustam distanta pomului
        if ( l[i] > d ) // pomul este in parcela speciala curenta
          ppom = p[i];
        else
          d -= l[i];
      }
    }
    u = p[i];
  }
  // cerinta a - test de lungime cu finalul de parcele
  if ( n + 1 - u > lmax )
    lmax = n + 1 - u;

  // cerinta b - test de parcela pomului la finalul de parcele
  if ( ppom == 0 )
    ppom = u + (d + L - 1) / L;
  
  fout = fopen( "praslea.out", "w" );
  fprintf( fout, "%d\n%d\n", lmax - 1, ppom );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Știm că prima parte, sortarea, este O(m2). Dar cea de-a doua parte, rezolvarea cerințelor? Deoarece bucla while se execută de m ori complexitatea ei va fi O(m). Se observă că timpul de rezolvare este dominat de sortare, complexitatea totală fiind O(m2).

Problema cautbin

Problema cautbin este clasică, aplicație directă a căutării binare. Să luăm pe rînd cele trei puncte.

Cerința 0

Se cere să găsim ultima apariție a lui x. Cum procedăm? Mai întîi ne hotărîm asupra testului. Am convenit că el va fi unul strict, fie mai mare, fie mai mic. Este destul de clar că dacă elementul curent din vector este strict mai mare decît x, atunci nu are sens să facă parte din intervalul nostru. De aici rezultă două lucruri:

  1. Testul va fi if ( v[med] > x )
  2. Intervalul de căutare va fi deschis la dreapta, iar intervalul original de căutare va fi [0..n)

La final, cînd intervalul rămîne de lungime unu ne vom întreba dacă v[st] == x.

Cerința 1

Se cere să găsim ultima poziție a unui element mai mic sau egal cu x. În fapt, ea este aceeași cerință cu cerința zero. Dacă rezolvăm această cerință vom găsi ultima apariție a lui x, dacă el există. Altfel vom găsi un element strict mai mic. Singura diferență față de cerința zero este că rezultatul va fi valoarea lui st indiferent de valoarea lui v[st].

Cerința 2

Se cere să găsim prima poziție a unui element mai mare sau egal cu x. Cum procedăm? La fel, să ne hotărîm asupra testului. Știm sigur că dacă elementul curent, la poziția din mijloc, este strict mai mic decît x, atunci îl putem scoate în afara intervalului, în partea stîngă, deoarece noi căutăm un element mai mare sau egal. De aici rezultă două lucruri:

  1. Testul va fi if ( v[med] < x )
  2. Intervalul de căutare va fi deschis la stînga, iar intervalul original de căutare va fi (-1..n-1]

Iată și programul bazat pe aceste idei:

#include <stdio.h>

int v[100000];

int main() {
  FILE *fin, *fout;
  int n, m, t, x, i, st, dr, med;

  fin = fopen( "cautbin.in", "r" );
  fout = fopen( "cautbin.out", "w" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fscanf( fin, "%d", &m );
  for ( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d", &t, &x );
    if ( t < 2 ) { // cazurile 0 si 1 sint similare
      // cautam cea mai mare pozitie pe care se afla <= x in intervalul [0 n)
      st = 0; // capatul din stinga este primul in intervalul [st dr), deci 0
      dr = n; // capatul din dreapta este primul in afara intervalului, deci n
      while ( dr - st > 1 ) {
        med = (dr + st) / 2;
        if ( v[med] > x ) // element strict mai mare?
          dr = med; // putem scoate pozitia med in dreapta afara intervalului
        else
          st = med; // altfel putem mari limita st catre med
      }
      if ( t == 0 && v[st] != x ) // in cazul 0 x trebuie sa fie gasit
        st = -2; // vom aduna unu la afisare
    } else {     // cautam prima aparitie a unui numar <= x in intervalul (-1 n-1]
      st = -1;   // capatul din stinga este ultimul in afara intervalului (-1 n-1]
      dr = n-1;  // capatul din dreapta este ultimul in interval, deci n-1
      while ( dr - st > 1 ) {
        med = (dr + st) / 2;
        if ( v[med] < x ) // element strict mai mic?
          st = med; // putem scoate pozitia med in stanga in afara intervalului
        else
          dr = med; // altfel putem micsora limita dr catre med
      }
      st = dr; // pentru a afisa totdeauna st ca rezultat
    }
    fprintf( fout, "%d\n", st + 1 ); // ajustam pozitia cu unu, ca in cerinta
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Vom efectua m căutari binare într-un vector de n elemente, deci complexitatea acestei soluții este O(m log n).

Problema divprimi

Problema divprimi a fost dată la olimpiada pe școală 2017 la Tudor Vianu, clasa a 10a. Ea este o aplicație a ciurului lui Eratostene. Cum o rezolvăm?

Precum am menționat la curs, putem adapta ciurul lui Eratostene pentru a calcula numărul de divizori primi ai numerelor pînă la n. Modificarea este simplă, în loc să atribuim unu elementelor vom crește cu unu, iar pornirea nu se va face de la d * d ci chiar de la d.

De remarcat că putem declara vectorul ciur ca vector de caractere. De ce? Deoarece numărul de divizori primi distincți ai oricărui număr mai mic sau egal cu un milion este cel mult șapte (demonstrați).

Odată calculat vectorul ciur am putea fi tentați să ordonăm numerele în ordinea cerută. Nu este cazul, trebuie doar să găsim al m-lea element. Pentru aceasta vom parcurge toate elementele cu un divizor, în ciur. Dacă nu găsim numărul nostru, vom parcurge toate elementele cu doi divizori, și tot așa pînă găsim numărul.

O optimizare ar putea fi să folosim un vector de frecvență al numărului de divizori, pentru a afla rapid cîți divizori are numărul căutat. Nu voi detalia soluția cu vector de frecvență pentru a nu o complica prea mult.

Iată o soluție posibilă:

#include <stdio.h>

#define MAXN 1000000

char ndivp[MAXN + 1];

int main() {
  FILE *fin, *fout;
  int n, m, d, nr, nd;

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

  for ( nr = 2; nr <= n; nr += 2 )
    ndivp[nr]++;
  for ( d = 3; d <= n; d += 2 )
    if ( ndivp[d] == 0 ) // numarul este prim
      for ( nr = d; nr <= n; nr += d )
        ndivp[nr]++;

  nd = nr = 1;
  m--;
  while ( m > 0 ) {
    if ( ++nr > n ) { // am terminat toate numerele cu nd divizori
      nr = 1;
      nd++;
    }
    if ( ndivp[nr] == nd )
      m--;
  }

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

  return 0;
}

Ce complexitate are această soluție? Deoarece ciurul este de la d complexitatea lui va fi O(n log n). Dar căutarea celui de-al m-lea element? Vom căuta prin vectorul ciur de un număr de ori care este maxim numărul maxim de divizori. Complexitatea căutării este, deci, O(div × n). Complexitatea totală este deci O(n × (log n + div). Dar, pentru orice număr x, numărul de divizori primi ai lui va fi mai mic decît log2x (demonstrați). De aceea putem ignora factorul div, complexitatea algoritmului fiind O(n log n).

Rezolvări aici [1]

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×102 + 0×101 + 4×100

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×24 + 1×23 + 0×22 + 1×21 + 0×20

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
13 = 2×6 + 1
6 = 2×3 + 0
3 = 2×1 + 1
1 = 2×0 + 1

26(10) = 11010(2)

Exemplul 2

Să convertim numărul 37 la baza 2:

37 = 2×18 + 1
18 = 2×9 + 0
9 = 2×4 + 1
4 = 2×2 + 0
2 = 2×1 + 0
1 = 2×0 + 1

37(10) = 100101(2)

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(2) = 1×25 + 0×24 + 0×23 + 1×22 + 0×21 + 1×20
100101(2) = 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 1×1
100101(2) = 32 + 4 + 1
100101(2) = 37(10)

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
1×2 + 1 = 3
3×2 + 0 = 6
6×2 + 1 = 13
13×2 + 0 = 26

11010(2) = 26(10)

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:

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

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

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

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:

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

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:

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

Exerciții

Conversie de la baza 10 la baza 2

Se citește n 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ă:

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

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 p10, cea mai mare putere a lui 10 mai mică sau egală cu numărul n. Prima cifră zecimală a lui n este n/p10. Apoi tăiem prima cifră calculînd n = n%p10; Apoi împărțim p10 la zece și reluăm.

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

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

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 n, înmulțindu-l pe acesta cu doi și apoi adunînd cifra. Iată programul:

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

Numărul de cifre binare 1

Se dă un număr zecimal n cu proprietatea că n ≤ 1018. 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 n. Drept pentru care le vom extrage pe toate văzînd care sînt unu:

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

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 20 adica 1, pentru a extrage ultimul bit, apoi 21 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:

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

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.

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

Complementul unui număr

Se definește complementul unui număr n astfel: se convertește n 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 n. Se dă un număr n, n ≤ 2 000 000 000 să se afișeze complementul lui. Exemplu: 45(10) se reprezintă în baza doi ca 101101(2), a cărui negare este 010010(2), care convertită înapoi la baza 10 este 18(10), deci se va afișa 18.

Vom calcula complementul astfel: vom extrage, pe rînd cîte o cifră binară de la coada reprezentării lui n. 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 n împărțindu-l la doi și mărim puterea înmulțind-o cu doi. Continuăm pînă ce n nu mai are cifre (este zero).

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

Palindrom binar

Se dă un numar n. Să se spună dacă reprezentarea lui în baza 2 este un palindrom. De exemplu 45(10) este un număr palindrom binar deoarece se reprezintă în baza doi ca 101101(2), 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):

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

Dublă conversie

Rezolvați în timpul cercului problema 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: 45(10) se reprezintă în baza doi ca 101101(2). Drept pentru care vom considera numărul 101101(10) (în baza 10) și-l vom converti la baza doi obținînd 11000101011101101(2).

Se citește la intrare un număr zecimal n (1 ≤ n ≤ 200 000) să se calculeze și să se afișeze dubla lui conversie la baza 2.

Temă

Rezolvări aici [2]