Dividi e necessario Algoritmo di chiarimento necessario

Naviga le tue risposte
1

Ho un compito a casa per una classe data / algoritmo di dati. Il compito è di prendere una matrice non ordinata di dimensione n (esempio: [-8, 3, 2, -3, 3, 1, -3, -5]), e noi abbiamo per usare un dividi e conquista l'approccio, w / ricorsione, per trovare la sottosequenza con il prodotto più grande.

È la stessa di questa domanda: link tranne che in sostituzione della somma, la mia domanda cerca un prodotto.

Capisco che un approccio D & C è desiderabile perché ha complessità temporale log(n) (dimezzamento) invece di n^2 (ciclo nidificato). Quello su cui sono poco chiaro è: l'intera funzione dovrebbe essere una chiamata ricorsiva? O è come:

  1. Dividi a metà.
  2. Funzione ricorsiva per trovare i prodotti più grandi e più piccoli (bc neg * neg) della metà sinistra
  3. Lo stesso ma la metà destra
  4. Lo stesso ma per il "bordo" del punto medio e metà sinistra
  5. Lo stesso ma per il "bordo" del punto medio e della metà destra
  6. Confronta tutti i valori

Questo è fatto con if / else e allora chiamate ricorsive, o è la stessa funzione ricorsiva con se / else è al suo interno? C'è un modo metodico per provare ad affrontare questo programma? Mi sento molto perso.

    
posta HC_ 24.09.2014 - 18:03
fonte

1 risposta

1

L'algoritmo divide and conquer ha 3 passaggi per ogni livello:

  1. Una chiamata ricorsiva nella metà sinistra.
  2. Una chiamata ricorsiva sulla destra la metà.
  3. Calcola la somma mista massima.

I passaggi 1 e 2 sono ricorsivi, chiamano nuovamente la funzione usando i nuovi punti finali. Il passaggio 3 non lo è, utilizza solo il fatto che la somma / prodotto deve includere i valori del bordo per fare solo n iterazioni. Ad esempio, se disponi di [1 2 3 4 5 6], sa che una somma mista / prodotto deve avere 3 e 4, e può semplicemente controllare 123, 23, 3 e 4, 45, 456, e quindi combinare i due in ottieni il massimo della somma / prodotto misto.

Ora confronti i risultati dei passaggi 1, 2 e 3 e il più grande è la somma / prodotto massimo possibile.

EDIT: alcuni pseudo code semplificati:

function maxProd (array)

A = maxProd (array [prima metà])

B = maxProd (array [seconda metà])

C = Calcola il prodotto massimo che contiene un elemento da entrambi i metà

return max (A, B, C)

    
risposta data 24.09.2014 - 18:28
fonte

Leggi altre domande sui tag

Progettazione di oggetti modali Java scrittura di test funzionali / di integrazione per python