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.