Algoritmo Divide et Impera

[g0t3nk5]

http://img822.imageshack.us/img822/3852/algoritmi.jpg potete consigliarmi come sviluppare l'algoritmo?? Con la tecnica del divide et impera non ho proprio idee di come procedere in quanto ad esempio in un vettore di quattro elementi 1, 3, 5, 7 dividendo il problema in due parti 1, 3 e 5, 7 non posso risolvere il secondo sottoproblema non conoscendo la soluzione del primo sottoproblema (in quanto ad esempio il terzo elemento del vettore B dovrebbe essere 4, ovvero la soluzione del primo sottoproblema +5).

[Gin&&Tonic]

Se ho capito bene la traccia , la soluzione è questa:


public static int AssegnaValore(int[] a, int indice){

if(indice==0) return a[0];

return a[indice]+AssegnaValore(a,indice-1);

}


public int[] creavettore(int[]a){
int[] b=new int[a.length];
for(int i=0;i<b.length;i++)
b[i]=AssegnaValore(a,i);

return b;
}



scusa non avevo letto che ti serviva per Pascal, comunque la logica è quella.

[g0t3nk5]

Grazie per la risposta ma il problema è che l'algoritmo deve essere di tipo divide et impera: http://it.wikipedia.org/wiki/Divide_et_impera_%28informatica%29

[Wing_Zero]

Grazie per la risposta ma il problema è che l'algoritmo deve essere di tipo divide et impera: http://it.wikipedia.org/wiki/Divide_et_impera_%28informatica%29

Il Pascal (volutamente) non lo conosco. Svilupperò l'esempio in un metalinguaggio simil-pascal. Poi sta a te implementarlo.
Questo cmq è uno dei classici (semplici) problemi risolvibili con l'argoritmo divide et impera.

I passi sono i seguenti:
1) Dividi l'array in sottoarray fino ad arrivare al caso singolo: array di 1 elemento
2) applichi la definizione del caso base
3) ricorsivamente riapplichi la definizione ai casi precedenti.

In pratica:
New=[];
A=1,3,5,7
int last =0;

Procedura DivImp(A):
begin:
if(lunghezza(A)==1)
begin
Append(New, last+A[1]);
last=last+A[1]
end
else
DivImp[A0....An/2]; //parte sinistra dell' array A
DivImp[An/2+1....An]; //parte destra dell'array A
end

New[] è l'array ordinato come da consegna.

Un consiglio, quando dici: "non posso risolvere il secondo sottoproblema non conoscendo la soluzione del primo sottoproblema" sembra che tu non abbia capito molto bene come funziona la ricorsione. Riflettici su.

Infine La complessità in tempo è proporzionale al prodotto tra il numero di partizioni e la dimensione delle stesse. Si risolve con una semplice equazione differenziale.

Se ti interessa passa qui a casa ^^

Ciao

Wing

[g0t3nk5]

Grazie.