[Algoritmo] Prova di esame 2

[first100]

Sia A un array formato da n numeri interi positivi consecutivi e sia S uguale alla sommatoria di tutti gli elementi di A. Progettare un algoritmo ottimo che dati A,n,S e un indice i>1 e i
Qui non capisco come procedere , ho già A ordinato con numeri consecutivi i-esimo elemento richiesto non è A?

Grazie

[onlyReferee]

Ciao first100
Array con numeri consecutivi ed array ordinato con numeri consecutivi sono due cose diverse. Ad esempio l'array $A = [ 2, 3, 4, 5, 6 ]$ è ordinato con numeri consecutivi e l'array $A = [ 3, 4, 5, 6, 2 ]$ è invece con numeri consecutivi (ma non ordinato).
Per la scrittura dell'algoritmo ci sto ragionando anche io.
--------------------------------------------------------------------
Risolto, ho trovato due metodi possibili.
Il primo è quello più semplice ed elementare ma allo stesso tempo meno efficiente (complessità $\Theta(n)$, dove $n$ è la dimensione dell'array): scansioni tutto il tuo array e determini il valore minimo dello stesso, che indichiamo con $\min(A)$, dove $A$ è chiaramente il nostro array. Alla fine è sufficiente restituire $min(A) + i$.
Il secondo è molto elegante, forse meno intuitivo del primo ma sicuramente molto più efficiente quando l'array aumenta la propria dimensione. Ti do un indizio senza svelarti per ora la soluzione finale: grazie a Gauss sappiamo che $\sum_{j = 1}^n j = \frac{n \cdot (n + 1)}{2}$ (ho usato $j$ semplicemente per non confonderci col nostro $i$).

[first100]

Con quella formula dati n elementi non ordinati l' n-esimo è il più grande e quindi mi evito di ordinare gli elementi. E' così?

[vict85]

Sono \(\displaystyle n \) numeri consecutivi di minimo \(\displaystyle m \). Pertanto hai che \(\displaystyle S = \sum_{j=0}^{n-1} (m+j) = nm + \sum_{j=0}^{n-1} j = nm + \frac{n(n-1)}{2} \). Siccome possiedi \(\displaystyle n \) e \(\displaystyle S \) puoi ricavare \(\displaystyle m \). A quel punto aggiungi i-1 (\(\displaystyle m \) è il primo elemento).