[Citat] eu nu sunt in stare sa scriu/citesc/descifrez nicio linie de cod![](images/smile.gif) |
Efortul este minim pentru a intelege cele de mai sus,
aici este prilejul unic pentru a tine (inca) pasul cu ce fac "baietii" la scoala.
Dupa parerea mea, C++ nu este limbajul didactic bun de intelegere a programarii.
Motivul este acel "zgomot alb" dintre liniile care conteaza. Eu prefer python, caz in care nu este nevoie de compilare... In limbaj uman:
In C++ se scrie ceva intr-un editor, cele scrise se compileaza mai intai (cutie neagra) iar cele compilate se ruleaza. De obicei pustii vin cu "echipamentul de dezvoltat cod gata fur(niz)at" si nu isi fac nici un fel de ganduri despre dependenta creata. Ar fi interesant de stiut in ce cadru dezvolta codul copiii astia.
In Python avem ceea ce este mai usor (pentru inceput), anume avem un "mancator de cod", tiparim o instructiune in interpreterul python si si vedem ce se intampla dupa ea. Se invata doar mai repede, altfel de la un punct conteaza doar gandirea logica, puterea de a separa calculele si a le face in mod optim, apoi structurarea codului.
Iata cum se calculeaza de exemplu in python distanta dinte
7390 si 4444 sa zicem. O sa dau numerele deja sparte in bucati, ca sa ne scapam de ceva birocratic in plus.
def distanta( cifra1, cifra2 ):
"""se calculeaza distanta dintre cele doua cifre
vazute puse pe graful ciclic cu ciclul 0,1,2,3,4,5,6,7,8,9,0,...
"""
# prefer sa ordonez mai bine
d1 = min( [ cifra1, cifra2 ] )
d2 = max( [ cifra1, cifra2 ] )
return min( [ d2-d1, (10+d1) - d2 ] )
In python putem cere direct duppa ce am tiparit cele de mai sus:
print distanta( 2,4 )
print distanta( 4,2 )
print distanta( 2,9 )
print distanta( 2,8 )
In mancatorul de text lucrurile acestea arata asa:
Asa se invata cel mai usor programarea. (Cu un "mancator de linii" = interpreter, nu cu un compiler la mijloc.)
Acum referitor la problema de mai sus.
Putem sa incercam impreuna si sa reproducem *toti* pasii.
In acelasi timp in python si in C++ .
Daca sunt intrebari cu incredere.
Din punct de vedere matematic, punctul nevralgic al programului este aici:
Si cele de mai sus se explica asa:
Cel mai bine pe caz particular.
N=4,
combinatia pe care o vedem (tot "cifru" pentru mine) este 7, 3, 9, 0.
Initializam NrMin cu 41. Imediat va fi mai mic.
Plecam pe rand cu un i de la 0 la 9.
Deci il facem pe rand pe i egal cu 0,1,2,..,9 .
Ceea ce in matematica este inductia (finita), in informatica este un ciclu.
Nu se poate intelege un lucru fara altul. (Dar se poate folosi, toata industria informatica se bazeaza pe faptul ca nu trebuie sa intelegem, ci trebuie sa scriem si sa testam bine. Cei ce inteleg au totusi nervii nesolicitati.)
Este afacerea cu
for(i=0;i<=9;i++)
{
...
}
Daca intre acolade avem *o singura linie* putem omite acoladele,
altfel nu.
Este un stil urat sa ingramadim cat se poate de multe lucruri pe o linie,
daca putem sa le scriem unul sub altul.
Suntem acum in interiorul acestui ciclu.
Ca sa mai variem, sa zicem ca suntem cu i = 6.
Instantaneu intram intr-un ciclu dupa un j de la 0 la 9.
Notatia este inselatoare.
Daca i este cifra care se refera la combinatia
iiii
cifra j se adreseaza tot unei cifre, insa intr-o alta structura.
Anume j este *indexul* din vectorul de aparitii
Apar
care la noi este
1,0,0,1,0,0,0,1,0,1 - unde se corespund pozitiile
0,1,2,3,4,5,6,7,8,9 .
Daca am fi plecat cu 3,6,1,3 in loc de 7,3,9,0, atunci am fi avut:
0,1,0,2,0,0,1,0,0,0 - pe pozitiile
0,1,2,3,4,5,6,7,8,9 .
Acum calculam pe rand distanta de la 7, apoi 3, apoi 9, apoi 0 la acest i=6.
Anume
pentru j=0, si inmultim cu Apar[0] = 1,
pentru j=3, si inmultim cu Apar[3] = 1,
pentru j=7, si inmultim cu Apar[7] = 1,
pentru j=9, si inmultim cu Apar[9] = 1,
in aceasta ordine
si ca sa nu calculam de pomana (optimizare in cod),
am pus conditia
if(Apar[j] && j!=i)
care se adreseaza numai liniei care vine, nu am pus acolade, dar am pus pe linia respectiva cat de mult am putut. (Chestie de gust / stil.)
Ei bine, propun sa rumegam bine impreuna liniile:
if(Apar[j] && j!=i)
Nr += abs(j-i) <= 10 - abs(j-i) ? Apar[j]*abs(j-i) : Apar[j]*(10 - abs(j-i));
stiind ca:
- instructiunea a += b inseamna a = a+b, adica uita-te la a+b, calculeaza asta vazand ce se afla in "sertarele" (registrii) a si b, rezultatul ia-l si baga-l in sertarul a. Pe scurt: a += b inseamna aduna ce e in sertarul a cu valoarea din b.
- instructiunea: <conditie> ? valoareCandConditiaEsteAdevarata : valoareCandConditiaEsteFalsa inseamna ca intai se evalueaza conditia <conditie>, dam de True sau False in C++, depinzand de acest lucru luam valoarea ...
Aici se intelege foarte bine diferenta dintre olimpiada de matematica si cea de informatica. In matematica nu conteaza "drumul scurt" (prea mult), dar argumentarea "drumului" este esentiala. Nici un fel de caz nu trebuie lasat la o parte. In informatica "scriem formula", suntem pe partea pragmatica si lasam apoi formula sa fie testata pe cazurile alese de cei ce testeaza.
(La noi putem sa le programam pe toate... Sunt putine.)
Conteaza ca *rezultatul sa fie bun* .
Probabil ca formula pe care o scriem nu e buna pentru N = 172, dar asta nu se testeaza.
Nu spun ca este bine sau rau, este "alta stiinta", dar intersectia este de asa natura incat
- un matematician care stie sa programeze are un atu puternic in cercetare (in principiu tot ce se poate face cu hartie si creion e daja facut).
In
- un informatician care stie matematica (rigoare, logica, izolartea formulei care trebuie in forma buna) are un atu puternic in gasit loc de munca si facut munca mai putin bruta din informatica. Este o munca bine platita de obicei. (Cei ce vor deja toata viata sa schimbe culoarea unui camp dintr-o masca - sau asa ceva - nu trebuie neaparat sa invete si matematica. Dar vor trebui sa invete o droaie de programe de schimbat culoarea in viata lor de informaticieni. Si cei tineri o vor schimba mereu mai repede. Insa cei ce vor sa programeze jocuri pe calculator e bine sa inteleaga fizica, miscari liniare dupa o ecuatie diferentiala cu derivate partiale implementata folosind metode de aproximare bune, trebuie sa inteleaga miscarile in spatiu, in principiu grupul O(3), si sa foloseasca asa ceva cum trebuie. Inca trebuie stapanite bibliotecile standard si cele ale firmei proprietarea in care are omul sansa sa lucreze.)
Bun, ce facem mai departe?
P.S. A trebuit sa trec la font tiny (mic de tot), altfel nu mi se compileaza pe pagina, latimea este depasita. Rog a se folosi lupa (rotita de la mouse trebuie miscata in timp ce se apasa Control).