PDA

Visualizza la versione completa : [c++] l’algoritmo del massimo e minimo simultanei


banino84
10-02-2015, 16:49
Ragazzi qualcuno mi saprebbe spiegare questo algoritmo e mi potrebbe dire come implementarlo in c++ con la tecnica del divide et impera?
grazie

oregon
10-02-2015, 17:05
http://www.di.unito.it/~deligu/didattica/aa0405/I2M/docs/DivideEtImpera.pdf

banino84
11-02-2015, 09:41
Mi sono implementato l'algoritmo del mergesort. L'algoritmo dei minimi e massimi simultanei dovrebbe fare questo:
1. SE LA DIMENSIONE DEL VETTORE NON SUPERA 2,ALLORA CALCOLA DIRETTAMENTE, MEDIANTE UNUNICO CONFRONTO, IL MINIMO E IL MASSIMO

2. ALTRIMENTI, DIVIDI IL VETTORE IN DUESOTTOVETTORI DELLA STESSA DIMENSIONE,CALCOLA RICORSIVAMENTE IL MINIMO MIN1E ILMASSIMO MAX1DEL PRIMO SOTTOVETTORE PRIMO SOTTOVETTORE E ILMINIMO MIN2E MAX2DEL SECONDO SECONDOSOTTOVETTORE SOTTOVETTORE

3. DETERMINA IL MINIMO E IL MASSIMO DEL VETTORE VETTORECOMPLESSIVO CONFRONTANDO MIN1 CON MIN2 E COMPLESSIVO CONFRONTANDO MIN1 CON MIN2 EMAX1 CON MAX2 MAX1 CON MAX2

come potrei modificare il codice sottostante per avere un algoritmo per il i min e massimi simultanei?



/**
Metodo MergeSort
*/




#include <string>
#define MAX 10
using namespace std;
typedef int start;
typedef int end;
typedef int Item;




/*
* Ricomponi i risultati ottenuti al passo precedente ed ottieni la soluzione complessiva
* (impera)
*/




void impera(Item a[], start left, int center, end right) {
Item* aux = new int[right + 1];
int i,j;
for (i = center+1; i > left; i--)
aux[i-1] = a[i-1];

for (j = center; j < right; j++)
aux[right+center-j] = a[j+1];

for (int k = left; k <= right; k++)
if (aux[j] < aux[i])
a[k] = aux[j--];
else
a[k] = aux[i++];
delete [] aux;
}




/*
* Dividi il vettore in due sottovettori di dimensione inferiore all'originale ed
* esegui l'algoritmo ricorsivamente sui due sottovettori (divide)
*/


void divide(Item a[], start inizio,end fine) {

if (inizio<fine) {
int media = (inizio+fine)/2;
divide(a, inizio, media);
divide(a, media+1, fine);
impera(a, inizio, media, fine);
}

}

Loading