Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » referate » 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 ?

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.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



PROIECT SISTEMUL DE OPERARE LINUX
ETAPELE DE REALIZARE A UNUI SISTEM INFORMATIC IDENTIFICAREA CERINTELOR SISTEMULUI ( MODELUL AFACERILOR )
Tiparirea textului si a graficii in Visual Basic
Notiunea de sistem, sistem cibernetic
ARHITECTURI DE COMANDA NUMERICA FOLOSITE IN SISTEMELE DE ACTIONARI ELECTRICE
Monitor 3D multiutilizator cu detectare a pozitiei capului avand laser RGB ca sursa de lumina
Caracteristicile celor patru tipuri de sisteme informationale
Date si informatii



Termeni si conditii
Contact
Creeaza si tu