Passaggi minimi per rendere tutti gli elementi uguali

7

Dato un array A di N interi positivi (N < = 20), abbiamo la seguente operazione. Per ogni due elementi non uguali consecutivi, possiamo sostituire il numero maggiore con il valore assoluto della differenza tra questi due numeri. Continuiamo ad usare questa operazione fino a quando tutti gli elementi sono uguali. Trova un modo per rendere tutti gli elementi uguali con un numero minimo di passaggi (numero di operazioni come descritto)

Ad esempio, A = 9, 6, 15, 12. Il numero minimo di passaggi è 5 (corretto per Pieter B).

9 6 9 12
9 6 9 3
9 6 3 3
3 6 3 3
3 3 3 3

Sto pensando ad ogni passaggio, possiamo scegliere l'elemento più grande e sostituirlo con la differenza con il suo vicino più piccolo. Tuttavia, fallisce per il test 1, 3, 2. Fallisce anche se scegliamo di sostituire l'elemento più grande con la differenza con il suo vicino più grande; ad esempio, 3, 8, 4.

C'è un modo per risolvere questo problema tranne la forza bruta? Se sto usando la forza bruta, sta sostituendo l'elemento più grande la scelta giusta?

Grazie.

    
posta dh16 16.02.2017 - 23:27
fonte

1 risposta

0

In realtà, può farlo come problema di fork / join. Nel tuo esempio, stai procedendo in modo iterativo. Potresti provare a suddividere i dati in modo ricorsivo, riducendo ogni parte, eseguendo un'operazione di unione tra le parti. Il tuo esempio precedente può essere risolto:

9 6 - 3 12

3 6 - 3 12

3 6 - 3 9

3 3 - 3 9

3 3 - 3 6

3 3 - 3 3

Quale non è migliore.

Anche se questo non avrà sempre meno "passi", se puoi eseguire passi in parallelo, può essere molto più efficiente. Se abbiamo due thread, in modo che possiamo fare due confronti alla volta, otteniamo:

9 6 - 3 12

3 6 - 3 9

3 3 - 3 6

3 3 - 3 3

Quando lo spazio del problema diventa più grande e / o otteniamo più "thread" questa soluzione diventa più efficiente.

Con il tuo piccolo spazio di problemi (20 max), un'implementazione effettiva probabilmente avrebbe troppi sovraccarichi per battere il caso iterativo, in termini di tempo.

Il che ci lascia chiedendo, "Cos'è esattamente un passo? (Ci scusiamo per la scarsa formattazione)

    
risposta data 17.02.2017 - 07:57
fonte

Leggi altre domande sui tag