Intervista di programmazione: su array ordinati, prova dell'algoritmo

Naviga le tue risposte
3

Quella che segue è una domanda dell'intervista di programmazione: dati 3 matrici ordinate. Trova (x, y, z), (dove x è dal primo array, y è dal secondo array e z è dal terzo array), tale che Max (x, y, z) - Min (x, y, z) è minimo Questa domanda è discussa qui: link

Una possibile soluzione discussa nella pagina della carriera è la seguente: "Prendi tre puntatori, ognuno al primo elemento della lista, poi trova il minimo di essi, calcola max (xyx) -Min (xyz). meno che fino ad ora risulta modificarlo, incrementa il puntatore dell'array che contiene il minimo di essi "

La mia domanda è, come possiamo dimostrare la correttezza di questo algoritmo? In caso contrario, possiamo arrivare a casi in cui l'algoritmo non riesce. E se è così, qual è un algoritmo corretto per risolvere questo problema con la prova.

    
posta Romonov 17.03.2013 - 20:30
fonte

2 risposte

1

Consente di chiamare le matrici ordinate A 1 , A 2 , A 3 . Abbiamo tre indici i 1 , i 2 , i 3 . Vogliamo trovare una tripla (i 1 , i 2 , i 3 ) tale che max (A 1 [i 1 ], A 2 [i 2 ], A 3 [i 3 ]) - min (A 1 [i 1 ], A 2 [i 2 ], A 3 [i 3 ]) è minimo. All'inizio i 1 = i 2 = i 3 = 0.

Un modo possibile è provare tutte le triple (i 1 , i 2 , i 3 ) per 0 < = i 1 < A 1 .lenght, 0 < = i 2 < A 2 .lenght, 0 < = i 3 < A 3 .lenght. Ma molte di quelle triple non saranno necessarie per controllare.

Senza perdita di generalità (questo è solo per facilitare il parlare di matrici) lascia A 1 [i 1 ] < = A 2 [i 2 ] < = A 3 [i 3 ]. Faremo un incremento in questo blocco.

Non c'è senso provare i tripli (j, i 2 , i 3 ) per j < i 1 , perché gli array sono ordinati e A 1 [j] < = A 1 [i 1 ] che è minimo Facciamo finta di aver già provato tutti questi (j, i 2 , i 3 ).

Non c'è senso provare (i 1 , i 2 , j) per j > i 3 perché A 3 [i 3 ] < = A 3 [j].

Provando le triple (i 1 , j, i 3 ) per arbitrario j possiamo andare peggio (il minimo sarà minore o uguale e il massimo sarà più alto o uguale ).

Abbiamo provato indici inferiori a i 1 , i 2 , i 3 . Abbiamo ragionato tripli (j < i 1 , i 2 , i 3 ) e (i 1 , j , i 3 ) non sono necessari, (i 1 , i 2 , j > i 3 ). Stessi argomenti per (j < = i 1 , k, l = i 3 ). Decrementare i 3 è inutile, come abbiamo provato (in realtà o ragionato) in questa tripla prima di aumentare il terzo indice.

Siamo lasciati ad aumentare i 1 che è l'indice di min nella tripla. Dopodiché la differenza potrebbe peggiorare o A 1 [i 1 + 1 ] non è minimale, ma procediamo allo stesso modo.

risposta data 17.03.2013 - 21:39
fonte
1

L'algoritmo ha come invarianza di ciclo dove conosciamo il valore più piccolo di max(x, y, z) - min(x, y, z) per tutti i possibili valori di x , y o z più piccoli dei valori correnti.

Per iniziare con x , y e z sono il più piccolo possibile, quindi l'invariante è vero all'inizio. Alla fine, x , y e z sono il più grande possibile, quindi coprono tutti i valori possibili e abbiamo la risposta.

Dati alcuni valori di x , y , z , se conosciamo il valore ottimale di max(x, y, z) - min(x, y, z) per valori più piccoli, allora qualsiasi valore migliore richiederebbe un incremento di x , y o% % co_de.

Se non incrementiamo il minimo di questi, ogni valore maggiore di z , x o y può solo aumentare il valore di z perché il massimo può solo aumentare e il minimo rimanere lo stesso. Quindi il minimo viene incrementato al valore più piccolo che potrebbe essere migliore di quello che abbiamo, che mantiene invariato il ciclo.

    
risposta data 17.03.2013 - 21:36
fonte

Leggi altre domande sui tag

Perché supportare le dipendenze cicliche? Ci sono casi d'uso validi? Parametri di tipo limitato