Nu exista diferente intre titluri.
Diferente intre continut:
(Categoria _Diverse_, Autor _Catalin Francu_, Preluat din cartea _"Psihologia concursurilor de informatica"_)
_"Cine doreste sa-si rezolve treburile la vremea potrivita, sa-si imparta cu atentie timpul"_ (Plaut)
(toc){width: 37em}*{text-align:center} *Conţinut:*
* 'Inainte de concurs':concursul-de-informatica#inainte-de-concurs
* 'In timpul concursului':concursul-de-informatica#in-timpul-concursului
* 'Strategii in timpul concursului':concursul-de-informatica#strategii
* 'Concluzii':concursul-de-informatica#concluzii
h3. _"Cine doreste sa-si rezolve treburile la vremea potrivita, sa-si imparta cu atentie timpul"_, Plaut
Experienta demonstreaza ca, oricat de mare ar fi bagajul de cunostinte acumulat de un elev, mai e nevoie de ceva pentru a-i asigura succesul la olimpiada de informatica. Aceasta deoarece in timp de concurs lucrurile stau cu totul altfel decat in fata calculatorului de acasa sau de la scoala. Reusita depinde, desigur, in cea mai mare masura de puterea fiecaruia de a pune in practica ceea ce a invatat acasa. Numai ca in acest proces intervin o serie de factori care tin de temperament, de experienta individuala, de numarul de ore dormite in noaptea dinaintea concursului (care in taberele nationale este ingrijorator de mic) si asa mai departe.
Cu riscul de a cadea in demagogie, trebuie sa spunem ca un concurs de informatica presupune mult mai mult decat un simplu act de prezenta la locul desfasurarii ostilitatilor. Capitolul de fata incearca sa enunte cateva principii ale concursului, pe care autorul si le-a insusit in cei patru ani de liceu, atat din experienta proprie, cat si invatand de la altii. Cititorul este liber sa respinga aceste sfaturi sau sa le accepte, filtrandu-le prin prisma personalitatii sale si alegand ceea ce i se potriveste.
h2. Inainte de concurs
h2(#inainte-de-concurs). Inainte de concurs
Primul si cel mai de seama lucru pe care trebuie sa il stiti este ca e important si sa participi, dar e si mai important sa participi onorabil, iar daca se poate sa si castigi. Nu trebuie sa porniti la drum cu ingamfare; modestia e buna, dar nu trebuie in nici un caz sa duca la neincredere in sine. Fiecare trebuie sa stie clar de ce e in stare si, mai presus de toate, sa se gandeasca ca la urma urmei nu dificultatea concursului conteaza, caci concursul, greu sau usor, este acelasi pentru toti. Mult mai importanta este valoarea individuala si nu in ultimul rand pregatirea psihologica.
Autorul a fost peste masura de surprins sa constate ca multi elevi merg la concurs fara ceas si fara hartie de scris. Aceasta este fara indoiala o greseala capitala. In timpul concursului trebuie tinuta o evidenta drastica a timpului scurs si a celui ramas. E drept ca in general supraveghetorii anunta din cand in cand timpul care a trecut, dar e bine sa nu va bazati pe nimeni si nimic altceva decat pe voi insiva. Unii colegi spuneau "Ei, ce nevoie am de ceas, oricum am ceasul calculatorului la indemana". Asa e, dar e extrem de incomod sa te opresti mereu la jumatatea unei idei, sa deschizi o sesiune DOS din cadrul limbajului de programare si sa afli cat e ceasul.
In ceea ce priveste hartia de scris, ea este in mod sigur necesara. De fapt, o parte importanta a rezolvarii unei probleme este proiectarea matematica a algoritmului, lucru care nu se poate face decat cu creionul pe hartie. Pe langa aceasta, majoritatea problemelor opereaza cu vectori, matrice, arbori, grafuri etc., iar exemplele pe care este testat programul realizat trebuie neaparat verificate "de mana". E de preferat sa aveti hartie de matematica; este foarte folositoare pentru problemele de geometrie analitica, precum si pentru reprezentarea matricelor. Cantitatea depinde de imaginatia fiecaruia. In unele cazuri speciale, autorului i s-a intamplat sa umple 7-8 coli A4.
h2. In timpul concursului
h2(#in-timpul-concursului). In timpul concursului
Din fericire pentru unii si din nefericire pentru altii, majoritatea examenelor iti cer sa dovedesti nu ca esti bine pregatit, ci ca esti mai bine pregatit decat altii. Aceasta inseamna ca si la olimpiada de informatica se aplica legea pestelui mai mare sau, cum i se mai spune, a concurentei. Valoarea absoluta a fiecaruia nu conteaza chiar in totalitate, ceea ce constituie sarea si piperul concursului. Intr-adevar, ce farmec ar avea sa mergi la un concurs la care se stie inca dinainte cine este cel mai bun ? Este destul de amuzant sa observi cum fiecare spera sa prinda "o zi buna", iar adversarii sai "o zi proasta".
Niciodata, chiar daca concursul este usor, nu e bine sa iesiti din sala de concurs inainte de expirarea timpului. Oricat ati fi de convinsi ca ati facut totul perfect, mai verificati-va; veti avea de furca cu remuscarile daca descoperiti dupa aceea ca ceva, totusi, nu a mers bine. Puteti face o multime de lucruri daca mai aveti timp (desi acest lucru se intampla rar). Iata o serie de metode de a exploata timpul:
* Verificati-va programul cu cat mai multe teste de mici dimensiuni. Sa presupunem ca programul vostru lucreaza cu vectori de maxim 10000 de elemente. E o idee buna sa il rulati pentru vectori de unul sau doua elemente. Nu se stie cum pot sa apara erori.
* Verificati-va programul cu cat mai multe teste de mici dimensiuni. Sa presupunem ca programul vostru lucreaza cu vectori de maxim 10 000 de elemente. E o idee buna sa il rulati pentru vectori de unul sau doua elemente. Nu se stie cum pot sa apara erori.
* Treceti la polul opus si creati-va un test de dimensiune maxima, dar cu o structura particulara, pentru care este usor de calculat rezultatul si de mana. De exemplu, vectori de 10000 elemente cu toate elementele egale, sau vectori de forma (1, 2, ..., 9999, 10000). Daca nu puteti sa editati un asemenea fisier de mana, copiind si multiplicand blocuri, puteti scrie un program care sa-l genereze.
* Treceti la polul opus si creati-va un test de dimensiune maxima, dar cu o structura particulara, pentru care este usor de calculat rezultatul si de mana. De exemplu, vectori de 10 000 elemente cu toate elementele egale, sau vectori de forma (1, 2, ..., 9 999, 10 000). Daca nu puteti sa editati un asemenea fisier de mana, copiind si multiplicand blocuri, puteti scrie un program care sa-l genereze.
* Daca inca v-a mai ramas timp, creati-va un program care sa genereze teste aleatoare. Spre exemplu, un program care sa citeasca un numar N si sa creeze un fisier $INPUT.TXT$ in care sa scrie N numere aleatoare. Intr-o prima faza, puteti folosi aceste teste pentru a verifica daca nu cumva la valori mai mari programul nu da eroare, nu se blocheaza (la alocarea unor zone mari de memorie) sau nu depaseste limita de timp, caz in care mai aveti de lucru.
* Daca inca v-a mai ramas timp, creati-va un program care sa genereze teste aleatoare. Spre exemplu, un program care sa citeasca un numar $N$ si sa creeze un fisier $INPUT.TXT$ in care sa scrie $N$ numere aleatoare. Intr-o prima faza, puteti folosi aceste teste pentru a verifica daca nu cumva la valori mai mari programul nu da eroare, nu se blocheaza (la alocarea unor zone mari de memorie) sau nu depaseste limita de timp, caz in care mai aveti de lucru.
* Daca tot nu va da nimeni afara din sala, puteti scrie un alt program auxiliar care, primind fisierul $INPUT.TXT$ si fisierul $OUTPUT.TXT$ produs de programul vostru, verifica daca iesirea este corecta. Aceasta deoarece, de obicei, este mult mai usor de verificat o solutie decat de produs una (sau, cum spunea Murphy, "cunoasterea solutiei unei probleme poate ajuta in multe cazuri la rezolvarea ei"). Folosind "generatorul" de teste si "verificatorul", puteti testa programul mult mai bine. De altfel, la multe probleme chiar testele rulate de comisia de corectare sunt create tot aleator.
* In caz ca ati dat o solutie euristica la o problema NP-completa, puteti implementa si un backtracking ca sa vedeti cat de bune sunt rezultatele gasite euristic. Apoi, puteti incepe sa modificati functia euristica pentru a o face cat mai performanta.
h2(#strategii). Strategii in timpul concursului
Si, ca sa nu mai lungim vorba, iata cateva strategii care par sa dea rezultate.
Si, ca sa nu mai lungim vorba, iata o strategie care pare sa dea rezultate:
h4. A)
**A)** Imediat ce primiti problemele, cititi toate enunturile si faceti-va o idee aproximativa despre gradul de dificultate al fiecarei probleme. Neaparat verificati daca se dau limite pentru datele de intrare (numarul maxim de elemente ale unui vector si valoarea maxima a acestora, numarul maxim de noduri dintr-un graf etc.) si pentru timpii de executie pentru fiecare test. Daca nu se dau, intrebati imediat. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vector cu $N=100$ elemente, un algoritm $O(N^3^)$ merge rezonabil, pe cand pentru $N=10000$ acelasi algoritm ar depasi cu mult cele cateva secunde care se acorda de obicei. Fair-play-ul cere sa puneti intrebarile cu voce tare, pentru ca si ceilalti sa auda; de altfel, nu aveti nici un motiv sa va feriti de ceilalti concurenti. Cei care sunt interesati de aceste intrebari le-ar pune oricum si ei, iar cei care nu sunt interesati vor ignora oricum raspunsul.
Imediat ce primiti problemele, cititi toate enunturile si faceti-va o idee aproximativa despre gradul de dificultate al fiecarei probleme. Neaparat verificati daca se dau limite pentru datele de intrare (numarul maxim de elemente ale unui vector si valoarea maxima a acestora, numarul maxim de noduri dintr-un graf etc.) si pentru timpii de executie pentru fiecare test. Daca nu se dau, intrebati imediat. Dimensiunea input-ului poate schimba radical dificultatea problemei. Spre exemplu, pentru un vector cu $N = 100$ elemente, un algoritm $O(N^3^)$ merge rezonabil, pe cand pentru $N = 10 000$ acelasi algoritm ar depasi cu mult cele cateva secunde care se acorda de obicei. Fair-play-ul cere sa puneti intrebarile cu voce tare, pentru ca si ceilalti sa auda; de altfel, nu aveti nici un motiv sa va feriti de ceilalti concurenti. Cei care sunt interesati de aceste intrebari le-ar pune oricum si ei, iar cei care nu sunt interesati vor ignora oricum raspunsul.
Daca exista probleme care cer sa se gaseasca un optim (maxim/minim) al unei valori, intrebati daca se acorda punctaje partiale pentru solutii neoptime. Si acest fapt poate schimba natura problemei. Dupa aceasta,
==code(c)|
== code(c) |
Nr_probleme_nerezolvate = Nr_probleme_primite;
while ((Nr_probleme_nerezolvate > 0) and !("Timpul a expirat, va rugam sa salvati"))
while ((Nr_probleme_nerezolvate > 0) and !("Timpul a expirat, va rugam sa salvati"))
{
==
**B)** Faceti o impartire a timpului pentru problemele ramase proportional cu punctajul fiecarei probleme. In general problemele au punctaje egale, dar nu totdeauna. De exemplu, daca o problema e cotata cu 100 puncte, iar alta cu 50, veti aloca de doua ori mai mult timp primei probleme, chiar daca nu vi se pare prea grea. Incercati sa nu depasiti niciodata limitele de timp pe care le-ati fixat. Daca in schimb reusiti sa economisiti timp fata de cat v-ati propus, cu atat mai bine, veti face o realocare a timpului si veti avea mai mult pentru celelalte probleme.
h4. B)
Faceti o impartire a timpului pentru problemele ramase proportional cu punctajul fiecarei probleme. In general problemele au punctaje egale, dar nu totdeauna. De exemplu, daca o problema e cotata cu 100 puncte, iar alta cu 50, veti aloca de doua ori mai mult timp primei probleme, chiar daca nu vi se pare prea grea. Incercati sa nu depasiti niciodata limitele de timp pe care le-ati fixat. Daca in schimb reusiti sa economisiti timp fata de cat v-ati propus, cu atat mai bine, veti face o realocare a timpului si veti avea mai mult pentru celelalte probleme.
h4. C)
Apucati-va de problema _cea mai simpla_, chiar daca e punctata mai slab. Mai bine sa duceti la bun sfarsit o problema usoara si sa luati un punctaj mai mic, decat sa va apucati de o problema grea si sa nu terminati niciuna. Daca toate problemele par grele, alegeti-o pe cea din domeniul care va este cel mai familiar, in care ati lucrat cel mai mult. Daca va este indiferent si acest lucru, alegeti o problema unde simtiti ca aveti o idee simpla de rezolvare. Daca, in sfarsit, nu aveti nici o idee la nici o problema, apucati-va de cea mai bine punctata.
**C)** Apucati-va de problema +cea mai simpla+, chiar daca e punctata mai slab. Mai bine sa duceti la bun sfarsit o problema usoara si sa luati un punctaj mai mic, decat sa va apucati de o problema grea si sa nu terminati niciuna. Daca toate problemele par grele, alegeti-o pe cea din domeniul care va este cel mai familiar, in care ati lucrat cel mai mult. Daca va este indiferent si acest lucru, alegeti o problema unde simtiti ca aveti o idee simpla de rezolvare. Daca, in sfarsit, nu aveti nici o idee la nici o problema, apucati-va de cea mai bine punctata.
h4. D)
**D)** Cititi din nou enuntul, de data aceasta cu mare grija. Intrebati supraveghetorul pentru orice nelamurire. Daca anumite lucruri nu sunt specificate, iar profesorul nu va da nici un fel de informatii suplimentare, tratati problema in cazul cel mai general. Iata mai multe exemple frecvente in care enuntul nu este limpede:
Cititi din nou enuntul, de data aceasta cu mare grija. Intrebati supraveghetorul pentru orice nelamurire. Daca anumite lucruri nu sunt specificate, iar profesorul nu va da nici un fel de informatii suplimentare, tratati problema in cazul cel mai general. Iata mai multe exemple frecvente in care enuntul nu este limpede:
* Daca nu se precizeaza cat de mari pot fi intregii dintr-un vector, nu lucrati pe Integer, nici pe Word, ci pe LongInt;
* Daca nu se precizeaza cat de mari pot fi intregii dintr-un vector, nu lucrati pe $Integer$, nici pe $Word$, ci pe $LongInt$;
* In problemele de geometrie analitica, e bine sa presupuneti ca punctele nu au coordonate intregi, ci reale;
* De asemenea, patratele si dreptunghiurile nu au neaparat laturi paralele cu axele, ci sunt asezate oricum in plan (aceasta poate intr-adevar sa complice extrem de mult problema; nu va doresc sa va izbiti de o asemenea neclaritate...);
* Daca fisierul de intrare contine string-uri, sa nu presupuneti ca ele au maxim 255 de caractere. Mai bine scrieti propria voastra procedura de citire a unui string, care sa citeasca din fisier caracter cu caracter pana la Eoln, decat sa aveti surprize. Daca S este o variabila de tip String, ReadLn(S) ignora tot restul randului care depaseste lungimea lui S.
* Daca fisierul de intrare contine siruri de caractere, sa nu presupuneti ca ele au maxim $255$ de caractere. Mai bine scrieti propria voastra procedura de citire a unui sir de caractere, care sa citeasca din fisier caracter cu caracter pana la $Eoln$, decat sa aveti surprize. Daca $S$ este o variabila de tip $String$, $ReadLn(S)$ ignora tot restul randului care depaseste lungimea lui $S$;
* Grafurile nu sunt neorientate, ci orientate. In principiu, enuntul nu are voie sa fie neclar in aceasta privinta, dar au existat cazuri de neintelegere.
**E)** Incepeti sa va ganditi la algoritmi cat mai buni, estimand in acelasi timp si cat v-ar lua ca sa-i implementati. Faceti, pentru fiecare idee care va vine, calculul complexitatii. Nu trebuie neaparat sa gasiti cel mai eficient algoritm, ci numai unul suficient de bun. In general, trebuie ca, dintre toti algoritmii care se incadreaza in timpul de rulare, sa-l alegeti pe cel care este cel mai usor de implementat. Iata un exemplu:
h4. E)
* Sa presupunem ca timpul de testare este de 5 secunde, lucrati pe un 486DX4, algoritmul vostru are complexitatea $O(N^3^)$, iar $N$ este maxim 100. Un 486 face cateva milioane de operatii elementare pe secunda, sa zicem 4.000.000. Aceasta inseamna ceva mai putine operatii mai costisitoare (atribuiri, comparatii etc.) pe secunda. Sa ne oprim deci la cifra de 1.000.000. Programul vostru are timp de rulare cubic, iar N3 este maxim 1.000.000. De aici deducem ca programul ar trebui sa se incadreze intr-o secunda. Calculul nostru este grosier, dar luand si o marja de eroare arhisuficienta, rezulta ca programul trebuie sa mearga cu usurinta in 5 secunde, deci algoritmul este acceptabil.
Incepeti sa va ganditi la algoritmi cat mai buni, estimand in acelasi timp si cat v-ar lua ca sa-i implementati. Faceti, pentru fiecare idee care va vine, calculul complexitatii. Nu trebuie neaparat sa gasiti cel mai eficient algoritm, ci numai unul suficient de bun. In general, trebuie ca, dintre toti algoritmii care se incadreaza in timpul de rulare, sa-l alegeti pe cel care este cel mai usor de implementat.
**F)** Daca algoritmul gasit este greu de implementat, mai cautati un altul o vreme. Trebuie insa ca timpul petrecut pentru gasirea unui nou algoritm plus timpul necesar pentru scrierea programului sa nu depaseasca timpul necesar pentru implementarea primului algoritm, altfel nu castigati nimic. Deci nu exagerati cu cautarile si nu incercati sa reduceti dincolo de limita imposibilului complexitatea algoritmului. Mai ales, nu uitati ca programul nu poate avea o complexitate mai mica decat dimensiunea input-ului sau a output-ului. De exemplu, daca programul citeste sau scrie matrice de dimensiune NxN, nu are sens sa va bateti capul ca sa gasiti un algoritm mai bun decat $O(N^2^)$.
Sa presupunem ca timpul de testare este de $5$ secunde, lucrati pe un 486DX4, algoritmul vostru are complexitatea $O(N^3^)$, iar $N$ este maxim $100$. Un 486 face cateva milioane de operatii elementare pe secunda, sa zicem $4 000 000$. Aceasta inseamna ceva mai putine operatii mai costisitoare (atribuiri, comparatii etc.) pe secunda. Sa ne oprim deci la cifra de $1 000 000$. Programul vostru are timp de rulare cubic, iar $N^3^$ este maxim $1 000 000$. De aici deducem ca programul ar trebui sa se incadreze intr-o secunda. Calculul nostru este grosier, dar luand si o marja de eroare arhisuficienta, rezulta ca programul trebuie sa mearga cu usurinta in $5$ secunde, deci algoritmul este acceptabil.
**G)** Dintre toate ideile de implementare gasite (care se incadreaza fara probleme in timp), o veti alege pe cea mai scurta ca lungime de cod. De exemplu:
h4. F)
* Daca N ≤ 1000 si dispuneti de doi algoritmi, unul pe care il estimati cam la 200 de linii de program, de complexitate $O(N log N)$ si unul de 100 de linii de complexitate $O(N^2^)$, cel de-al doilea este evident preferabil, pentru ca nu pierdeti nimic din punctaj, sau cel mult pierdeti un test prin cine stie ce intamplare, in schimb castigati timp pretios pe care il puteti folosi pentru alte probleme. Bineinteles, primul program este mai eficient, dar in conditii de concurs el este prea eficient. Este o mandrie sa faceti o problema perfect chiar daca ratati o alta, dar este un castig si mai mare sa faceti amandoua problemele suficient de bine.
Daca algoritmul gasit este greu de implementat, mai cautati un altul o vreme. Trebuie insa ca timpul petrecut pentru gasirea unui nou algoritm plus timpul necesar pentru scrierea programului sa nu depaseasca timpul necesar pentru implementarea primului algoritm, altfel nu castigati nimic. Deci nu exagerati cu cautarile si nu incercati sa reduceti dincolo de limita imposibilului complexitatea algoritmului. Mai ales, nu uitati ca programul nu poate avea o complexitate mai mica decat dimensiunea input-ului sau a output-ului. De exemplu, daca programul citeste sau scrie matrice de dimensiune $N x N$, nu are sens sa va bateti capul ca sa gasiti un algoritm mai bun decat $O(N^2^)$.
**H)** In general, pentru orice problema exista cel putin o solutie, fie si una slaba. Sunt numeroase cazurile cand nici nu va vine alta idee de rezolvare decat cea slaba. De regula, cand nu aveti in minte decat o rezolvare neeficienta a problemei, care stiti ca nu o sa treaca toate testele (un backtracking, sau un $O(N^5^)$, $O(N^6^)$ etc.), e bine sa incercati urmatorul lucru:
h4. G)
Dintre toate ideile de implementare gasite (care se incadreaza fara probleme in timp), o veti alege pe cea mai scurta ca lungime de cod. De exemplu:
* Daca $N ≤ 1 000$ si dispuneti de doi algoritmi, unul pe care il estimati cam la $200$ de linii de program, de complexitate $O(N log N)$ si unul de $100$ de linii de complexitate $O(N^2^)$, cel de-al doilea este evident preferabil, pentru ca nu pierdeti nimic din punctaj, sau cel mult pierdeti un test prin cine stie ce intamplare, in schimb castigati timp pretios pe care il puteti folosi pentru alte probleme. Bineinteles, primul program este mai eficient, dar in conditii de concurs el este prea eficient. Este o mandrie sa faceti o problema perfect chiar daca ratati o alta, dar este un castig si mai mare sa faceti amandoua problemele suficient de bine.
h4. H)
In general, pentru orice problema exista cel putin o solutie, fie si una slaba. Sunt numeroase cazurile cand nici nu va vine alta idee de rezolvare decat cea slaba. De regula, cand nu aveti in minte decat o rezolvare neeficienta a problemei, care stiti ca nu o sa treaca toate testele (un backtracking, sau un $O(N^5^)$, $O(N^6^)$ etc.), e bine sa incercati urmatorul lucru:
* Sa presupunem ca v-a mai ramas o ora pentru rezolvarea acestei probleme. Calculati cam cat timp v-ar trebui ca sa implementati rezolvarea slaba. Sa zicem 40 de minute. In acest calcul trebuie sa includeti si timpul de depanare a programului (care variaza de la persoana la persoana) si pe cel de testare. Daca sunteti foarte siguri pe voi, puteti sa neglijati timpul de testare, dar orice program trebuie testat cel putin pe exemplul de pe foaie.
* Puteti, ca o masura extrema, sa depasiti cu maxim 5 minute cele 20 de minute planificate, dar de cele mai multe ori acesta e timp pierdut, deoarece intervine stresul si nu puteti sa va mai concentrati.
**I)** Daca ati ajuns pana aici inseamna ca ati optat pentru o varianta de implementare. Din acest moment, pentru aceasta varianta veti scrie programul, fara a va mai gandi la altceva, chiar daca pe parcurs va vin alte idei. Iata unele lucruri pe care e bine sa le stiti despre scrierea unui program:
h4. I)
Daca ati ajuns pana aici inseamna ca ati optat pentru o varianta de implementare. Din acest moment, pentru aceasta varianta veti scrie programul, fara a va mai gandi la altceva, chiar daca pe parcurs va vin alte idei. Iata unele lucruri pe care e bine sa le stiti despre scrierea unui program:
* Datele de intrare se presupun a fi corecte. Aceasta este o regula nescrisa (uneori) a concursului de informatica. Chiar daca, prin absurd, stiti sigur ca datele de intrare trebuie verificate, mai bine n-o faceti, din mai multe motive. In primul rand, scopul cu care v-a fost data problema este altul decat sa se constate cine verifica mai bine datele de intrare. De aceea, cel mult un test sau doua vor fi cu date gresite. In al doilea rand, nu se justifica sa risipiti atata timp numai pentru cateva puncte pe care le-ati putea pierde daca nu faceti verificarea. In al treilea rand, e posibil sa gresiti oricum problema in sine, caz in care nu mai conteaza daca ati citit perfect datele de intrare. In sfarsit, legea lui Murphy spune ca "oricate teste ar efectua cineva asupra datelor de intrare, se va gasi cineva care sa introduca date gresite". Efortul este deci zadarnic...
* Ultimul lucru, cand sunteti convinsi ca programul este terminat si cand v-ati hotarat sa nu il mai modificati, adaugati optiunile de compilare. Puteti face aceasta apasand Ctrl-O-O. La inceputul programului vor aparea directivele de compilare. Setati $B, $I, $R si $S pe - (minus). Eventual, puteti include direct linia I$B-,I-,R-,S-S imediat dupa titlul programului. Aceasta va face compilatorul sa nu mai evalueze complet expresiile booleene, sa nu mai verifice operatiile de intrare/iesire, domeniul de atribuire (Range Checking) si stiva (Stack Checking). Exista doua avantaje majore: in primul rand ca programul merge mai repede (se castiga cateva procente bune la viteza), iar in al doilea rand, psihologic vorbind, este preferabil ca un program sa se blocheze decat sa se opreasca printr-un banal $"Range check error"$. Nu va grabiti sa puneti directivele de compilare inca de la inceput, deoarece nu veti mai primi mesajele corespunzatoare de eroare si va va fi mai greu sa depanati programul.
* Ultimul lucru, cand sunteti convinsi ca programul este terminat si cand v-ati hotarat sa nu il mai modificati, adaugati optiunile de compilare. Puteti face aceasta apasand $Ctrl-O-O$. La inceputul programului vor aparea directivele de compilare. Setati $$B$, $$I$, $$R$ si $$S$ pe - (minus). Eventual, puteti include direct linia $I$B-,I-,R-,S-S$ imediat dupa titlul programului. Aceasta va face compilatorul sa nu mai evalueze complet expresiile booleene, sa nu mai verifice operatiile de intrare/iesire, domeniul de atribuire $(Range Checking)$ si stiva $(Stack Checking)$. Exista doua avantaje majore: in primul rand ca programul merge mai repede (se castiga cateva procente bune la viteza), iar in al doilea rand, psihologic vorbind, este preferabil ca un program sa se blocheze decat sa se opreasca printr-un banal $Range check error$. Nu va grabiti sa puneti directivele de compilare inca de la inceput, deoarece nu veti mai primi mesajele corespunzatoare de eroare si va va fi mai greu sa depanati programul.
* Pe cat este posibil, incercati sa convingeti juriul sa nu va ruleze sursa (Pascal sau C/C++), ci direct executabilul. Merge simtitor mai repede. Asta numai in cazul in care va temeti ca programul ar putea sa nu se incadreze in timp.
* Daca se poate, evitati lucrul cu pointeri. Programele care ii folosesc sunt mai greu de depanat si se pot bloca mult mai usor.
* Sa presupunem ca aveti de lucrat cu matrice de dimensiuni maxim 100x100. Unii elevi au obiceiul sa dimensioneze la inceput matricele de 5x5 sau 10x10, deoarece sunt mai comod de evaluat cu $Evaluate$ (Ctrl-F4) sau $Watch$ (Ctrl-F7). Acest lucru este adevarat, dar exista riscul ca la sfarsit sa uitati sa redimensionati matricele de 100x100. Decat sa faceti o asemenea greseala (care in mod sigur va va compromite toata problema), mai bine setati dimensiunile corecte de la inceput. De altfel, ideal ar fi ca depanarea programelor sa fie suprimata cu totul si programul sa mearga din prima.
* Sa presupunem ca aveti de lucrat cu matrice de dimensiuni maxim $100 x 100$. Unii elevi au obiceiul sa dimensioneze la inceput matricele de $5 x 5$ sau $10 x 10$, deoarece sunt mai comod de evaluat cu $Evaluate (Ctrl-F4)$ sau $Watch (Ctrl-F7)$. Acest lucru este adevarat, dar exista riscul ca la sfarsit sa uitati sa redimensionati matricele de $100 x 100$. Decat sa faceti o asemenea greseala (care in mod sigur va va compromite toata problema), mai bine setati dimensiunile corecte de la inceput. De altfel, ideal ar fi ca depanarea programelor sa fie suprimata cu totul si programul sa mearga din prima.
* Evitati lucrul cu numere reale, daca puteti. Operatiile in virgula mobila sunt mult mai lente. De exemplu, testul daca un numar este prim nu va incepe in nici un caz cu linia
==code(c) |
while (i <= srt(N))
while (i <= sqrt(N))
==
ci cu linia
==code(c) |
while (i*i <= N)
while (i * i <= N)
==
Din punct de vedere logic, conditiile sunt perfect echivalente. Totusi, prima se evalueaza de cateva zeci de ori mai incet decat a doua.
deoarece pot aparea erori, ci implementati o functie:
==code(c) |
int equal(float R1, R2)
int equal(float R1, float R2)
{
if (abs(R1-R2) < 0.00001) return 1;
if (abs(R1 - R2) < 1e-4) // 1e-4 = 0.00001
return 1;
return 0;
}
==
Numarul de zerouri de dupa virgula trebuie sa fie suficient de mare astfel incat doua numere diferite sa nu fie tratate drept egale (se poate lucra de pilda cu 0.000001).
Numarul de zerouri de dupa virgula trebuie sa fie suficient de mare astfel incat doua numere diferite sa nu fie tratate drept egale (se poate lucra de pilda cu $0.000001$).
* Tot in cazul numerelor reale, evitati pe cat posibil sa faceti impartiri, deoarece sunt foarte greoaie. De exemplu:
X/5 <tex> \Leftrightarrow </tex> 0.2*X
X/Y/Z <tex> \Leftrightarrow </tex> X/(Y*Z)
$X / 5 <=> 0.2 * X$
$X / Y / Z <=> X / (Y * Z)$
* Optimizarile de genul $X shl 1$ respectiv $X<<1$ in loc de $2*X$ sunt niste artificii de cele mai multe ori neesentiale, care in schimb fac formulele mai lungi, greu de urmarit si pot crea complicatii. Cel mai bine este sa lucrati cu notatiile obisnuite si doar la sfarsit, daca timpul de rulare trebuie redus cu orice pret, sa faceti inlocuirile.
* Optimizarile de genul $X shl 1$ respectiv $X << 1$ in loc de $2 * X$ sunt niste artificii de cele mai multe ori neesentiale, care in schimb fac formulele mai lungi, greu de urmarit si pot crea complicatii. Cel mai bine este sa lucrati cu notatiile obisnuite si doar la sfarsit, daca timpul de rulare trebuie redus cu orice pret, sa faceti inlocuirile.
* Alegeti-va numele de variabile in asa fel incat programul sa fie clar. Sunt permise mai mult de doua litere! Numele fiecarei proceduri, functii, variabile trebuie sa-i explice clar utilitatea. E drept, lungimea programului creste, dar codul devine mult mai limpede si timpul de depanare scade foarte mult. Ca o regula generala, claritatea programelor face mult mai usoara intelegerea lor chiar si dupa o perioada mai indelungata de timp (luni, ani). Nu trebuie nici sa cadeti in cealalta extrema. De exemplu, nu depasiti 10 caractere pentru un nume de variabila.
* Tot in situatia in care exista mai multe seturi de date in fisierul de intrare, daca iesirea se face intr-un fisier, este bine ca dupa afisarea rezultatului pentru fiecare test sa actualizati fisierul de iesire (fie prin comanda $Flush$, fie prin doua proceduri, $Close$ si $Append$). In felul acesta, chiar daca la unul din teste programul se blocheaza sau da eroare, rezultatele deja scrise raman scrise. Altfel, e posibil ca rezultatele de la testele anterioare sa ramana intr-un buffer in memorie, fara a fi "varsate" pe disc.
* Daca fisierul de iesire are dimensiuni foarte mari, de exemplu daca vi se cer toate solutiile, iar numarul acestora este de ordinul zecilor de mii, puteti avea surpriza ca timpul sa nu va ajunga pentru a le tipari pe toate in fisierul de iesire. Si in acest caz, este recomandat ca dupa tiparirea fiecarei solutii sa executati comanda Flush, sau sa inchideti fisierul de iesire si sa-l redeschideti in modul Append.
* Daca fisierul de iesire are dimensiuni foarte mari, de exemplu daca vi se cer toate solutiile, iar numarul acestora este de ordinul zecilor de mii, puteti avea surpriza ca timpul sa nu va ajunga pentru a le tipari pe toate in fisierul de iesire. Si in acest caz, este recomandat ca dupa tiparirea fiecarei solutii sa executati comanda $Flush$, sau sa inchideti fisierul de iesire si sa-l redeschideti in modul $Append$.
h4. J)
**J)** Daca ati trecut cu bine si de faza de scriere a programului, mai aveti doar partile de depanare si testare, care de multe ori se imbina. Metoda cea mai buna de depanare este urmatoarea:
Daca ati trecut cu bine si de faza de scriere a programului, mai aveti doar partile de depanare si testare, care de multe ori se imbina. Metoda cea mai buna de depanare este urmatoarea:
* Incepeti cu un test nici prea simplu, nici prea complicat (si usor de urmarit cu creionul pe hartie) si executati-l de la cap la coada. Daca merge perfect, treceti la teste mai complexe (minim 4 teste si maxim 7-8). Daca le trece si pe acestea, puteti fi mandri. Legile lui Murphy in programare se aplica in continuare: "Depanarea nu poate demonstra ca un program merge; ea poate cel mult demonstra ca un program nu merge". Totusi, daca programul vostru a mers perfect pe 7-8 teste date la intamplare, exista sanse foarte mari sa mearga pe majoritatea testelor comisiei, sau chiar pe toate.
}
==
***
h2(#concluzii). Concluzii
Probabil nu veti fi de acord cu toate sfaturile date mai sus. E bine insa sa le aplicati. Scopul pentru care ele au fost incluse in aceasta carte este de a ajuta concurentii sa se acomodeze mai usor cu atmosfera concursului. De multe ori, primul an de participare la olimpiada se soldeaza cu un rezultat cel mult mediu, deoarece, oricat ar spune cineva "ei, nu-i asa mare lucru sa mergi la un concurs", experienta acumulata conteaza mult. De aceea, abia de la a doua participare si uneori chiar de mai tarziu incep sa apara rezultatele. Intentia autorului a fost sa va usureze misiunea si sa va dezvaluie cateva din dificultatile de toate felurile care apar la orice concurs, pentru a nu va da ocazia sa le descoperiti pe propria piele. Poate ca aceste ponturi va vor fi de folos.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
