Analiza
complexitatii algoritmilor este o activitate importanta pentru realizarea unor
programe eficiente. Un algoritm care se executa in timp liniar este, de obicei,
mult mai rapid decat unul care se executa in timp patratic. In general, timpul
de executie al unui algoritm se determina in raport cu dimensiunea n
a datelor de intrare. Intrucat determinarea unei formule pentru timpul de executie
care sa depinda de n nu este
ceva usor de realizat, ar prinde foarte bine daca aceasta activitate ar putea
fi automatizata. In aceasta problema vom considera numai programe avand o structura
simpla, pentru care timpul de executie se poate determina exact. Structura acestor
programe este definita in continuare:
Program
:=
begin <Secventa
de instructiuni> end
Secventa
de instructiuni
:=
loop <x>
<Secventa de instructiuni> end
sau
op
<x> <Secventa de instructiuni>
sau
break <Secventa
de instructiuni>
sau
continue
<Secventa de instructiuni>
sau
<Sirul
vid>
x
:=
n
sau
<Numar
natural>
Timpul de executie
a unui astfel de program se calculeaza dupa cum urmeaza:
1. Executia unei instructiuni op
dureaza atatea unitati de timp cate indica parametrul x
al acesteia (care poate fi un numar natural mai mic sau egal cu 2.000.000.000
sau variabila n)
2. Secventa de instructiuni inchisa in cadrul unei instructiuni de tip loop
este executata de atatea ori cate indica parametrul acesteia (care poate fi
un numar natural mai mic sau egal cu 2.000.000.000
sau variabila n).
3. Timpul de executie al unei secvente de instructiuni este egal cu suma timpilor
de executie a instructiunilor din cadrul secventei.
4. Instructiunea break determina
iesirea din cadrul buclei loop
curente (instructiunile de dupa break
din cadrul buclei nu mai sunt executate).
5. Instructiunea continue determina
intoarcerea la inceputul buclei loop
curente si trecerea la urmatoarea iteratie a acesteia (instructiunile de dupa
continue din cadrul buclei curente
nu mai sunt executate).
6. Daca se intalnesc instructiuni break
sau continue in afara vreunei
bucle loop, acestea vor fi ignorate.
Timpul total de
executie este un polinom ce depinde de variabila n.
Date de intare
Fisierul de intrare
complex.in va contine un program
scris in conformitate cu regulile definite mai sus. In fisier pot aparea oricate
spatii, tab-uri sau linii goale.
Date de iesire
In fisierul de
iesire complex.out veti afisa
timpul de executie al programului. Acesta va fi un polinom in variabila n.
Polinomul va fi scris sub forma: "an^21+bn^20+..+tn^2+un+v",
unde a, b,
.., u, v
reprezinta coeficientii polinomului. Sirul afisat nu va contine spatii, iar
termenii care au coeficientul egal cu 0
vor fi omisi. In cazul gradului 1,
va fi afisat "n", in
loc de "n^1", iar in
cazul gradului 0 va fi afisat
doar coeficientul, nu si "n^0".
In cazul in care coeficientul unui termen este egal cu 1,
iar gradul este mai mare decat 0,
nu se va afisa coeficientul. In cazul in care toti coeficientii sunt 0,
afisati sirul "0" (fara
ghilimele).
Restrictii si
precizari
Nivelul de imbricare
a buclelor loop va fi cel mult 20.
Dimensiunea maxima a unui fisier de test este de 1000
de octeti.
Valorile coeficientilor obtinuti nu vor depasi 2.000.000.000.
Afisati caracterul "linie noua" la sfarsitul sirului ce descrie polinomul.
Exemplu
complex.in
complex.out
begin loop
n loop 3 loop n
op 20
end end end
loop n op 3 break end
loop n loop n
op 1
break
end end
end
60n^2+n+3
As.drd.ing.
Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare mugurel_ionut@yahoo.com