Fin da quando ho iniziato a programmare questo è stato qualcosa di cui sono stato curioso. Ma sembra troppo complicato per me anche solo tentare.Algoritmo per trovare il numero successivo in una sequenza
Mi piacerebbe vedere una soluzione.
1, 2, 3, 4, 5 // returns 6 (n + 1)
10, 20, 30, 40, 50 //returns 60 (n + 10)
10, 17, 31, 59, 115 //returns 227 ((n * 2) - 3)
Quello che vuoi fare è chiamato interpolazione polinomiale . Esistono molti metodi (vedere http://en.wikipedia.org/wiki/Polynomial_interpolation), ma è necessario avere un U con limite superiore sul grado del polinomio e almeno su valori di U + 1.
Se si dispone di valori sequenziali, esiste un semplice algoritmo.
Data una sequenza x1, x2, x3, ..., lascia Delta (x) la sequenza di differenze x2 - x1, x3 - x2, x4 - x3, .... Se hai valori consecutivi di un grado n polinomiale, allora l'ennesima iterazione di Delta è una sequenza costante.
Ad esempio, il polinomio n^3:
1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...
Per ottenere il valore successivo, riempire un altro 6 e poi procedere a ritroso.
6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...
La restrizione sul numero di valori sopra assicura che la sequenza non diventi mai vuota durante l'esecuzione delle differenze.
Ya, questa è davvero la base del motore di differenza Babbage. Capire che la derivata Nth è una costante, e semplicemente l'aggiunta ti darà il prossimo numero. – EvilTeach
dispiace deludervi, ma questo non è del tutto possibile (in generale), in quanto vi sono un numero infinito di sequenze per ogni dato k valori. Forse con alcuni vincoli ..
Puoi dare un'occhiata a questo post Everything2, che punta a Lagrange polynomial.
Sì, potrebbero esserci molte possibilità, tuttavia non potresti trovarne una che funzioni per un determinato array e usarla? Non ha necessariamente bisogno di coprire ogni singola possibilità. Ha senso? –
Il problema è che il prossimo numero può essere letteralmente qualsiasi cosa, e puoi capire un modello/polinomio per adattarlo a quel nuovo modello. Ad esempio, c'è uno schema che si adatta, 1, 2, 3, 4, 5, 6, ma anche 1, 2, 3, 4, 5, 5, 5, 5, 5, 5 .. – Larry
Ma voglio dire, basta trovare una formula per montare quei 5 numeri, quindi usala per ottenere il sesto. –
Mi piace l'idea e la sequenza 1 e 2 mi sembra che sia possibile, ma di nuovo non è possibile generalizzare in quanto la sequenza potrebbe completamente andare fuori base. La risposta è probabilmente che non puoi generalizzare, quello che puoi fare è scrivere un algoritmo per eseguire una sequenza specifica conoscendo il (n + 1) o (2n + 2) ecc ...
Una cosa che potresti essere in grado di fare è fare una differenza tra l'elemento i e l'elemento i + 1 e l'elemento i + 2.
per esempio, nel terzo esempio:
10 17 31 59 115
Differenza tra 17 e 10 è 7, e la differenza tra 31 e 17 è 14, e la differenza tra 59 e 31 è 28, e il diffeerence tra 115 e 59 è 56.
Quindi si nota che diventa l'elemento i + 1 = i + (7 * 2^n).
Così 17 = 10 + (7 * 2^0)
E 31 = 17 + (7 * 2^1)
E così via ...
Si può cercare di utilizzare extrapolation. Ti aiuterà a trovare le formule per descrivere una determinata sequenza.
Mi dispiace, non posso dirvi molto di più, dato che la mia formazione matematica è avvenuta qualche tempo fa. Ma dovresti trovare più informazioni nei buoni libri.
Questo tipo di serie di numeri fa spesso parte di "test di intelligenza", che mi porta a pensare nei termini di un tale algoritmo come qualcosa che sta passando (almeno in parte) a Turing Test, che è qualcosa di abbastanza difficile da realizzare.
Formalmente non esiste un valore successivo esclusivo per una sequenza parziale. Il problema come di solito inteso può essere chiaramente indicato come:
Si supponga che la sequenza parziale visualizzata sia sufficiente per vincolare alcune regole di generazione, dedurre la regola più semplice possibile e mostrare il valore successivo generato.
Il problema attiva il significato di "più semplice" e quindi non è particolarmente adatto alle soluzioni algoritmatiche. Può essere fatto se si limita il problema a una determinata classe di moduli funzionali per la regola di generazione, ma i dettagli dipendono da quali forme si è disposti ad accettare.
Il libro Numerical Recipes ha pagine e pagine di veri e propri algoritmi pratici per fare questo genere di cose. Vale la pena leggerlo!
I primi due casi sono facili:
>>> seq1 = [1, 2, 3, 4, 5]
>>> seq2 = [10, 20, 30, 40, 50]
>>> def next(seq):
... m = (seq[1] - seq[0])/(1-0)
... b = seq[0] - m * 0
... return m*len(seq) + b
>>> next(seq1)
6
>>> next(seq2)
60
Il terzo caso richiederebbe risolvendo una funzione non lineare.
Per una funzione arbitraria non può essere eseguita, ma per una funzione lineare come in ciascuno dei vostri esempi è abbastanza semplice.
Hai f(n+1) = a*f(n) + b e il problema è di trovare a e b.
Dato almeno tre termini della sequenza, è possibile farlo (ne occorrono tre perché si hanno tre incognite - il punto di partenza, a e b). Ad esempio, supponiamo di avere f(0), f(1) e f(2).
Siamo in grado di risolvere le equazioni:
f(1) = a*f(0) + b
f(2) = a*f(1) + b
La soluzione per è: (. Ti consigliamo di risolvere separatamente il caso in cui f(0) = f(1) per evitare una divisione per zero)
a = (f(2)-f(1))/(f(1)-f(0))
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0))
Una volta che hai a e b, puoi applicare ripetutamente la formula al valore iniziale per generare qualsiasi termine nel se quence.
Si potrebbe anche scrivere una procedura più generale che funziona quando somministrato eventuali tre punti nella sequenza (ad esempio 4 °, 7 °, 23 °, o altro). . . questo è solo un semplice esempio.
Ancora una volta, tuttavia, abbiamo dovuto formulare alcune ipotesi su quale forma avrebbe avuto la nostra soluzione. . .in questo caso assumerlo per essere lineare come nel tuo esempio. Si potrebbe considerare un polinomio più generale, ad esempio, ma in tal caso sono necessari più termini della sequenza per trovare la soluzione, a seconda del grado del polinomio.
Vedi anche il capitolo "cercare da dove viene una sequenza" dal libro "concetti fluidi e analogie creative: modelli di computer dei meccanismi fondamentali del pensiero" di Douglas Hofstadter
Bene i primi due sono facili ma come generalizzare? – JonH
Penso che la seconda riga restituisca 60 ... –
Sì, grazie Maurizio. Mi è mancato. : p –