www.didactic.ro

[raduv]

Problema stop Runda 4

Rezolvare:
P1.k<--0;
P2.k<--k+1
P3.t<--k,ok<--true;
pentru i=1,n executa
t<--t+i ;daca [nu se trece de stopul i] ok<--false;
P4.daca ok=true atunci scrie k stop. altfel mergi la P2

Complexitatea:Pasul P3 se executa in O(n).
Constanta are aceeasi valoare k=cmmmc(1,2,3,4,5,6,7,8,9,10)
deoarece dupa aceasta valoare configuratia se repeta.
Rezulta k*n.

Concluzie: rezolvarea este la fel de puternica ca si
a solutiei comisiei, fara programare dinamica.

Radu Visinescu