Trova il numero minimo di iterazioni per raggiungere una certa somma

Sto provando a risolvere questo problema da settimane, ma non ho potuto arrivare a una soluzione. Si inizia con due numeri X e Y entrambi uguali a 1. Solo le opzioni valide sono X+Y o Y+X alla volta. Dobbiamo trovare il numero minimo di iterazioni necessario per raggiungere un numero specifico.Trova il numero minimo di iterazioni per raggiungere una certa somma

esempio: se il numero è 5

X=1, Y=1; X = X+Y 

X=2, Y=1; Y = X+Y 

X=2, Y=3; Y = Y+X 

X=2, Y=5; Stop answer reached

mio prendere: se un numero è dispari diciamo 23, decremento di 1. Ora value = 22. Trovare il più grande numero che divide 22 = 11. Ora raggiungere il numero aggiungendo 1 di modo che:

X=11; Y=1 ; Y=Y+X 

X=11; Y=12; X=X+Y 

X=23, answer reached

Ma il problema con questo approccio è che non posso ricorsivamente raggiungere un numero specifico, come anche se raggiungo un certo punto, diciamo X = valore richiesto, il valore Y ottiene mal riposto e non posso riutilizzarlo per raggiungere un altro valore

fonte

2015-10-29 Mayur Kulkarni

Può essere questa domanda sul sito di matematica? –

Un'osservazione: se si costruisce un albero con possibili risultati distinti dopo ogni passaggio, si ottiene {(1-1)} a 1 punto, {(2-1)} al secondo, {(3-1), (2- 3)} al terzo, {(4-1), (3-4), (5-3), (2-5)} al quarto ecc. Il valore massimo che si ottiene in ogni passo è il numero di Fibonacci {1, 2, 3, 5, 8 ...}. Mentre i passaggi procedono, tutti i valori vengono riempiti in ogni passaggio da 1 a numero di fibonacci, ma nel passaggio 5 manca il numero 6, nel passaggio 6 hai tutti da 1 a 13, quindi nel passaggio 7 hai tutti da 1 a 21 ma tranne 20. I non ha proceduto di più ma potrebbe essere una sequenza nota {6, 20, ..} Non so. –

Quindi la mia ipotesi sarebbe che il numero minimo di passi per ottenere il numero richiesto sia uguale all'altezza di quell'albero eccetto quei numeri magici (6, 20, ...) Ad esempio se hai bisogno di ottenere il numero 67, allora lo trovi non può essere prima del numero 55 di fibonacci ma probabilmente apparirà sul prossimo gradino dove Fibonacci è 89. Quindi ottieni 10 passi come altezza dell'albero sarà 10. Per 5 (è fibonacci) ottieni altezza 4, per 7 ottieni altezza 5 come 7 è tra 5 e 8. Ma è solo un suggerimento. –

Ora posso dare una soluzione O(nlogn).

Il metodo sembra greatest common divisor

Usa f(x, y) esprimono il numero minimo di iterazioni da questo stato. Questo stato può essere raggiunto da f(x-y, y) se x>y o f(x,y-x) se x<y. Possiamo vedere che il modo per raggiungere lo stato (x, y) è unico, possiamo calcolarlo in O(logn) come gcd.

La risposta è min(f(n, i) | 1 <= i < n) così complessità è il codice O(nlogn)

pitone:

def gcd (n, m): 
    if m == 0: 
     return n 
    return gcd (m, n%m) 

def calculate (x, y): 
    if y == 0: 
     return -1 
    return calculate (y, x%y) + x/y 

def solve (n): 
    x = 0 
    min = n 
    for i in xrange (1, n): 
     if gcd (n, i) == 1: 
      ans = calculate (n, i) 
      if ans < min: 
       min = ans 
       x = i 
    print min 

if __name__ == '__main__': 
    solve (5)

fonte

2015-10-29 08:18:12 throwit

Perché non possiamo raggiungere lo stato '(x, y)' con 'x <= y' dallo stato' (x-y, y) '? – fjardon

Poiché x ≤ y implica x - y ≤ 0. – gnasher729

Dovresti menzionare che gcd (x, y) = 1 in tutte le aggiunte che portano al risultato n, perché ciò consente la condizione gcd (n, i) = 1. Se si rimuovono i casi n ≤ 4 che richiedono passi n-1, si può assumere n> i> n/2 e il numero di passi è 1 + calcolare (i, n - 1). Se n è pari, io devo essere dispari, quindi puoi scorrere attraverso il solo io dispari, migliorando la velocità. – gnasher729

Se i numeri non sono così grandi (ad esempio, sotto 1000), è possibile utilizzare uno breadth-first search.

Considerare un grafico diretto in cui ogni vertice è una coppia di numeri (X,Y) e da ciascun vertice ci sono due spigoli ai vertici (X+Y,Y) e (X,X+Y). Esegui un BFS su quel grafico da (0,0) finché non raggiungi una delle posizioni di cui hai bisogno.

fonte

2015-10-29 07:59:58 Petr

L'intervallo è fino a 10000 –

@MayurKulkarni, BFS dovrebbe funzionare anche per questo. – Petr

Grazie, vado subito a scrivere il codice :-) –

Trova il numero minimo di iterazioni per raggiungere una certa somma

risposta

Problemi correlati