Creeaza.com - informatii profesionale despre
TehnologieAfaceriScoalaDidacticaLegislatieFamilie


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » scoala » informatica
Algoritmi echivalenti

Algoritmi echivalenti


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

creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.