Algoritmi echivalenti
Doi algoritmi se numesc echivalenti, daca pentru orice set de date de intrare, introdus in ambii algoritmi, se obtine, de catre ambii algoritmi, acelasi set de date de iesire.
Exemplul 1 : Se da n numar natural nenul si apoi se da p numar prim.
La ce putere apare p in descompunerea in factori primi a numarului n ?
|
Algoritm 1 |
Algoritm 2 |
|
Citeste n ( natural nenul ) Citeste p ( prim ) nr cat timp n%p=0 executa nr nr+1 n [n/p] Scrie nr |
Citeste n ( natural nenul ) Citeste p ( prim ) nr daca n%p=0 atunci Executa nr nr+1 n [n/p] pana cand n%p¹ Scrie nr |
|
Algoritm 1 |
Algoritm 2 |
||
|
Caz |
Set de date de intrare |
Set de date de iesire |
Set de date de iesire |
|
p este factor prim al lui n |
n=120, p=2 |
nr=3 |
nr=3 |
|
p nu este factor prim al lui n |
n=120, p=7 |
nr=0 |
nr=0 |
Concluzie : cei doi algoritmi sunt echivalenti
Exemplul 2 : Se da n numar natural.
Care este valoarea produsului tuturor cifrelor pare din n ?
|
Algoritm 1 |
Algoritm 2 |
|
Citeste n ( natural ) p cat timp n>0 executa daca (n%2=0) atunci p p*(n%10) n [n/10] Scrie p |
Citeste n ( natural ) p Executa daca (n%2=0) atunci p p*(n%10) n [n/10] pana cand n=0 Scrie p |
|
Algoritm 1 |
Algoritm 2 |
||
|
Caz |
Set de date de intrare |
Set de date de iesire |
Set de date de iesire |
|
n este nenul |
n=12324 |
p=24 |
p=24 |
|
n este nul |
n=0 |
p=1 |
p=0 |
Concluzie : cei doi algoritmi NU sunt echivalenti .
Corect este algoritmul 2.
Exemplul 3 : Se dau a,b numere intregi. Sa se afiseze, in ordine crescatoare, toate numerele intregi ce apartin intervalului [a,b] daca acest interval exista .
|
Algoritm 1 |
Algoritm 2 |
Algoritm 3 |
|
Citeste a,b ( intregi ) Pentru i a,b executa Scrie i,¢ ¢ |
Citeste a,b ( intregi ) i a cat timp i£b executa Scrie i,¢ ¢ i i+1 |
Citeste a,b ( intregi ) i a Executa Scrie i,¢ ¢ i i+1 pana cand i>b |
|
Algoritm 1 |
Algoritm 2 |
Algoritm 3 |
||
|
Caz |
Set de date de intrare |
Set date de iesire |
Set date de iesire |
Set date de iesire |
|
a<b |
a=13, b=20 | |||
|
a=b |
a=13, b=13 | |||
|
a>b |
a=13, b=8 | |||
Concluzie : sunt echivalenti algoritmii 1 si 2 ; NU sunt echivalenti algoritmii 1 si 3 respectiv 2 si 3
Corecti sunt doar algoritmii 1,2
Exemplul 4 : Se dau a,b numere naturale nenule, cu a£b
Cate numere pare sunt in intervalul [a,b] ?
|
Algoritm 1 |
Algoritm 2 |
Algoritm 3 |
|
Citeste a,b ÎN*, a£b) nr pentru i a,b executa daca i%2=0 atunci nr nr+1 Scrie nr |
Citeste a,b ÎN*,a£b) nr i a cat timp i£b executa daca i%2=0 atunci nr nr+1 Scrie nr |
Citeste a,b ÎN*, a£b) nr [b/2]-[(a-1)/2] scrie nr |
|
Algoritm 1 |
Algoritm 2 |
Algoritm 3 |
||
|
Caz |
Set de date de intrare |
Set date de iesire |
Set date de iesire |
Set date de iesire |
|
a-par, b-par |
a=12, b=16 |
Nr=3 |
Nr=3 |
Nr=3 |
|
a-par, b-impar |
a=12, b=19 |
Nr=4 |
Nr=4 |
Nr=4 |
|
a-impar, b-par |
a=13, b=16 |
Nr=2 |
Nr=2 |
Nr=2 |
|
a-impar, b-impar |
a=13, b=19 |
Nr=3 |
Nr=3 |
Nr=3 |
Concluzie : sunt echivalenti algoritmii : 1 si 2, 1 si 3, 2 si 3
Algoritmul 3 este cel mai eficient deoarece numarul de operatii executate de algoritm nu depinde de dimensiunea intervalului. Acesta este algoritmul IDEAL pentru rezolvarea problemei date.
|
Politica de confidentialitate |
 .com |
Copyright ©
2023 - Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational. |
| Termeni si conditii |
| Contact |
| Creeaza si tu |
