Bella: /* Temă */

2017-11-13T12:35:35Z

Temă

New page

= Tema - rezolvări =

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

= 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 <nowiki>{ 1, 2, 3, ..., n }</nowiki>.

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 <tt>for</tt>. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle <tt>for</tt>. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de <tt>n</tt>. Dar stai! Nu putem scrie un număr variabil de bucle <tt>for</tt> 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 <tt>n</tt>, vom avea un element în vectorul <tt>v</tt>. Pentru o submulțime dată <tt>v[i]</tt> este 1 dacă elementul <tt>i</tt> 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 <tt>for</tt> 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 <tt>n</tt> elemente folosim un număr binar cu <tt>n</tt> cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele <tt>n</tt> cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

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

<pre>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</pre>

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

<syntaxhighlight lang="C" style="border: dashed">#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;
}</syntaxhighlight>
=== 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 [http://varena.ro/problema/dconv 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 <tt>long long</tt>.
* Putem să îl calculăm în program într-o buclă <tt>for</tt>.

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ă <tt>long long</tt>.

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 [http://varena.ro/problema/ascunsa baza ascunsă] la vianuarena.

=== Concurs C4_6===
* [http://varena.ro/problema/paritate paritate] Cerc informatică Vianu [http://isa.algopedia.ro/wiki/index.php/paritate Rez]
* [http://varena.ro/problema/submult submult] Cerc informatică Vianu [http://isa.algopedia.ro/wiki/index.php/submult Rez]

= Temă =

* implementati singuri [http://varena.ro/problema/submultimi1 submulțimi1] (tema din urma)
* implementati problemele din concurs, conform corecturii.
** Pentru paritate, va rog sa implementati sursa c, cu citire caracter cu caracter pana la \n.
** Pentru problema submult, va rog sa faceti 2 implementari: cea cu numarare pana la 3n si alta simuland adunarea cu 1 pe vector a unui numar in baza 3 cu n cifre. Ultima implementare este de fapt adunarea unui numar mare cu un scalar.

** [http://varena.ro/problema/ascunsa baza ascunsă]
** [http://varena.ro/problema/decbin Decbin]

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

Suplimentar, daca aveti toate temele facute:
* [http://varena.ro/problema/cepe cepe]

Clasa a VI-a lecția 9 - Revision history

Bella: /* Temă */