METODE DE SORTARE

METODE DE SORTARE

1. Sortarea prin selectarea     minimului (maximului):

#include <iostream.h>

main()

for(i=0;i<n-1;i++)

man=a[k];

a[k]=a[i];

a[i]=man;

}

for(i=0;i<n;i++)

cout<<a[i]<<endl;

Pag 48 si 49pana la bule

2. Metoda Greedy (metoda rucsacului)

Trebuie sa golim o incapere plina cu tot felul de obiecte de diferite marimi, greutati si chiar utilitati. Ni se cere sa golim repede camera, din cat mai putine mutari. Avem la dispozitie doar un rucsac destul de incapator, dar care nu "tine" mai mult de 30 kg. Obiectele au fost cantarite si pe fiecare este inscrisa greutatea (in kilograme): 7, 8, 10, 25, 5, 7, 8, 10,9,5, 6, 7, 25, 5.

Algoritmul:

inceput rucsac

aloca G[100]

repeta citeste n pana cand n<100

pentru i=1,n executa citette G[i]

sfarsit pentru

ordoneaza G//prelucrare nerezolvata

R 0 // golim rucsacul

m 0

i 1

repeta

daca G[i]<=30-R

atunci

bloc

R ← R + G[i]

i ← i+1

sfarsit bloc

altfel

bloc

m ← m+1

R ← 0

sfarsit bloc

sfarsit daca

pana cand i>n

m ← m+1

scrie m //numarul de rucsacuri

sfarsit rucsac

//sortp48m.cpp

#include<iostream.h>

void main()

while(n>100 || n<0);

cout<<'dati greutatile celor '<<n<<' obiecte:'<<endl;

for(i=0;i<n;i++)

cin>>G[i];

//ordonam vectorul ca sa putem aplica algoritmul (algoritmul de sortare e metoda minimului)

for(i=0;i<n-1;i++)

man=G[k];

G[k]=G[i];

G[i]=man;

//algoritmul propriuzis

R=0;

m=0;

i=0;

do

else

}while (i<n);

m=m+1;

cout<<'numarul de rucsacuri='<<m;

TEME pag 49

1.a. Mai multi elevi s-au documentat asupra evenimentelor istorice desfasurate in Europa in perioada Evului Mediu si le-au prezentat la ora de istorie in urmatoarea ordine:

838 771 584 1108 862 496 728

Desi a apreciat munca elevilor, profesorul nu a fost multumit de prezentare. De ce?

Evenimentele trebuie prezentate in ordine cronologica deoarece pot arata cauza - efect.

Programul este ordonarea unui vector.

#include<iostream.h>

void main()

man=evenimente[k];

evenimente[k]=evenimente[i];

evenimente[i]=man;

cout<<endl<<'evenimentele ordonate cronologic: '<<endl;

for(i=0;i<n;i++)

cout<<evenimente[i]<<' ';

1.b. La sfarsitul fiecarei luni, directorul unei firme comerciale afiseaza o lista cu incasarile realizate de fiecare dintre agentii sai de vanzari, in ordinea in care acestia au fost angajati. Agentii de vanzari sunt nemultumiti de modul de afisare intrucat ar dori sa-si aprecieze cu usurinta nivelul incasarilor personale fata de incasarile celorlalti colegi. (Construiti si un exemplu numeric. )

Initial:

Gigi 48

Migi 68

Relu 56

Ordonam in functie de suma:

Migi 68

Relu 56

Gigi 48

#include<iostream.h>

#include <string.h>

typedef struct

agent_vanzari;

void main()

for(i=0;i<n-1;i++)

man=agent[k];

agent[k]=agent[i];

agent[i]=man;

cout<<endl<<'datele aranjate cum vor agentii:'<<endl;

for(i=0;i<n;i++)

cout<<agent[i].nume<<' '<<agent[i].suma<<endl;

1.c. Operatoarele de la serviciul Informatii trebuie sa gaseasca intr-un timp scurt numarul de telefon al unui abonat cunoscand numele si adresa acestuia. Un informatician distrat a realizat o agenda telefonica in care numerele de telefon sunt atezate in ordine crescatoare. Operatoarele sunt nemultumite. De ce?

Se ordoneaza in functie de nume.

E mai complicat sa ti'l fac. Trebuie pointeri.

1.d. La un club sportiv au inceput inscrierile pentru echipa de baschet. Desi sunt inscrisi doar cei cu inaltimea peste 1,70 m, numarul candidatilor este mult mai mare decat numarul locurilor. Cum procedeaza antrenorul pentru a-i alege cu usurinta pe cei mai dotati candidati.

Ii ordoneaza in functie de inaltime: