Separazione dell'array unito di serie aritmetiche e geometriche [chiuso]

Puoi farlo in tempo lineare.

In primo luogo, si noti che una progressione geometrica è solo una progressione aritmetica nel logaritmo elementare della sequenza. Quindi possiamo pensare di avere una sequenza di coppie di numeri che vogliamo coprire con una progressione che è aritmetica nel primo elemento e una progressione che è aritmetica nel secondo elemento.

Due dei primi tre elementi devono trovarsi nella stessa progressione. Senza perdita di generalità, presumo che sia la progressione aritmetica. Puoi trovare, in tempo lineare, la sequenza aritmetica più lunga con il giusto inizio e la differenza comune che è una sottosequenza del tuo input. Lo fai e poi ti rimane un mucchio di elementi scoperti; dì che i loro logaritmi sono g_1, g_2, ..., g_k.

Trova il "massimo comun divisore" di g_2-g_1, ..., g_k-g_1 --- Voglio il più grande numero reale d tale che g_2-g_1, g_3-g_1, ..., g_k-g_1 possa tutti devono essere scritti come multipli di d.

Quindi, se c'è una progressione geometrica che copre g_1, ..., g_k che è una sottosequenza del tuo input, ci deve essere uno con rapporto comune d. Tutto quello che devi fare è controllare che g_1, g_1 * exp (d), g_1 * exp (2d), ..., g_k siano tutti elementi del tuo input, e puoi farlo in tempo lineare.

Quindi fai le sei volte sopra (due volte --- aritmetiche e geometriche --- per ognuna delle tre possibili scelte di "prime due"), e quello sopra richiede un tempo lineare.

Supponiamo che una sequenza contenga almeno 2 numeri. Ecco un approccio più o meno brutale:

• calcola la differenza di ogni coppia di numeri: questo ti dà un numero finito di possibili differenze (chiamiamo quel numero impostato D). Una di queste differenze deve essere la differenza costante dell'AP

• inoltre, calcola il rapporto di ogni coppia di numeri: questo ti dà un numero finito di possibili rapporti (chiamiamo quel numero impostato R). Uno di questi deve essere la costante razione del GP

• Scegli ogni coppia (d, r) di D x R. Test se riesci a trovare un AP in una sequenza secondaria con diff d costante e una sotto-sequenza GP con rapporto costante r, in modo che l'unione di entrambe le sotto-sequenze formano la sequenza originale.

Per l'ultimo passaggio, devi considerare che potrebbero esserci più di una possibile sottosequenza per un dato dominio. Tuttavia, puoi fare di meglio che generare tutte le possibili sottosequenze se fai uso di questo fatto che almeno una delle due sequenze deve contenere il primo di tutti i numeri, e la seconda deve contenere uno dei numeri che non è contenuto nell'altra sotto-sequenza.

Per esempio, quando usi il tuo esempio sopra, il set D conterrà 2 (e alcuni più numeri), e R conterrà 2, 2.5, e alcuni più numeri. Il test d = 2, r = 2, porterà all'AP 2,4,6,8,10,12, ma il rimanente numero 25 non fa parte di un GP con almeno due numeri e r = 2 (né 50 né 12.5 fa parte del set di numeri specificato). Tuttavia, quando il prossimo test è d = 2, r = 2.5, troverai facilmente la soluzione sopra.

Puoi provare un metodo per trovare la più lunga progressione aritmetica. Ecco semplice soluzione DP con complessità quadratica e il documento PDF completo contiene indizi per (teoricamente) metodo più efficace.

Questo metodo è applicabile alle serie geometriche a (controllo A[i] + A[k] = 2*A[j] turns into A[i] * A[k] = A[j] * A[j] e così via ..)

Preferisco interpretare il tuo esempio come
AP: 2,4,6,8,10,12
GP: 25
in quanto questa è un'interpretazione valida pure e più facile da trovare.

Per prima cosa guarderei i primi tre numeri interi. Chiamiamoli a , b e c .

• Se b - a = c - b , puoi supporre che questa sia la larghezza del passo della tua serie aritmetica, e la serie geometrica non è ancora iniziata.
• Se b / a = c / b , puoi supporre che questo è il rapporto tra le serie geometriche e che la serie aritmetica non è ancora iniziata.
• Indipendentemente dal fatto che entrambe le condizioni siano soddisfatte o meno (grazie a tmyklebu per indicarlo), hai diverse altre ipotesi valide. Puoi supporre che due dei numeri costituiscano l'inizio di una delle serie e che l'elemento rimanente sia l'inizio delle altre serie.

È possibile mantenere un elenco di ipotesi attualmente valide mentre si procede lungo l'array. Nel caso di un'ipotesi con una sola sequenza avviata, si deve assumere che il primo numero che non appartiene a quella sequenza sia l'inizio dell'altra sequenza. Se hai una sequenza e l'inizio di un'altra sequenza, probabilmente incontrerai un numero che non fa parte della sequenza definita. Puoi usarlo per definire la sequenza rimanente.

Devi prenderti cura di te. Quando hai avuto una serie geometrica e trovi il secondo numero che non corrisponde a quella serie, sai di aver trovato due numeri appartenenti alla serie aritmetica. Ma la loro differenza potrebbe essere un multiplo della larghezza del passo. Quindi dovresti scorrere tutti i divisori di quella differenza e controllare se i valori intermedi indicati dalla larghezza del passo ridotta sono presenti nelle serie geometriche. Solo fino a due elementi di una serie aritmetica possono far parte di una serie geometrica, quindi non è necessario controllare tutti i divisori. È sufficiente controllare metà e un terzo della larghezza e solo se quel numero è un numero intero. Una considerazione simile deve essere utilizzata per trovare il rapporto delle serie geometriche, prendendo in considerazione gli elementi duplicati posisabili. Devi controllare la radice quadrata e la radice cubica della frazione dei due numeri che definiscono, e vedere se anche questi sono razionali e risultano in numeri interi. L'arrotondamento potrebbe essere un problema, a meno che non si disponga di una struttura dati per rappresentare numeri razionali e scomporre il fattore primo.

Potrebbe essere che più larghezze o rapporti di step siano coerenti con i dati fino ad ora. In tal caso, si dovrebbe andare con tutti loro, controllando i dati rimanenti per vedere se sono ancora in attesa. Alla fine, hai una singola ipotesi valida, o un insieme di ipotesi da cui puoi scegliere a piacimento. Se lo si desidera, è possibile verificare se una di queste serie può essere estesa prima del primo elemento presunto, riutilizzando elementi delle altre serie. Questo potrebbe essere usato per trovare 4 e 10 nell'esempio del tuo. Ma la risposta dovrebbe essere valida anche senza questo passaggio.