Nome:

trovastringhediradicedienneelementi
Download:

Codice sorgente (in C++) Eseguibile (compilato per Linux su Pentium I) Eseguibile (compilato per Win 2000 su Pentium III)
Retroscena matematico: Data una sequenza qualsiasi di n numeri, esiste almeno un modo per togliere alcuni elementi fino a renderla una sequenza monotona (crescente o decrescente) con almeno radice di n elementi. Che io sappia esistono due dimostrazioni di questo fatto: l'algoritmo stesso di questo programmino (che magari qualcuno aveva scoperto prima di me, ma che non ho trovato in giro) ed un'altra che utilizza alcune proprieta' degli ordinamenti.
Funzionamento: Data una serie S=(s1, s2, s3... sn^2), "tiriamone fuori" una stringa T1 tale che:

1- il primo elemento sia il primo elemento di S (s1)

2- il secondo sia il primo elemento che incontriamo, leggendo S da sinistra a destra, maggiore di s1 (chiamiamolo sk)

3- il terzo sia il primo elemento di S, leggendo la serie da sinistra a destra e partendo dall'elemento successivo a sk, maggiore di sk...

e cosi' via. Abbiamo formato cosi' una nuova stringa (crescente), ed S ha "perso" alcuni elementi. Ripetiamo il procedimento con altre stringhe T2 (che partira' dal primo degli elementi rimasti ad S), T3... finche' gli elementi di S non saranno finiti.

Ci troviamo quindi con m stringhe crescenti. Se almeno una di queste ha n o piu' elementi, abbiamo trovato la stringa che cercavamo.

Altrimenti, siccome il numero totale di elementi e' n^2, m>n.

Sia sh l'ultimo elemento (il maggiore) dell'ultima stringa (Tm) che abbiamo creato: togliamo a tutte le stringhe T1...Tm-1 gli elementi sj con j>h (ovvero tutti quelli che, nella sequenza S iniziale, si trovavano piu' a destra di sh). Ripetiamo lo stesso procedimento con l'ultimo elemento della sequenza Tm-1 (cioe' sottraiamo dalle sequenze T1...Tm-2 gli elementi che in S si trovavano alla sua sinistra), e cosi' via con tutti gli ultimi elementi delle stringhe, da destra a sinistra.

Una volta compiuto questo procedimento, dalle nostre stringhe crescenti T1...Tm cosi' modificate prendiamo gli ultimi (maggiori) elementi ed inseriamoli in una nuova sequenza V, rispettando l'ordine delle sequenze di provenienza (il primo elemento di V sara' l'ultimo di T1, l'ultimo sara' l'ultimo di Tm: notiamo che questi elementi avranno tra di loro lo stesso ordinamento che avevano in S).

Questa sequenza V ha m elementi, ed m>n. Inoltre e' decrescente.

Che sia sempre decrescente, si dimostra perche', se prendiamo in considerazione l'elemento massimo di una data serie Tl, ipotizzando per assurdo che l'elemento massimo della serie Tl+1 (alla sua destra) sia maggiore, ci accorgiamo che allora, per il modo in cui abbiamo creato le serie, avrebbe fatto parte di tl stessa, invece che di Tl+1.

Similmente si dimostra che ogni sequenza T1...Tm aveva almeno un elemento quando abbiamo creato V.

Note tecniche: - Per "crescente" si intende che ogni elemento e' maggiore O UGUALE del precedente. L'algoritmo sopra descritto varrebbe anche per stringhe strettamente crescenti/decrescenti, ma allora nella sequenza iniziale non dovrebbero esserci due elementi uguali.

- Questo programmino da' sempre almeno una sequenza crescente o decrescente "interessante". Spesso le da' entrambe. Se ne da' una sola, ad esempio, crescente, NON SIGNIFICA che non ne esistano di decrescenti, ne' che non esistano altre crescenti. Inoltre le sequenze date sono "buone", ma non sono per forza quelle con piu' elementi. Probabilmente la stringa decrescente, se viene data, e' veramente la piu' lunga che esista, ma non ho verificato.

- Inserire tanti elementi uno dopo l'altro e' noiso: si possono inserire direttamente tutti insieme, separati da uno spazio.

- Il codice sorgente non e' commentato: i pochi commenti sono pezzi di codice poi "aboliti". Me ne scuso, ma e' palloso mettere commenti in un codice che nessuno leggera'.