Clasa a V-a lecția 44 - 11 iun 2013
Lecție
Conversii implicite şi conversii explicite
Atunci cînd atribuim unei variabile de un tip o valoare de alt tip programul execută o conversie implicită, aşa cum am văzut mai sus. Putem, însă, să dăm şi comenzi explicite de conversie. Să luăm un exemplu. Iată un calcul incorect:
int a, b; long long s; ... s = a + b;
Acest program nu funcţionează corect dacă a şi b sînt foarte mari, deoarece adunarea se va face pe numere întregi, abia apoi făcîndu-se conversie la tipul long long. Pentru a forţa conversia implicită la tipul long long putem să facem operaţia de adunare pe rînd:
int a, b; long long s; ... s = a; s = s + b;
dar programul se lungeşte şi devine mai puţin citibil. Al doilea mod este prin conversie explicită, astfel:
int a, b; long long s; ... s = ((long long)a) + b;
Deoarece unul din operanzi este de tip long long, de data aceasta adunarea se va face pe tipul long long, efectuîndu-se corect.
Ce observăm? Conversiile explicite se fac punînd tipul la care dorim să convertim valoarea între paranteze.
Instrucțiunea do-while
Instrucțiunea do-while în limbajul C implementează o structură repetitivă de tip REPEAT-UNTIL, care este o structură similară cu WHILE-DO. Iată schemele logice pentru cele două structuri alternative:
 |
while ( <cond> ) {
<prel>;
}
|
 |
do {
<prel>;
} while ( !<cond> );
|
Structura REPEAT-UNTIL repetă o secvenţă pînă cînd condiţia este adevărată. De aceea ieşirea din buclă se face pe "DA". Prin contrast, instrucţiunea do-while din C execută corpul buclei cîtă vreme condiţia este adevărată, de unde şi operatorul not (!) introdus în C.
Oricare din cele două structuri repetitive sînt suficiente pentru a descrie orice algoritm. Cu toate acestea, structura WHILE-DO este mai generală decît structura DO-UNTIL, deoarece corpul buclei REPEAT-UNTIL se execută cel puţin o dată, pe cînd bucla WHILE-DO poate să nu se execute nici o dată. Acesta este şi motivul pentru care nu am predat-o pînă acum.
Exemplu
Dîndu-se un număr n să se descompună în sumă de două pătrate perfecte nenule. Vom folosi următoarea metodă: vom căuta o descompunere n = a * a + b * b. Putem considera că a < b, fără a pierde din soluţii. Astfel, vom varia a * a de la 1 pînă la n / 2, verificînd dacă n - a * a este pătrat perfect. Această verificare se face extrăgînd radicalul şi verificînd că pătratul acestuia este chiar numărul original. Iată două variante de implementare, prima folosind while-do, iar a doua folosind do-while:
| Implementare cu WHILE-DO | Implementare cu REPEAT-UNTIL |
|---|---|
a = 1;
d = n - a * a;
b = sqrt( d );
while ( b * b < d && 2 * a * a < n ) {
a++;
d = n - a * a;
b = sqrt( d );
}
|
a = 0;
do {
a++;
d = n - a * a;
b = sqrt( d );
} while ( b * b < d && 2 * a * a < n );
|
Se observă că varianta cu do-while este ceva mai scurtă, deoarece nu repetă instrucţiunile care calculează valoarea lui b. Aceste cazuri, în care do-while este preferabilă lui while-do apar mai rar în practică.
Concurs: jocul Nim
Scrieți un program care să joace jocul Nim, descris mai jos. Elevii care vor reuși să termine implementarea jocului vor intra în concurs. În cadrul concursului fiecare program va juca cu fiecare alt program două jocuri, unul "tur" și unul "retur".
Echipe înscrise pînă acum
| Program | Programatori |
|---|---|
| alfa | Marcu Trițescu |
| auto-vortex | Matei Lascu, Vlad Ulmeanu |
| brain-kill | Vlad Stanciu, Rareș Căutiș |
| DAC-ul | Andrei Diaconu |
| emplopi | Ștefan Nițu |
| fire-phoenix | Matei Deleanu |
| FTL | Alexandru Păcurar |
| IM | Ruxandra Icleanu, Ioana Manea |
| nim | Robert Popovici |
| nim-tricks | Andrei Coman |
| pangeea | Ruxandra Hristache |
| primul-joc | Radu Priboi, Alex Mitrofan |
| stone-age | Alexandra Timofte |
| strategus | David Sachelarie |
Descriere joc
Originalul jocului Nim se joacă pe o tablă cu trei grămezi de piese, de cîte trei, patru și respectiv cinci piese fiecare. Fiecare jucător joacă, pe rînd, luînd un număr oarecare de piese (dar cel puțin una), din aceeași grămadă. Jucătorul care ia ultima piesă cîștigă.
Ce se cere, pe scurt
Dată o tablă de Nim, trebuie să executați mutarea voastră și să tipăriți tabla rezultată la ieșire. Voi și oponentul vostru jucați pe rînd, luînd piese, pînă ce toate piesele sînt luate. Cîștigătorul va primi un punct.
Programul vostru va citi un șir de numere de la intrarea standard (citire cu fgetc(stdin)) reprezentînd o configurație a tablei de Nim, apoi va executa o mutare prin scăderea unui din numerele diferite de zero de la intrare, iar în final va scrie la ieșirea standard (scriere cu fputc(c, stdout)) un alt şir de numere, configurația tablei după executarea mutării. Fiecare program va muta pe rînd, avînd la dispoziție 0.001 secunde pentru mutare.
Tabla de start
Tabla de start constă din maxim 30 de grămezi a cîte maxim 30 de piese fiecare. Ea este reprezentată printr-un şir de numere întregi despărţite prin spaţii. La finalul şirului vom avea un caracter sfîrşit de linie (\n). Iniţial toate grămezile vor avea cel puţin o piesă. Iată un exemplu de tablă de start:
3 4 5
Sînt trei grămezi, de cîte trei, patru, respectiv cinci piese fiecare.
- Tabla iniţială de joc va fi întotdeauna de un şir de maxim 30 numere nenule şi mai mici ca 30.
- Odată început jocul oricare din grămezile avînd un număr nenul de piese poate fi micşorată cu un număr ce corespunde numărului de piese luate.
- Programul va afişa aceleaşi grămezi, în aceeaşi ordine, singura diferenţă fiind grămada din care s-au luat piese.
- Datele de intrare și cele de ieșire nu vor conține alte caractere în afara şirului de întregi și caracterul sfîrșit de linie ("\n") la finalul liniei.
Tabla unui joc în desfășurare
3 0 5
Această tablă arată o mostră de joc după ce au fost efectuate una sau mai multe mutări, iar grămada din mijloc este acum vidă, nemaiavînd nici o piesă.
- Mutările se vor face prin scăderea numărului de piese dintr-o grămadă nenulă.
- Întotdeauna va exista cel puțin o grămadă nevidă rămasă pe tabla de la intrare, așa încît întotdeauna va fi posibilă executarea unei mutări.
Punctarea
- Programul care goleşte tabla (ia ultima piesă de pe tablă) cîştigă un punct.
- Fiecare meci va consta din două jocuri, fiecare program va avea ocazia să înceapă. Cîștigătorul meciului va fi programul care acumulează mai multe puncte în ambele meciuri.
Programul vostru
- Limbajul folosit va fi limbajul C. Atenție! Nu se acceptă extensii C++! Fișierele vor fi denumite cu extensia .c
- Fiecare mutare trebuie executată în maxim 0.001 secunde (1 milisecundă). Adică extrem de repede, pentru a putea desfășura un număr mare de jocuri.
- Limita de memorie este de 64MB.
- Programul vostru trebuie să citească de la intrarea standard și să scrie la ieșirea standard. Aceasta înseamnă să nu folosiți fișiere ci instrucțiunile scanf/printf sau fgetc/fputc cu parametri stdin/stdout în loc de fișiere.
- Programul vostru nu poate să citească din, sau să scrie în fișiere. Singura informație disponibilă este cea citită la intrare și anume starea actuală a tablei de joc.
- Datele de la intrare sînt corecte. Intrarea nu va conține alte caractere în afara șirului de numere reprezentînd grămezile și "\n" la finalul liniei.
Desfășurarea concursului
Concursul se va desfășura în timpul orelor de cerc de marți 18 iunie 2013, orele 10:30-12:30. Vor fi acordate premii! Pot participa orice elevi de la clasa a 5-a de la Tudor Vianu. Dacă vor fi mai mult de 30 de participanți s-ar putea să schimb puțin regulile de desfășurare din criză de timp.
Concursul se va desfășura în sistem campionat. Fiecare program va juca un meci cu fiecare alt program. Un meci constă din două jocuri pe aceeași tablă, în care fiecare din programe începe, pe rînd. În final clasamentul programelor se stabilește pe baza numărului de puncte acumulate.
Trimiterea codului sursă
Momentul limită al acceptării unui program pentru concurs este la începutul cercului din 18 iunie. Cu toate acestea vă încurajez să-mi trimiteți variante intermediare pe email (numai programul C vă rog, nu și proiectul). Voi încerca să vă returnez cum s-a comportat programul vostru contra celorlalte programe trimise. De asemenea vă voi raporta erorile de execuție (depășire de timp, mutare eronată, depășire de memorie). Vă rog să-mi trimiteți sursele ca atașamente.
Fiecare program C care participă va fi denumit cu o denumire de cod ce va fi folosită în tabelele de rezultate drept identificare. Primele linii ale programului C vor avea următorul antet, drept comentariu, care conține numele programului și datele concurentului:
/* Nume program : rapid-si-furios.c Nume concurent : Cristian Francu E-mail : cristian@francu.com */
În acest exemplu numele fișierului C este rapid-si-furios.c, iar programul va fi referit în tabelele de rezultate ca rapid-si-furios.
Atenție: Puteți forma echipe de maxim doi oameni, dar premiul se va împărți la doi.
Atenție: Trimiteți-mi cît mai repede un email de confirmare a participării, ca să știu cîte programe vor fi. Emailul trebuie să conțină numele și emailurile concurenților din echipă.
Temă
- Participați la concurs. Accept rezolvări pe email de la orice elev de clasa a 5-a la liceul Tudor Vianu.
- Pentru doritori mai există un concurs, pentru clasele 6-8. Este vorba tot de un joc, dar ceva mai greu. Puteți să participați și aici dacă doriți, dar vă rog, multă seriozitate. Sursele "la mișto" vor fi excluse și mă vor supăra.
