Clasa a V-a lecția 26 - 25 feb 2014

Probleme date la ultimele două teme - rezolvări

Rezolvări aici [1]

Lecție

Discuție temă

Discuție despre problemele de la temă.

Problema bețe

Problema bete se rezolvă elegant fără vectori. Pentru primul punct, lungimea inițială a bețelor trebuie să facem suma tuturor bețelor, atît ale Anei cît și ale lui Bogdan. Împărțind suma la N vom găsi lungimea inițială. O alternativă observată de unii din voi este să calculăm minimul unuia din copii și maximul celuilalt și să le facem suma. Pentru al doilea punct, aflarea bățului maxim ce se poate forma cu două bețe, avem nevoie de maximele din ambele secvențe. Suma lor este răspunsul. În fine, pentru a calcula numărul de bețe de lungime maximă ce se pot calcula trebuie să ținem cont de următoarele:

• Odată lipite, bețele nu se mai dezlipesc la loc. Ce înseamnă aceasta? Că bețele pe care le formăm sînt eliminate. Bețele pe care le formăm ulterior trebuie să fie din alte fragmente.
• Toate bețele pe care le formăm vor fi formate din maxime ale Anei și maxime ale lui Bogdan. De ce? Gîndiți-vă voi la asta (demonstrație prin reducere la absurd).

Rezultă că vom putea forma un număr de bețe de lungime maximă egal cu minimul dintre bețele maxime ale Anei și bețele maxime ale lui Bogdan. Rezultă că atunci cînd calculăm maximul din secvențe trebuie să calculăm și numărul lui de apariții.

Problema chibrituri

Problema chibrituri poate fi foarte simplă, sau foarte complicată, în funcție de cum o abordați. Să observăm un lucru important: numărul total de ore afișabile pe un ceas electronic este 1440. Acest număr provine din înmulțirea tuturor orelor cu toate minutele, adica 24 * 60. Acest număr este suficient de mic încît să putem să generăm toate orele si minutele posibile și apoi să le testăm dacă corespund cerinței, respectiv dacă numărul total de bețe orizontale și verticale este egal cu cel cerut la intrare.

Rămîne să lămurim cum putem calcula ușor numărul de bețe orizontale și verticale. Cel mai simplu ar fi să avem un vector v si un vector h, de zece elemente fiecare, care să ne spună numerele, astfel: v[i] este numărul de bețe verticale ale cifrei i, iar o[i] este numarul de bețe orizontale. Cum calculăm acești vectori? "De mînă" :) Fiecare element v[i] și o[i] are valoare constantă, care nu se modifică pe parcursul execuției programului. Deci putem să scriem 20 de instrucțiuni de atribuire:

v[0] = 4; // 4 bete verticale in cifra 0
v[1] = 2; // 2 bete verticale in cifra 1
v[2] = 2; // 2 bete verticale in cifra 2
...
v[9] = 3; // 3 bete verticale in cifra 9
o[0] = 2; // 2 bete verticale in cifra 0
o[1] = 0; // nici un bat vertical in cifra 1
...
o[9] = 3; // 3 bete verticale in cifra 9

Ei bine, pentru astfel de situații, limbajul C ne permite să inițializăm vectorii mai simplu, la declararea lor, astfel:

int v[10] = { 4, 2, 2, 2, 3, 2, 3, 2, 4, 3 };
int o[10] = { 2, 0, 3, 3, 1, 3, 3, 1, 3, 3 };

Un ultim aspect este cum facem afișarea. În primul rînd, citind cu atenție enunțul reținem că ora minimă și cea maximă trebuie afișate în formatul ceasului electronic. Nu putem afișa pur și simplu ora, apoi caracterul ':' și apoi minutele, căci atunci cînd ele vor avea doar o cifră, nu se va afișa și cifra zero din față. O soluție ar fi să afișăm cîte o cifră. O altă soluție este să folosim afișarea cu descriptori de formatare. În loc de %d putem spune %2d, ceea ce înseamnă că numărul va fi afișat pe două poziții, completînd la stînga cu spații. Pentru a completa cu zero în loc de spații trebuie să mai punem un zero: %02d.

Precum vedeți această soluție folosește lucruri pe care nu le-am învățat la cerc. Cu toate acestea nici una nu este esențială. Putem rezolva problema și fără aceste lucruri noi.

Temă

Tema 26 clasa a 5^a:

• bețe dată la OJI 2013 clasa a 5^a
• chibrituri dată la OJI 2013 clasa a 5^a

Rezolvări aici [2]