Clasa a V-a lecția 28 - 22 feb 2020

From Algopedia
Revision as of 17:04, 9 February 2021 by Mihai (talk | contribs) (→‎Tema opțională - rezolvări)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Concurs - rezolvări

Rezolvări aici [1]

Tema - rezolvări

Rezolvări aici [2]

Tema opțională - rezolvări

Rezolvări aici [3]

Lecție

<html5media height="720" width="1280">http://algopedia.ro/video/2019-2020/2020-02-22-clasa-5-lectie-info-28-720p.mp4</html5media>

Vectori preinițializați

Să presupunem că vrem să rezolvăm următoarea problemă:

Aprinse

Dispunem de un calculator de buzunar care afișează cifrele în mod clasic, folosind 7 fante luminoase aprinse sau stinse. Astfel, cele zece cifre zecimale se reprezintă astfel:

Cifre afișaj electronic

Se cere ca, dat un număr de maximum 18 cifre la intrare să se afișeze numărul de fante aprinse necesare pentru a afișa acel număr pe ecranul calculatorului de buzunar.

Exemple: numărul 254 are 14 segmente aprinse (5 + 5 + 4), iar numărul 2083 are 23 de segmente (5 + 6 + 7 + 5).

Pentru a rezolva această problemă vom afla pe rînd cifrele numărului, și pentru fiecare cifră în parte vom afla numărul său de segmente, pe care îl vom aduna la o sumă globală (variabilă acumulator). Întrebarea este 'cum calculăm numărul de segmente al unei cifre date'?

Soluție fără vectori

Putem rezolva această problemă fără a folosi vectori. Pentru fiecare cifră vom avea nouă teste if pentru a decide ce număr adunăm:

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  if ( cf == 0 )
    s += 6;
  else if ( cf == 1 )
    s += 2;
  else if ( cf == 2 )
    s += 5;
  ...
  else if ( cf == 8 )
    s += 7;
  else
    s += 6;
}
printf( "%d", s)

Putem scurta puțin această soluție grupînd cifrele după numărul lor de segmente:

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  if ( cf == 0 || cf == 6 || cf == 9 )
    s += 6;
  else if ( cf == 1 )
    s += 2;
  else if ( cf == 2 || cf == 3 || cf == 5 )
    s += 5;
  else if ( cf == 4 )
    s += 4;
  else if ( cf == 7 )
    s += 3;
  else
    s += 7;
}
printf( "%d", s)

Există o soluție mai bună?

Soluție cu vector

Desigur, folosind vectori. Am putea să păstrăm pentru fiecare cifră numărul ei de segmente. Vom păstra aceste numere într-un vector nrseg[10], pe care îl vom inițializa la începutul programului. În acest fel putem afla ușor cîte segmente are o cifră: dacă cifra este cf, atunci numărul său de segmente este nrseg[cf].

Iată un program posibil:

int nrseg[10];
...
nrseg[0] = 6;
nrseg[1] = 2;
nrseg[2] = 5;
nrseg[3] = 5;
nrseg[4] = 4;
nrseg[5] = 5;
nrseg[6] = 6;
nrseg[7] = 3;
nrseg[8] = 7;
nrseg[9] = 6;

s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  s += nrseg[cf];
}
printf( "%d", s)

Precum observați, programul nu este cu mult mai scurt. Dar de data aceasta mare parte din program este inițializarea vectorului nrseg[10], instrucțiunile de atribuire. Calculul în sine ocupă doar șase linii, corpul instrucțiuni while este mult mai mic față de soluțiile anterioare.

Soluție cu vector preinițializat

Pentru astfel de situații, atunci cînd ne dorim să inițializăm un întreg vector cu multiple valori, limbajul C ne ajută să scriem ceva mai puțin. Putem atribui toate cele zece valori într-o singură linie! Această atribuire se face în aceeași linie în care declarăm vectorul. Astfel, în exemplul nostru, vom atribui cele zece valori astfel:

int nrseg[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

Acest tip de declarație poartă denumirea de vector preinițializat. Astfel, programul nostru devine:

int nrseg[10] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
...
s = 0;
while ( n > 0 ) {
  cf = n % 10;
  n /= 10;
  s += nrseg[cf];
}
printf( "%d", s)

Manipularea orelor și minutelor pe ceas

Deși orele și minutele sînt doar numere, anumite exerciții pot pune probleme.

Problemă: se dau doi timpi, t1 și t2, specificați ca ore și minute. Astfel, vom avea la intrare o1, m1 și o2, m2. Cîte ore și minute se află între acești doi timpi? Atenție! Dacă t2 este înaintea lui t1 se consideră că am trecut într-o nouă zi. Exemplu: dacă t1 este 10:35 și t2 este 18:20 atunci vom afișa 07:45. Dacă t1 este 22:25 și t2 este 20:05 vom afișa 21:40.

La prima vedere acest exercițiu pare încîlcit. Va trebui să comparăm cei doi timpi. Dacă t1 este înaintea lui t2 atunci va trebui să comparăm cîte ore avem între o1 și o2. Dar și aceasta va depinde de relația dintre m1 și m2. Dacă t1 este după t2 lucrurile se complică și mai mult: trebuie să aflăm cîte ore și minute avem pîna la finalul zilei, apoi să aflăm cîte ore și minute avem de la începutul zilei pînă la t2, iar în final trebuie să le adunăm. Multe cazuri particulare. Cum facem să simplificăm lucrurile?

Regulă: pentru a nu ne încurca, întotdeauna vom face conversia orelor la cea mai mică unitate de măsură, fie ea minut sau secundă. În final vom face conversia inversă, de la minute, la ore și minute.

În cazul problemei noastre, vom converti t1 și t2 la minute. Algoritmul este următorul:

1. calculează t1 = o1 * 60 + m1
2. calculează t2 = o2 * 60 + m2
3. calculează d = t2 - t1
4. dacă d < 0 atunci
     4.1 calculează d = 24 * 60 - d
5. calculează o3 și t3 pe baza lui d, astfel:
     5.1 o3 = d / 60
     5.2 m3 = d % 60
6. afișează o3 și m3

Concluzie: în problemele în care avem nevoie să lucrăm cu ore, minute și secunde, este foarte important să transformăm timpul într-un singur număr exprimat în cea mai mică unitate de timp implicată. În exemplul de mai sus această unitate este minutul. Uneori s-ar putea să fie secunda. După transformare vom face calculele cerute de problemă. În final vom transforma înapoi în ore, minute, posibil secunde, dacă problema necesită acest lucru.

Sfaturi pentru olimpiadă

Iată cîteva sugestii pentru olimpiadă.

Ce să faceți / ce să nu faceți

Ce să faceți

  • Odihnă: odihniți-vă cu o zi înainte. Relaxați-vă cu activitatea favorită. Mergeți la un film, jucați jocul vostru preferat, etc. Încercați să nu vă gîndiți la concurs.
  • Ceas: aveți un ceas la voi. Nu ceasul calculatorului, al telefonului sau al smartphone-ului. Fiți conștienți de trecerea timpului, nu vă treziți din visare cînd mai este un sfert de oră. Pentru aceasta un ceas așezat pe banca de lucru este ideal. Nu uitați: toate celelalte ceasuri pot fi incorecte, sau să moară.
  • Țineți socoteala timpului: notați ora începerii concursului pe foaie. Verificați la final că ați avut tot timpul promis. Dacă aveți probleme cu calculatorul și cereți ajutorul supraveghetorului notați timpul cînd ați fost întrerupți și apoi timpul cînd reveniți la un calculator funcțional. Aveți dreptul la o prelungire a timpului egală cu timpul pierdut.
  • Cereți-vă drepturile: dacă vă opresc mai devreme decît e cazul, sau dacă ați pierdut zece minute din cauza unui calculator care nu a funcționat și nu vi se dau, cereți respectuos să vi se extindă timpul cu acele minute. Supraveghetorii pot uneori să uite, olimpiada este stresantă și pentru ei. Dacă nu înțelegeți textul unei probleme, după ce l-ați citit cu mare atenție, puneți întrebări pentru clarificare (formulate astfel încît răspunsul să fie 'DA' sau 'NU').
  • Low hanging fruit: rezolvați problema mai ușoară prima. Citiți toate problemele la început și hotărîți-vă care este mai ușoară. Cu ea începeți. Puteți inclusiv să rezolvați subpunctele mai ușoare primele. De exemplu puteți să rezolvați problema 1 punctul a), apoi problema 2 punctul b).
  • Moral ridicat: intrați în sală încrezători în voi. Sînteți printre cei mai buni din țară, aveți puterea să vă clasați printre primii din țară. Propuneți-vă să luați punctaj maxim și reamintiți-vă că puteți acest lucru.
  • Probleme grele: atunci cînd constatați că problemele sînt grele nu vă speriați. Bucurați-vă! Este cea mai bună situație pentru voi. Aveți numai de cîștigat: fie știți să faceți problema, caz în care este perfect, căci problema fiind grea v-ați asigurat că veți fi mai sus ca ceilalți. Fie nu știți să faceți problema și atunci care este șansa ca cei mai slabi ca voi să știe să o facă? Temeți-vă de problemele ușoare, pe care știu toți să le facă. Voi le veți gîndi, ceilalți le vor picta la perfecție.
  • Atenție: fiți foarte atenți la detalii: la numele fișierelor de intrare/ieșire; la numele sub care trebuie să salvați programul C; la setările de proiect CodeBlocks de care am vorbit: -Wall și -O2; la locul unde ați salvat proiectul, și numele proiectului în caz că aveți nevoie să le copiați în altă parte.

Ce să nu faceți

  • Nu îngrășați porcul în ajun: nu faceți probleme în ultima clipă . Vă veți extenua inutil. În urma stresului s-ar putea să nu reușiți să le faceți, ceea ce vă va demoraliza. Aveți nevoie de moral ridicat la concurs.
  • Nu vă panicați: panica ucide creierul. Panica vă face să gîndiți mai încet și să doriți în subconștient să ieșiți din sală. Controlați-o. Nu uitați că o problemă grea, pe care nu știți să o faceți, vă avantajează, pentru că probabil nici ceilalți nu știu, pe cînd voi aveți o șansă să luați puncte pe ea.
  • Nu-i băgați în seamă pe cei ce se dau mari: unii elevi spun cu voce suficient de tare să fie auziți, în timpul concursului, lucruri de genul 'aaah, am făcut-o și pe asta, super' sau 'am rupt, sigur iau suta', etc. Este modul lor inconștient de a vă demoraliza. De obicei ei se clasează slab. Ignorați-i. De asemenea veți vedea că unii dintre concurenți părăsesc sala mai devreme cu o oră cu un aer fericit, eventual spunînd 'sigur mă calific' sau 'am făcut tot, yesss'. Ignorați-i. Și ei se clasează slab. Nu vă demoralizați indiferent cîți elevi ies din sală. Lupta voastră nu este cu ei, ci cu problemele și punctele.
  • Nu ieșiți mai devreme din sală: dacă nu ați terminat problemele continuați să vă gîndiți la o soluție. Dacă ați terminat problemele și vă plictisiți creați mai multe teste pe care să le testați. Nu uitați: nimănui nu-i pasă cît de repede ați ieșit. Nu luați puncte suplimentare pentru asta.
  • Nu modificați în ultima clipă un program care funcționează: riscați să nu aveți timp să-l testați și să luați zero puncte la acea problemă.
  • Nu vă îngrijorați de părerea noastră: noi, instructorii, știm bine care este valoarea voastră. Nu avem nevoie de un rezultat la olimpiadă să aflăm. Nu o să ne vedeți vreodată supărați pe voi pentru că nu ați luat punctaj bun. Dimpotrivă, orice veți face vom fi mîndri de voi pentru cît de departe ați ajuns în numai cîteva luni. Grija voastră trebuie să fie rezolvarea problemelor, nu noi. Noi sîntem de partea voastră. Chiar dacă la cerc sau la clasă, cînd sîntem între noi, vă certăm sau ne mai supărăm pe voi, în momentul cînd ați ieșit din școală să vă "luptați" cu olimpiada pentru noi, sîntem de aceeași parte a baricadei.

Diferenţa dintre olimpiadă şi viaţa reală

Nu uitaţi că olimpiada este un concurs de verificare a cunoştinţelor, nimic mai mult, nimic mai puţin. Ea nu este evaluarea supremă a unui elev, la fel cum nu este nici ceva de ignorat cu dispreţ. Este cel mai mare concurs de la clasa a 5a, drept pentru care îl vom trata cu respect. Dar nu ne vom spînzura de grindă, considerînd că viaţa s-a sfîrşit, dacă nu obţinem rezultatul dorit. Olimpiada nu ne defineşte ca oameni.

Acestea fiind spuse, dacă mergem la olimpiadă, ne dorim un scor cît mai bun. De aceea consider utilă următoarea analogie între arte marţiale si informatică:

  • În viaţa reală: în arte marţiale învăţăm pe viaţă. Procedee noi, ce trebuie aplicate cît mai corect, perfect dacă se poate. Filozofie, mod de comportament, respect faţă de artă şi luptă. Atunci cînd mişcarea nu este perfectă, instructorul vă va corecta. Bătaia este interzisă cu excepţia cazului cînd sînteţi în legitimă apărare. Este imoral şi foarte urît să cîştigaţi avantaje în viaţa reală bătîndu-i pe cei mai slabi. Artele marţiale au ca scop îmbunătăţirea organismului.
  • La olimpiadă: olimpiada este ca legitima apărare. Ca şi cînd sînteţi cu fratele mai mic după voi şi vă atacă golanii. În acel moment nu vă verifică nimeni cît de frumos aţi executat procedeul pentru a scăpa teferi. Tot ce contează este să învingeţi. Pentru aceasta vă veţi folosi de orice! Dacă găsiţi un bolovan, îl aruncaţi în adversar. O chiuvetă spartă, bună şi aceea! La fel şi la olimpiadă, tot ce contează sînt punctele. Nu cît de frumoasă este metoda folosită, nici cît de frumos aţi scris codul. Dacă puteţi lua puncte afişînd mereu "0", o faceţi. Această practică nu ar fi acceptată nici la cercul nostru şi nici în viaţa reală. Din păcate, însă, la olimpiadă nu se punctează stilul şi perfecţionismul, ci numai punctele.

Atenţie însă! Olimpiada este o excepţie, nu o regulă! Aşa cum în viaţa reală nu puteţi să smulgeţi chiuveta din perete pentru a o arunca în colegul de clasă, nici la cerc, la companii, sau unde se va întîmpla să rezolvaţi probleme de informatică, nu puteţi trişa, sau scrie cod ineficient.


Tema

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

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

Rezolvări aici [4]