Difference between revisions of "Clasa a V-a lecția 26 - 15 feb 2020"

From Algopedia
Jump to navigationJump to search
(Created page with "= Tema - rezolvări = == Problema cfdist == Problema [http://varena.ro/problema/cfdist cfdist] cere de fapt să se calculeze numărul de cifre distincte ale unui număr. El se...")
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
= Anunțuri generale =
 +
 +
== Cantonament de pregătire ==
 +
Mai sunt doar 3 săptămâni până la olimpiada de informatică, faza județeană. Din acest motiv, intrăm în ''cantonament''. Ce înseamnă asta? Vom aveam mai multe teste, mai multe teme și mai mult de lucru în general.
 +
 +
* De acum înainte, vom avea o temă mai mare și, pe lângă tema obligatorie, vom avea o temă opțională. Cu cât faceți mai mult acasă, cu atât vă creșteți șansele să ajungeți la următoarea etapă a concursului.
 +
 +
* În fiecare zi de duminică, între orele 11:00 - 13:00 veți avea un concurs cu penalizare.
 +
 +
* Cursurile vor dura 3 ore și vor începe de la ora 12:00. În ultima oră de curs, veți da un concurs cu penalizare în sală, alături de mine. Cursurile vor aborda mai multă materie, să ne asigurăm că acoperim tot ce ne trebuie pentru a face față etapei curente.
 +
 +
Astfel, programul pentru următoarele săptămâni va fi următorul:
 +
* Duminică, 16 februarie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă
 +
* Sâmbătă, 22 februarie 2020, 12:00 - 15:00 - Curs + concurs în sală (1 oră), stil olimpiadă
 +
* Duminică, 23 februarie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă
 +
* Sâmbătă, 29 februarie 2020, 12:00 - 15:00 - Curs + concurs în sală (1 oră), stil olimpiadă
 +
* Duminică, 1 martie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă
 +
 +
== Reguli noi pentru concursuri ==
 +
Observ că nu tratați concursurile cu seriozitate. Încercați să pescuiți scorul prin a trimite mai întâi problema la arhivă. Vă simplific regulile: cine mai trimite la arhivă problemele din concurs, în timpul concursurilor sau temelor, '''cartonaș roșu cu eliminare, fără drept de contestare.'''
 +
 +
Scopul temelor, concursurilor este să simulăm situația reală de concurs și să vedem unde suntem capabili, pregătiți și unde trebuie să mai lucrăm. Pe mine nu mă interesează punctajul vostru, dacă acesta nu este veridic.
 +
 
= Tema - rezolvări =
 
= Tema - rezolvări =
 
== Problema cfdist ==
 
== Problema cfdist ==
Line 106: Line 129:
 
}</syntaxhighlight>
 
}</syntaxhighlight>
  
= Tema - rezolvări =
+
= Concurs - rezolvări =
 
== Problema culori ==
 
== Problema culori ==
 
Problema [http://varena.ro/problema/culori culori] cere să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordine crescătoare.
 
Problema [http://varena.ro/problema/culori culori] cere să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordine crescătoare.
Line 183: Line 206:
 
   return 0;
 
   return 0;
 
}</syntaxhighlight>
 
}</syntaxhighlight>
 +
= Lecție =
 +
 +
== Tipuri de numere întregi ==
 +
Precum ştim, calculatorul reprezintă toate valorile, fie ele numere sau caractere, ca biţi, sau valori zero şi unu. Vom explora mai jos cîteva din tipurile simple de date, fără pretenţia de a trata exhaustiv subiectul. Pentru simplitate vom discuta despre un tip concret de calculator, şi anume cel pe care lucrăm zi de zi: sistem de operare Windows, compilator gcc pe 32 biți în mediul de programare CodeBlocks.
 +
 +
=== Tipul char ===
 +
Este cel mai mic întreg. El ocupă 8 biţi, numiţi şi un octet (un octet are opt biţi). Care este intervalul de numere care se pot reprezenta pe 8 cifre binare? El este de la 0 la 2<sup>8</sup>-1, adică 0..255, cu totul 256 de valori. Dar deoarece avem şi numere negative intervalul se translatează cu 128, ceea ce înseamnă că un <tt>char</tt> este un număr întreg din intervalul -128..127.
 +
 +
În acelaşi timp ştim că el este un tip dual, poate fi văzut atît ca întreg pe 8 biţi cît şi ca caracter. Dacă vrem să îl tipărim vom folosi <tt>%d</tt> dacă vrem să afişăm valoarea lui întreagă, respectiv <tt>%c</tt> pentru caracter (dar modul preferat de tipărire este cu <tt>fputc</tt>).
 +
 +
=== Tipul int ===
 +
Tipul întreg cu care sîntem obișnuiți. El ocupă 32 de biţi, sau 4 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 2<sup>32</sup>-1, adică între 0 şi ceva mai mult de patru miliarde, dar pentru că avem şi numere negative intervalul devine -2 miliarde..2 miliarde. Pentru a-l citi sau tipări vom folosi descriptorul <tt>%d</tt>.
 +
 +
=== Tipul long long ===
 +
Este dublu faţă de tipul <tt>int</tt>. El ocupă 64 de biţi, sau 8 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 2<sup>64</sup>-1, dar pentru că avem şi numere negative intervalul devine -2<sup>63</sup>..2<sup>63</sup>-1. Dacă aproximăm 2<sup>10</sup> cu 10<sup>3</sup> aceasta înseamnă cu aproximaţie 8 cu 18 zero după el. Pentru a-l citi sau tipări vom folosi descriptorul <tt>%lld</tt>.
 +
 +
'''Atenție'''! Windows nu respectă standardul C! De aceea, dacă folosiți Code::Blocks în Windows va trebui să folosiți <tt>%I64d</tt> în loc de <tt>%lld</tt>. Deoarece varena.ro folosește GNU/Linux voi va trebui să schimbați <tt>%I64d</tt> în <tt>%lld</tt>, atunci cînd trimiteți un program spre evaluare.
 +
 +
'''Atenție'''! La olimpiadă veți lucra în Windows, deci veți folosi <tt>%I64d</tt>, nefiind nevoie să schimbați nimic în program.
 +
 +
== Depăşire ==
 +
Ce se întîmplă atunci cînd depăşim valoarea maximă a unui întreg? Vom învăţa pe un exemplu. Ce va afişa programul următor?
 +
 +
<syntaxhighlight>char c;
 +
c = 127; // valoarea maxima a unui caracter
 +
c++;
 +
printf( "%d", c )</syntaxhighlight>
 +
 +
Răspunsul este <tt>-128</tt>! Pentru a înţelege de ce vom face următoarea observaţie: valorile unui întreg sînt circulare. Ce înseamnă aceasta? Că după cea mai mare valoare posibilă urmează, în cerc, cea mai mică valoare posibilă. Cu alte cuvinte după <tt>127</tt> urmează <tt>-128</tt>. Nu voi explica de ce se întîmplă acest lucru, dar voi menţiona că este mulţumită reprezentării numerelor întregi în calculator în complement faţă de 2. În mod similar, dacă vom scădea unu dintr-un caracter care conţine valoarea <tt>-128</tt> vom obţine valoarea <tt>127</tt>.
 +
 +
Acelaşi lucru se întîmplă şi pe întregi (<tt>int</tt>). Dacă în calculele noastre vom depăşi cea mai mare valoare reprezentabilă, aproximativ două miliarde, vom obţine valori negative. În concluzie trebuie să fim foarte atenţi la depăşiri, deoarece calculatorul nu va da nici o eroare, ci pur şi simplu o va lua de la capăt. Vom obţine valori aberante şi programul nostru va afişa numere ciudate.
 +
 +
Cum ne ferim de depăşiri? Folosind tipul întreg potrivit cu valorile maxime de care avem nevoie în program. Calculăm aceste valori din limitele impuse în problemă. Dar de ce nu putem să folosim întotdeauna cel mai mare întreg, tipul <tt>long long</tt>? Din mai multe motive:
 +
 +
* Lipsă de memorie: un vector de <tt>long long</tt> ocupă dublu faţă de un vector de <tt>int</tt> şi de opt ori mai mult faţă de un vector de <tt>char</tt>! S-ar putea să nu ne ajungă memoria! Multe probleme dau memorie la limită exact în ideea ca voi să vă calculaţi cît mai bine necesarul.
 +
* Risipă: în viaţă este bine să fim economi (în ciuda a ceea ce ne învaţă consumerismul aşa zisei economii de piaţă). De ce să folosim mai multă memorie decît este nevoie? Nu toate programele se execută pe un calculator, care are multă memorie. Multe programe se execută pe circuite izolate, gen cipuri electronice din încărcătorul de mobil, sau în prăjitorul de pîine. Acele sisteme nu au multă memorie la dispoziţie.
 +
* Timp: operaţiile cu <tt>long long</tt> sînt mai lente decît cele cu <tt>int</tt>. De asemenea, din cauza unui mecanism care se numeşte ''cache'', dacă ocupăm mai multă memorie programul se încetineşte.
 +
 +
== Conversii ==
 +
Atunci cînd atribuim o valoare de tip <tt>char</tt> unei variabile de tip <tt>int</tt> programul face automat o conversie de la 8 biţi la 32 biţi. La fel, dacă atribuim o valoare de tip <tt>int</tt> unei variabile de tip <tt>char</tt> programul compilat va face o conversie de la 32 de biti la 8 biți.
 +
 +
=== Conversie de întregi de la mic la mare ===
 +
În acest caz totul funcţionează aşa cum ne-am aştepta, deoarece orice valoare mică este inclusă în intervalul de valori mai mari. Nu vom avea nici o problemă să atribuim o variabilă de tip <tt>char</tt> uneia de tip <tt>int</tt>, sau o variabilă de tip <tt>int</tt> uneia de tip <tt>long long</tt>.
 +
 +
=== Conversie de întregi de la mare la mic ===
 +
În acest caz există posibilitatea de depăşire. Drept pentru care este normal ca şi conversia să urmeze regulile depăşirilor. Ne putem închipui că la valoarea mare putem ajunge pornind de la ultima valoarea mică şi adunînd unu. Exemplu: ce valoare va afişa programul următor?
 +
 +
<syntaxhighlight>char c;
 +
int i;
 +
i = 128;
 +
c = i;
 +
printf( "%d", c );</syntaxhighlight>
 +
 +
Valoarea afişată va fi <tt>-128</tt>, deoarece <tt>128 = 127 + 1</tt><nowiki>; </nowiki><tt>127</tt> fiind cea mai mare valoare caracter, următoarea valoare va fi <tt>-128</tt>. Din acelaşi motiv <tt>129</tt> se va converti la <tt>-127</tt>, <tt>130</tt> la <tt>-126</tt>... <tt>383</tt> la <tt>127</tt> şi <tt>384</tt> din nou la <tt>-128</tt>.
 +
 +
=== Tipul unei expresii ===
 +
 +
Dacă o expresie conține valori "amestecate", adică și de tip <tt>int</tt> și de tip <tt>long long</tt>, de ce tip va fi rezultatul calculat?
 +
 +
'''Regulă''': '''fiecare operator va opera cu valoarea cea mai mare a operanzilor săi'''.
 +
 +
Ce înseamnă acest lucru? Fiecare operație aritmetică, fie ea adunare, scădere, înmulțire, etc, se va uita la cele două numere pe care le adună, sau scade, etc. Dacă unul este de tip <tt>int</tt>, iar al doilea de tip <tt>long long</tt>, atunci operația se va efectua pe tipul <tt>long long</tt>, deoarece este mai mare. Variabila de tip <tt>int</tt> va fi convertită la tipul <tt>long long</tt>.
 +
 +
==== Exemplul 1 ====
 +
 +
<syntaxhighlight>int a;
 +
long long x, y;
 +
a = 100000000; // o suta de milioane
 +
x = 200000000; // doua sute de milioane
 +
y = a * x;    // calculul se va face pe long long, convertind variabila 'a' la long long
 +
printf( "%lld", y );</syntaxhighlight>
 +
 +
Programul va afișa produsul, adică 2 cu 16 zerouri.
 +
 +
'''Atenție''': depășirile sînt rele (în general). Cum ne asigurăm că nu vom avea o situație de depășire? Asigurîndu-ne că valoarea atribuită nu depășește valoarea maximă posibilă a variabilei în care atribuim.
 +
 +
==== Exemplul 2 ====
 +
 +
<syntaxhighlight>int a;
 +
long long x;
 +
a = 200000000; // doua sute de milioane
 +
x = a * a;
 +
printf( "%lld", x );</syntaxhighlight>
 +
 +
Ce va afișa programul de mai sus? Ne-am aștepta să obținem răspunsul <tt>40000000000000000</tt>, adică 4 urmat de 16 zerouri, nu? Ei bine, programul afișează <tt>-1090256896</tt>! De ce oare? Evident programul a generat o depășire de numere întregi, dar de ce? Doar am atribuit rezultatul înmulțirii unei variabile de tip <tt>long long</tt>, nu-i așa?
 +
 +
La momentul cînd se face calculul expresiei, valoarea de după egalul atribuirii, programul nu știe că urmează să atribuie rezultatul unei variabile de tip <tt>long long</tt>. El va aplica regula tipului unei expresii. Va observa că valorile înmulțite sînt de tip <tt>int</tt> și va face calculul pe <tt>int</tt>. De aceea apare depășirea. Valoarea depășită, incorectă, va fi cea care va fi atribuită variabilei <tt>x</tt>.
 +
 +
Cum scriem corect această secvență de program? Dacă înmulțirea conține măcar o valoare de tip <tt>long long</tt> ea se va evalua corect. Putem, deci, fie să declarăm variabila <tt>a</tt> ca <tt>long long</tt>, fie, mai elegant, să ne folosim chiar de variabila <tt>x</tt>, astfel:
 +
 +
<syntaxhighlight>int a;
 +
long long x;
 +
a = 200000000; // doua sute de milioane
 +
x = a;
 +
x = x * x;
 +
printf( "%lld", x );</syntaxhighlight>
 +
 +
== Tabel de descriptori citire/scriere ==
 +
Să recapitulăm care sînt descriptorii de citire/scriere folosiți de <tt>scanf()</tt> și <tt>printf()</tt> pentru fiecare din tipurile învățate mai sus.
 +
 +
{| class="wikitable"
 +
!Tip variabilă
 +
!Valori limită
 +
!Format folosit (litere)
 +
|-
 +
| <tt>char</tt>
 +
| style="text-align:right;" | <tt>-128</tt>&nbsp;...&nbsp;<tt>+127</tt>
 +
| <tt>'''%d'''</tt> dacă vrem să afișăm numărul întreg<br/><tt>'''%c'''</tt> dacă vrem să afișăm caracterul
 +
|-
 +
| <tt>int</tt>
 +
| style="text-align:right;" | <tt>-2147483648</tt>&nbsp;...&nbsp;<tt>2147483647</tt><br/>aproximativ '''două milarde''' (2 cu nouă zerouri)
 +
| <tt>'''%d'''</tt>
 +
|-
 +
| <tt>long long</tt>
 +
| style="text-align:right;" | <tt>-9223372036854775808</tt>&nbsp;...&nbsp;<tt>9223372036854775807</tt><br/>aproximativ '''9&middot;10<sup>18</sup>''' (9 cu 18 zerouri)
 +
| <tt>'''%lld'''</tt> în GNU/Linux și varena.ro<br/><tt>'''%I64d'''</tt> în Windows
 +
|}
 +
 +
== Probleme clasice cu vectori ==
 +
=== Căutare în vector ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente și un extra element <tt>e</tt>. Să se găsească poziția <tt>p</tt> în <tt>v</tt> unde apare prima oară elementul <tt>e</tt>. Dacă elementul <tt>e</tt> nu apare <tt>p</tt> va avea valoarea <tt>n</tt>. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente si o valoare e de gasit in acest vector
 +
p = 0;
 +
while ( p < n && v[p] != e )
 +
  p++;
 +
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v</syntaxhighlight>
 +
 +
=== Inserare în vector ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente, un extra element <tt>e</tt> și o poziție <tt>p</tt>. Să se insereze elementul e la poziția <tt>p</tt>. În final elementul <tt>e</tt> va fi pe poziția <tt>p</tt> în vector, iar elementele de la poziția <tt>p</tt> pînă la final vor fi deplasate spre final cu o poziție. Vom considera că p este o poziție validă, între 0 și n.
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente si o valoare e de inserat la poziția p
 +
for ( i = n - 1; i >= p; i-- ) // deplasăm elementele spre dreapta
 +
  v[i+1] = v[i];
 +
v[p] = e;
 +
n++; // vectorul are acum n+1 elemente!</syntaxhighlight>
 +
 +
=== Ștergere din vector ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente și o poziție <tt>p</tt>. Să se elimine elementul de la poziția <tt>p</tt> din vector. Elementele de la poziția <tt>p</tt> pînă la final se vor deplasa către începutul vectorului cu o poziție.
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
 +
for ( i = p + 1; i < n; i++ ) // deplasam elementele spre stinga
 +
  v[i-1] = v[i];
 +
n--; // vectorul are acum n-1 elemente!</syntaxhighlight>
 +
 +
=== Răsturnare vector ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente. Inversați poziția elementelor în vector. Avem mai multe soluții posibile, una foarte simplă este să folosim doi indici, unul care crește și unul care descrește. Vom interschimba elementele celor doi indici. Vom repeta acest lucru pînă ce indicii se întîlnesc.
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente, vrem sa il rasturnam
 +
i = 0;
 +
j = n – 1;
 +
while ( i < j ) {
 +
  aux = v[i];
 +
  v[i] = v[j];
 +
  v[j] = aux;
 +
  i++;
 +
  j--;
 +
}</syntaxhighlight>
 +
 +
=== Rotire vector ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu <tt><nowiki>[1, 6, 2, 7, 4, 3, 2]</nowiki></tt> se va transforma în <tt><nowiki>[6, 2, 7, 4, 3, 2, 1]</nowiki></tt>.
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
 +
aux = v[0];
 +
for ( i = 1; i < n; i++ )
 +
  v[i-1] = v[i];
 +
v[n-1] = aux;</syntaxhighlight>
 +
 +
=== Mutare zerouri la coadă ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente. Să se modifice ordinea elementelor în vector astfel încît toate elementele zero să fie la coada vectorului. Celelalte elemente nu trebuie să își păstreze ordinea originală (pot fi în orice ordine). O soluție posibilă este să mergem cu doi indici, unul crescător și unul descrescător. Cel crescător avansează pînă ce găsește un zero. Apoi interschimbă cu celălalt indice, pe care îl scade.
 +
 +
<syntaxhighlight>// avem vectorul v de n elemente, vrem sa mutăm zerourile la coada
 +
i = 0;
 +
j = n – 1;
 +
while ( i < j ) {
 +
  if ( v[i] == 0 ) { // daca avem un zero pe pozitia i
 +
    v[i] = v[j];    // il trecem la coada, interschimbind cu pozitia j
 +
    v[j] = 0;
 +
    j--;            // deoarece pe pozitia j avem un zero, putem sa scadem j
 +
  } else
 +
    i++;            // daca avem nonzero pe pozitia i putem avansa i
 +
}</syntaxhighlight>
 +
 +
=== Comparație vectori ===
 +
Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.
 +
 +
Rămîne ca temă.
 +
 +
=== Rotire multiplă de vector * ===
 +
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente și un număr <tt>k</tt>. Să se rotească vectorul cu o poziție către început cu <tt>k</tt> poziții. De exemplu, pentru <tt>k=3</tt> <tt><nowiki>[1, 6, 2, 7, 4, 3, 2]</nowiki></tt> se va transforma în <tt><nowiki>[7, 4, 3, 2, 1, 6, 2]</nowiki></tt>.
 +
 +
Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.
 +
 +
= Temă =
 +
Atenţie: rezolvaţi problemele următoare '''folosind vectori de frecvenţă'''! Acesta este scopul temei.
 +
 +
[http://varena.ro/runda/2018-01-25-clasa-5-tema-22 Tema 26]: să se rezolve următoarele probleme (program C  trimis la vianuarena):
 +
 +
* [http://varena.ro/problema/minnr Minnr]
 +
* [http://varena.ro/problema/cifre3 Cifre 3]
 +
* [http://varena.ro/problema/compus compus] problemă de exersat operațiile clasice pe vectori
 +
* [http://varena.ro/problema/felinare felinare] dată la ONI 2008 clasa a 5<sup>a</sup>
 +
* [http://varena.ro/problema/culori1 culori 1] dată la ONI 2012 clasa a 5<sup>a</sup>
 +
 +
'''Opțional''':
 +
[http://varena.ro/runda/2018-01-25-clasa-5-tema-22 Temă opțională 26]: să se rezolve următoarele probleme (program C  trimis la vianuarena):
 +
 +
* [http://varena.ro/problema/cfcomune Cifre comune]
 +
* [http://varena.ro/problema/minnrk Minnrk]
 +
* '''Grea''': [http://varena.ro/problema/rotk rotk] (rotație multiplă vector fără a face rotații repetate cu unu).
 +
 +
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_26_-_15_feb_2020]

Revision as of 10:21, 14 February 2020

Anunțuri generale

Cantonament de pregătire

Mai sunt doar 3 săptămâni până la olimpiada de informatică, faza județeană. Din acest motiv, intrăm în cantonament. Ce înseamnă asta? Vom aveam mai multe teste, mai multe teme și mai mult de lucru în general.

  • De acum înainte, vom avea o temă mai mare și, pe lângă tema obligatorie, vom avea o temă opțională. Cu cât faceți mai mult acasă, cu atât vă creșteți șansele să ajungeți la următoarea etapă a concursului.
  • În fiecare zi de duminică, între orele 11:00 - 13:00 veți avea un concurs cu penalizare.
  • Cursurile vor dura 3 ore și vor începe de la ora 12:00. În ultima oră de curs, veți da un concurs cu penalizare în sală, alături de mine. Cursurile vor aborda mai multă materie, să ne asigurăm că acoperim tot ce ne trebuie pentru a face față etapei curente.

Astfel, programul pentru următoarele săptămâni va fi următorul:

  • Duminică, 16 februarie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă
  • Sâmbătă, 22 februarie 2020, 12:00 - 15:00 - Curs + concurs în sală (1 oră), stil olimpiadă
  • Duminică, 23 februarie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă
  • Sâmbătă, 29 februarie 2020, 12:00 - 15:00 - Curs + concurs în sală (1 oră), stil olimpiadă
  • Duminică, 1 martie 2020, 11:00 - 13:00 - Concurs de acasă, stil olimpiadă

Reguli noi pentru concursuri

Observ că nu tratați concursurile cu seriozitate. Încercați să pescuiți scorul prin a trimite mai întâi problema la arhivă. Vă simplific regulile: cine mai trimite la arhivă problemele din concurs, în timpul concursurilor sau temelor, cartonaș roșu cu eliminare, fără drept de contestare.

Scopul temelor, concursurilor este să simulăm situația reală de concurs și să vedem unde suntem capabili, pregătiți și unde trebuie să mai lucrăm. Pe mine nu mă interesează punctajul vostru, dacă acesta nu este veridic.

Tema - rezolvări

Problema cfdist

Problema cfdist cere de fapt să se calculeze numărul de cifre distincte ale unui număr. El se poate calcula ușor astfel: extragem în mod repetat ultima cifră c a numărului, avînd grijă să setăm vectorul de frecvență pe 1 la poziția c. În final parcurgem elementele vectorului de frecvență și numărăm cîte elemente 1 avem. Iată o soluție posibilă:

#include <stdio.h>

int v[10];

int main() {
  FILE *fin, *fout;
  int n, cf, nrcf;

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

  while ( n > 0 ) {
    v[n % 10] = 1;
    n /= 10;
  }

  nrcf = 0;
  for ( cf = 0; cf < 10; cf++ )
    nrcf += v[cf];

  fout = fopen( "cfdist.out", "w" );
  fprintf( fout, "%d", nrcf );
  fclose( fout );

  return 0;
}

De remarcat că nu avem nevoie de numărul de apariții al cifrelor, de aceea stocăm unu, ori de cîte ori apare o cifră. Aceasta ne permite ca la final să calculăm suma elementelor vectorului de frecvență, fără a mai testa dacă valorile sînt zero.

Problema maxnr

Problema maxnr cere să se afişeze cel mai mare număr care se poate forma cu cifrele unui număr. Prima parte a rezolvării problemei este foarte similară cu problema anterioară (cfdist): vom construi vectorul de frecvență al cifrelor numărului, de data asta adunînd 1 pentru fiecate cifră. Apoi vom parcurge vectorul în sens invers, afișînd poziția curentă i de cîte ori ne spune elementul v[i]. Iată o rezolvare posibilă:

#include <stdio.h>

int v[10];

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

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

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

  fout = fopen( "maxnr.out", "w" );
  for ( cf = 9; cf >= 0; cf-- )
    while ( v[cf] > 0 ) {
      fprintf( fout, "%d", cf );
      v[cf]--;
    }
  fclose( fout );

  return 0;
}

Problema plus

Problema plus poate părea la prima vedere o problema care se rezolvă cu vectori: fiecare cifră o așezăm în vectori și apoi facem operațiile aferente. Nu este o rezolvare rea, dar se poate rezolva foarte simplu prin manipularea cifrelor numărului. Scopul problemei era să vă determin să faceți diferența când trebuie să folosim sau nu vectori.

Iată o posibilă rezolvare:

#include <stdio.h>
int main()
{
    FILE *fin = fopen ( "plus.in", "r" );
    FILE *fout = fopen ( "plus.out", "w" );
    int  numar, masca, invers;
    fscanf( fin , "%d" , &numar );
    masca = 0; 
    inv = 0;

    // primul pas reprezintă răsturnarea numărului; 
    // în acest proces, avem grijă să adăugăm deja +1 
    while( numar ) { //adica cat timp există
        masca = masca * 10 + 1;
        invers = invers * 10 + numar % 10 ;
        numar = numar / 10;
    }

    fprintf( fout, "%d\n" , invers % 10 ); //afișăm prima cifră a numărului
    numar = masca + invers;
    invers = 0;

    // al doilea pas este să răsturnăm iarăși numărul;
    // astfel, îl aducem în forma corectă pentru afișare
    while( numar ) {
        invers = invers * 10 + numar % 10;
        numar = numar / 10;
    }

    fprintf( fout, "%d\n" , invers );
    fclose( fin );
    fclose ( fout );

    return 0;
}

Concurs - rezolvări

Problema culori

Problema culori cere să se afișeze o secvență de culori codificate cu numere mai mici ca 100 în ordine crescătoare.

Atenție la următoarele greșeli uzuale:

  • Vectorul de culori declarat ca int v[99]. Greșit, vectorul are 100 de elemente, iar ultimul element este v[99]. Vectorul trebuie declarat ca int v[100], altfel vom depăși vectorul atunci cînd apelăm v[99], deoarece acest element ar fi în afara vectorului.
  • Parcurgerea vectorului de la 1 la 100, inclusiv 100 la afișarea culorilor. Greșit, ultima culoare posibilă este 99.

Problema culori ne învață să ordonăm numere naturale, atunci cînd numerele naturale nu sînt foarte mari. În cazul nostru avem de ordonat culori, care sînt numere între 1 și 99. Pentru aceasta vom folosi un vector de frecvență de 100 de elemente. Să nu uităm că elementele vor fi numerotate de la 1 la 99. Pe măsură ce citim culorile adunăm unu la poziția acelei culori în vectorul de frecvență. Observație: nu avem nevoie să păstrăm culorile în alt vector! Odată calculat vectorul de frecvență îl vom parcurge de la 1 la 99 afișînd indicele i de cîte ori ne arată elementul v[i].

Această ordonare (sau sortare) se mai numește și sortare prin numărare (counting sort). Iată o soluție bazată pe această idee:

#include <stdio.h>

int v[100];

int main() {
  FILE *fin, *fout;
  int n, i, culoare;

  fin = fopen( "culori.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &culoare );
    v[culoare]++;
  }
  fclose( fin );

  fout = fopen( "culori.out", "w" );
  for ( cul = 1; cul < 100; culoare++ )
    while ( v[culoare] > 0 ) {
      fprintf( fout, "%d ", culoare );
      v[culoare]--;
    }
  fclose( fout );

  return 0;
}

Problema tastatura 1

Problema tastatura 1 este un exerciţiu de lucru cu caractere şi compunerea valorilor unor numere întregi pornind de la caracterele cifre ce le constituie. Am mai întîlnit aceste două elemente în problema fgetc.

Pentru rezolvare vom citi caracterele de la intrare pînă la final de linie, '\n', ignorînd caracterele '#'. Vom adăuga caracterele cifră la coada unui număr n, întocmai ca la problema fgetc. Cînd întîlnim un caracter '+' vom adăuga numărul n la sumă. Mare atenție la un caz particular: ultimul număr nu va avea un caracter '+' după el, deci va trebui adăugat special la sumă.

Iată o soluție posibilă:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  char c;
  int numar, suma;
  
  fin = fopen( "tastatura1.in", "r" );
  c = fgetc( fin );
  suma = 0;
  numar = 0;
  while ( c != '\n' ) { // citim pina la final de linie
    if ( c != '#' ) {   // caracterele # se ignora
      if ( c == '+' ) { // s-a incheiat numarul, il adunam la suma
        suma = suma + numar;
        numar = 0;
      } else            // altfel este o cifra deghizata in litera mare
        numar = numar * 10 + c - 'A';
    }
    c = fgetc( fin );
  }
  suma = suma + numar; // ultimul numar nu are plus dupa el, deci il adunam separat
  fclose( fin );

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

  return 0;
}

Lecție

Tipuri de numere întregi

Precum ştim, calculatorul reprezintă toate valorile, fie ele numere sau caractere, ca biţi, sau valori zero şi unu. Vom explora mai jos cîteva din tipurile simple de date, fără pretenţia de a trata exhaustiv subiectul. Pentru simplitate vom discuta despre un tip concret de calculator, şi anume cel pe care lucrăm zi de zi: sistem de operare Windows, compilator gcc pe 32 biți în mediul de programare CodeBlocks.

Tipul char

Este cel mai mic întreg. El ocupă 8 biţi, numiţi şi un octet (un octet are opt biţi). Care este intervalul de numere care se pot reprezenta pe 8 cifre binare? El este de la 0 la 28-1, adică 0..255, cu totul 256 de valori. Dar deoarece avem şi numere negative intervalul se translatează cu 128, ceea ce înseamnă că un char este un număr întreg din intervalul -128..127.

În acelaşi timp ştim că el este un tip dual, poate fi văzut atît ca întreg pe 8 biţi cît şi ca caracter. Dacă vrem să îl tipărim vom folosi %d dacă vrem să afişăm valoarea lui întreagă, respectiv %c pentru caracter (dar modul preferat de tipărire este cu fputc).

Tipul int

Tipul întreg cu care sîntem obișnuiți. El ocupă 32 de biţi, sau 4 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 232-1, adică între 0 şi ceva mai mult de patru miliarde, dar pentru că avem şi numere negative intervalul devine -2 miliarde..2 miliarde. Pentru a-l citi sau tipări vom folosi descriptorul %d.

Tipul long long

Este dublu faţă de tipul int. El ocupă 64 de biţi, sau 8 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 264-1, dar pentru că avem şi numere negative intervalul devine -263..263-1. Dacă aproximăm 210 cu 103 aceasta înseamnă cu aproximaţie 8 cu 18 zero după el. Pentru a-l citi sau tipări vom folosi descriptorul %lld.

Atenție! Windows nu respectă standardul C! De aceea, dacă folosiți Code::Blocks în Windows va trebui să folosiți %I64d în loc de %lld. Deoarece varena.ro folosește GNU/Linux voi va trebui să schimbați %I64d în %lld, atunci cînd trimiteți un program spre evaluare.

Atenție! La olimpiadă veți lucra în Windows, deci veți folosi %I64d, nefiind nevoie să schimbați nimic în program.

Depăşire

Ce se întîmplă atunci cînd depăşim valoarea maximă a unui întreg? Vom învăţa pe un exemplu. Ce va afişa programul următor?

char c;
c = 127; // valoarea maxima a unui caracter
c++;
printf( "%d", c )

Răspunsul este -128! Pentru a înţelege de ce vom face următoarea observaţie: valorile unui întreg sînt circulare. Ce înseamnă aceasta? Că după cea mai mare valoare posibilă urmează, în cerc, cea mai mică valoare posibilă. Cu alte cuvinte după 127 urmează -128. Nu voi explica de ce se întîmplă acest lucru, dar voi menţiona că este mulţumită reprezentării numerelor întregi în calculator în complement faţă de 2. În mod similar, dacă vom scădea unu dintr-un caracter care conţine valoarea -128 vom obţine valoarea 127.

Acelaşi lucru se întîmplă şi pe întregi (int). Dacă în calculele noastre vom depăşi cea mai mare valoare reprezentabilă, aproximativ două miliarde, vom obţine valori negative. În concluzie trebuie să fim foarte atenţi la depăşiri, deoarece calculatorul nu va da nici o eroare, ci pur şi simplu o va lua de la capăt. Vom obţine valori aberante şi programul nostru va afişa numere ciudate.

Cum ne ferim de depăşiri? Folosind tipul întreg potrivit cu valorile maxime de care avem nevoie în program. Calculăm aceste valori din limitele impuse în problemă. Dar de ce nu putem să folosim întotdeauna cel mai mare întreg, tipul long long? Din mai multe motive:

  • Lipsă de memorie: un vector de long long ocupă dublu faţă de un vector de int şi de opt ori mai mult faţă de un vector de char! S-ar putea să nu ne ajungă memoria! Multe probleme dau memorie la limită exact în ideea ca voi să vă calculaţi cît mai bine necesarul.
  • Risipă: în viaţă este bine să fim economi (în ciuda a ceea ce ne învaţă consumerismul aşa zisei economii de piaţă). De ce să folosim mai multă memorie decît este nevoie? Nu toate programele se execută pe un calculator, care are multă memorie. Multe programe se execută pe circuite izolate, gen cipuri electronice din încărcătorul de mobil, sau în prăjitorul de pîine. Acele sisteme nu au multă memorie la dispoziţie.
  • Timp: operaţiile cu long long sînt mai lente decît cele cu int. De asemenea, din cauza unui mecanism care se numeşte cache, dacă ocupăm mai multă memorie programul se încetineşte.

Conversii

Atunci cînd atribuim o valoare de tip char unei variabile de tip int programul face automat o conversie de la 8 biţi la 32 biţi. La fel, dacă atribuim o valoare de tip int unei variabile de tip char programul compilat va face o conversie de la 32 de biti la 8 biți.

Conversie de întregi de la mic la mare

În acest caz totul funcţionează aşa cum ne-am aştepta, deoarece orice valoare mică este inclusă în intervalul de valori mai mari. Nu vom avea nici o problemă să atribuim o variabilă de tip char uneia de tip int, sau o variabilă de tip int uneia de tip long long.

Conversie de întregi de la mare la mic

În acest caz există posibilitatea de depăşire. Drept pentru care este normal ca şi conversia să urmeze regulile depăşirilor. Ne putem închipui că la valoarea mare putem ajunge pornind de la ultima valoarea mică şi adunînd unu. Exemplu: ce valoare va afişa programul următor?

char c;
int i;
i = 128;
c = i;
printf( "%d", c );

Valoarea afişată va fi -128, deoarece 128 = 127 + 1; 127 fiind cea mai mare valoare caracter, următoarea valoare va fi -128. Din acelaşi motiv 129 se va converti la -127, 130 la -126... 383 la 127 şi 384 din nou la -128.

Tipul unei expresii

Dacă o expresie conține valori "amestecate", adică și de tip int și de tip long long, de ce tip va fi rezultatul calculat?

Regulă: fiecare operator va opera cu valoarea cea mai mare a operanzilor săi.

Ce înseamnă acest lucru? Fiecare operație aritmetică, fie ea adunare, scădere, înmulțire, etc, se va uita la cele două numere pe care le adună, sau scade, etc. Dacă unul este de tip int, iar al doilea de tip long long, atunci operația se va efectua pe tipul long long, deoarece este mai mare. Variabila de tip int va fi convertită la tipul long long.

Exemplul 1

int a;
long long x, y;
a = 100000000; // o suta de milioane
x = 200000000; // doua sute de milioane
y = a * x;     // calculul se va face pe long long, convertind variabila 'a' la long long
printf( "%lld", y );

Programul va afișa produsul, adică 2 cu 16 zerouri.

Atenție: depășirile sînt rele (în general). Cum ne asigurăm că nu vom avea o situație de depășire? Asigurîndu-ne că valoarea atribuită nu depășește valoarea maximă posibilă a variabilei în care atribuim.

Exemplul 2

int a;
long long x;
a = 200000000; // doua sute de milioane
x = a * a;
printf( "%lld", x );

Ce va afișa programul de mai sus? Ne-am aștepta să obținem răspunsul 40000000000000000, adică 4 urmat de 16 zerouri, nu? Ei bine, programul afișează -1090256896! De ce oare? Evident programul a generat o depășire de numere întregi, dar de ce? Doar am atribuit rezultatul înmulțirii unei variabile de tip long long, nu-i așa?

La momentul cînd se face calculul expresiei, valoarea de după egalul atribuirii, programul nu știe că urmează să atribuie rezultatul unei variabile de tip long long. El va aplica regula tipului unei expresii. Va observa că valorile înmulțite sînt de tip int și va face calculul pe int. De aceea apare depășirea. Valoarea depășită, incorectă, va fi cea care va fi atribuită variabilei x.

Cum scriem corect această secvență de program? Dacă înmulțirea conține măcar o valoare de tip long long ea se va evalua corect. Putem, deci, fie să declarăm variabila a ca long long, fie, mai elegant, să ne folosim chiar de variabila x, astfel:

int a;
long long x;
a = 200000000; // doua sute de milioane
x = a;
x = x * x;
printf( "%lld", x );

Tabel de descriptori citire/scriere

Să recapitulăm care sînt descriptorii de citire/scriere folosiți de scanf() și printf() pentru fiecare din tipurile învățate mai sus.

Tip variabilă Valori limită Format folosit (litere)
char -128 ... +127 %d dacă vrem să afișăm numărul întreg
%c dacă vrem să afișăm caracterul
int -2147483648 ... 2147483647
aproximativ două milarde (2 cu nouă zerouri)
%d
long long -9223372036854775808 ... 9223372036854775807
aproximativ 9·1018 (9 cu 18 zerouri)
%lld în GNU/Linux și varena.ro
%I64d în Windows

Probleme clasice cu vectori

Căutare în vector

Se dă un vector v de n elemente și un extra element e. Să se găsească poziția p în v unde apare prima oară elementul e. Dacă elementul e nu apare p va avea valoarea n. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:

// avem vectorul v de n elemente si o valoare e de gasit in acest vector
p = 0;
while ( p < n && v[p] != e )
  p++;
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v

Inserare în vector

Se dă un vector v de n elemente, un extra element e și o poziție p. Să se insereze elementul e la poziția p. În final elementul e va fi pe poziția p în vector, iar elementele de la poziția p pînă la final vor fi deplasate spre final cu o poziție. Vom considera că p este o poziție validă, între 0 și n.

// avem vectorul v de n elemente si o valoare e de inserat la poziția p
for ( i = n - 1; i >= p; i-- ) // deplasăm elementele spre dreapta
  v[i+1] = v[i];
v[p] = e;
n++; // vectorul are acum n+1 elemente!

Ștergere din vector

Se dă un vector v de n elemente și o poziție p. Să se elimine elementul de la poziția p din vector. Elementele de la poziția p pînă la final se vor deplasa către începutul vectorului cu o poziție.

// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
for ( i = p + 1; i < n; i++ ) // deplasam elementele spre stinga
  v[i-1] = v[i];
n--; // vectorul are acum n-1 elemente!

Răsturnare vector

Se dă un vector v de n elemente. Inversați poziția elementelor în vector. Avem mai multe soluții posibile, una foarte simplă este să folosim doi indici, unul care crește și unul care descrește. Vom interschimba elementele celor doi indici. Vom repeta acest lucru pînă ce indicii se întîlnesc.

// avem vectorul v de n elemente, vrem sa il rasturnam
i = 0;
j = n – 1;
while ( i < j ) {
  aux = v[i];
  v[i] = v[j];
  v[j] = aux;
  i++;
  j--;
}

Rotire vector

Se dă un vector v de n elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu [1, 6, 2, 7, 4, 3, 2] se va transforma în [6, 2, 7, 4, 3, 2, 1].

// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
aux = v[0];
for ( i = 1; i < n; i++ )
  v[i-1] = v[i];
v[n-1] = aux;

Mutare zerouri la coadă

Se dă un vector v de n elemente. Să se modifice ordinea elementelor în vector astfel încît toate elementele zero să fie la coada vectorului. Celelalte elemente nu trebuie să își păstreze ordinea originală (pot fi în orice ordine). O soluție posibilă este să mergem cu doi indici, unul crescător și unul descrescător. Cel crescător avansează pînă ce găsește un zero. Apoi interschimbă cu celălalt indice, pe care îl scade.

// avem vectorul v de n elemente, vrem sa mutăm zerourile la coada
i = 0;
j = n – 1;
while ( i < j ) {
  if ( v[i] == 0 ) { // daca avem un zero pe pozitia i
    v[i] = v[j];     // il trecem la coada, interschimbind cu pozitia j
    v[j] = 0;
    j--;             // deoarece pe pozitia j avem un zero, putem sa scadem j
  } else
    i++;             // daca avem nonzero pe pozitia i putem avansa i
}

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Rămîne ca temă.

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.

Temă

Atenţie: rezolvaţi problemele următoare folosind vectori de frecvenţă! Acesta este scopul temei.

Tema 26: să se rezolve următoarele probleme (program C trimis la vianuarena):

Opțional: Temă opțională 26: să se rezolve următoarele probleme (program C trimis la vianuarena):

Rezolvări aici [1]