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 |
60n^2+n+3 |
Timp maxim de executie/test: 0.1 secunde
As.drd.ing.
Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare
mugurel_ionut@yahoo.com