compter les générations précédentes d'un nombre

Question

J'essaie de faire de l'ingénierie inverse d'un ensemble de nombres qui me sont donnés (f, m) Je dois passer par et trouver combien de générations il faut partir de 1,1 en utilisant l'algorithme ci-dessous pour chaque génération:

x = 1 
y = 1 
new_generation = y+x 
x OR y = new_generation 

IE, je ne sais pas si X ou Y est modifié, l'autre variable reste la même ... Une liste des sorties possibles ressemblerait à ceci pour les valeurs de fin de 4 et 7 :

f = 4 
m = 7 
[1, 1] 
[2, 1, 1, 2] 
[3, 1, 2, 3, 3, 2, 1, 3] 
[4, 1, 3, 4, 5, 3, 2, 5, 5, 2, 3, 5, 4, 3, 1, 4] 
[5, 1, 4, 5, **7, 4**, 3, 7, 7, 5, 2, 7, 7, 2, 5, 7, 7, 3, **4, 7**, 5, 4, 1, 5] 

Où tous les deux ensembles de nombres (2,1) et (1,2) sont une sortie possible. Notez que ** indique la réponse (dans ce cas, l'ordre n'a pas d'importance tant que m et f ont leur valeur dans la liste). De toute évidence, il y a une croissance exponentielle ici, donc je ne peux pas (ou moins efficace) faire une liste et ensuite trouver la réponse; à la place, je suis en utilisant le code suivant pour inverser ce processus ...

def answer(m,f): 
    #the variables will be sent to me as a string, so here I convert them... 
    m = (int(m)) 
    f = (int(f)) 
    global counter 
    #While I have not reduced my given numbers to my starting numbers.... 
    while m != 1 or f != 1: 
     counter +=1 
     #If M is greater, I know the last generation added F to M, so remove it 
     if m > f: 
      m = m-f 
     #If F is greater, I know the last generation added M to M, so remove it 
     elif f > m: 
      f = f-m 
     else: 
      #They can never be the same (one must always be bigger, so if they are the same and NOT 1, it can't be done in any generation) 
      return "impossible" 
    return str(counter) 

print(answer("23333","30000000000")) 

Cela renvoie la réponse correcte (par exemple, 4,7 renvoie « 4 » qui est correct), mais il prend trop de temps quand je passe plus chiffres (je dois être capable de gérer 10^50, montant fou, je sais!). Ma pensée était que je devrais être capable d'appliquer une équation mathématique au nombre pour la réduire et les multiplier les générations, mais j'ai du mal à trouver un moyen de faire cela qui détient aussi l'intégrité de la réponse (par exemple , si je divise le plus grand par le plus petit, sur de petits nombres (7, 300000) je reçois une réponse très proche (mais fausse), cependant sur des nombres plus proches tels que (23333, 300000) la réponse est nulle, même proche, ce qui fait sens dû aux différences dans le chemin de génération). Note J'ai aussi essayé dans une fonction récursive (pour trouver les générations) et en utilisant la méthode non-inversée (construction de la liste et de vérifier la réponse, ce qui est beaucoup plus lente pour des raisons évidentes)

---

Voici quelques tests cas avec leurs réponses:

f = "1" 
m = "2" 
Output: "1" 

f = "4" 
m = "7" 
Output: "4" 

f = "4" 
m = "2" 
Output: "impossible" 

Toute aide est très appréciée! P.S. Je cours Python 2.7.6

[EDIT]

---

Le code ci-dessous fonctionne comme vous le souhaitez.

from fractions import gcd 

def answer(m,f): 
    #Convert strings to ints... 
    m = (int(m)) 
    f = (int(f)) 

    #If they share a common denominator (GCD) return impossible 
    if gcd(m,f) != 1: 
     return "impossible" 
    counter = 0 
    #While there is still a remainder... 
    while m != 0 and f != 0: 
     if m > f: 
      counter += m // f 
      #M now equals the remainder. 
      m %= f 
     elif f > m: 
      counter += f // m 
      f %= m 
    return str(counter - 1) 

Answer 1

Vous êtes sur la bonne voie avec l'approche descendante que vous avez affichée. Vous pouvez l'accélérer d'un facteur énorme si vous utilisez la division entière au lieu de la soustraction répétée.

def answer(m, f): 
    m = int(m) 
    f = int(f) 
    counter = 0 
    while m != 0 and f != 0: 
     if f > m: 
      m, f = f, m 
     print(m, f, counter, sep="\t") 
     if f != 1 and m % f == 0: 
      return "impossible" 
     counter += m // f 
     m %= f 
    return str(counter - 1) 

En utilisant ce qui précède, answer(23333, 30000000000) cède

30000000000 23333 0 
23333 15244 1285732 
15244 8089 1285733 
8089 7155 1285734 
7155 934 1285735 
934 617 1285742 
617 317 1285743 
317 300 1285744 
300 17 1285745 
17 11 1285762 
11 6 1285763 
6 5 1285764 
5 1 1285765 
1285769 

et answer(4, 7) cède

7 4 0 
4 3 1 
3 1 2 
4 

Answer 2

Essayez une forme de récursion:

(Python 2.7.6)

def back(): 
    global f,m,i 
    if f<m: 
     s=m//f 
     i+=s 
     m-=s*f 
    elif m<f: 
     s=f//m 
     i+=s 
     f-=s*m 
    else: 
     return False 
    return True 
while True: 
    f=int(raw_input('f = ')) 
    m=int(raw_input('m = ')) 
    i=0 
    while True: 
     if f==m==1: 
      print 'Output:',str(i) 
      break 
     else: 
      if not back(): 
       print 'Output: impossible' 
       break 
    print 

(Python 3.5.2)

def back(): 
    global f,m,i 
    if f<m: 
     s=m//f 
     i+=s 
     m-=s*f 
    elif m<f: 
     s=f//m 
     i+=s 
     f-=s*m 
    else: 
     return False 
    return True 
while True: 
    f=int(input('f = ')) 
    m=int(input('m = ')) 
    i=0 
    while True: 
     if f==m==1: 
      print('Output:',str(i)) 
      break 
     else: 
      if not back(): 
       print('Output: impossible') 
       break 
    print() 

Note: Je suis Python 3.5 codeur donc j'ai essayé de antidater mon code, s'il vous plaît laissez-moi savoir s'il y a quelque chose de mal avec cela.

Le format d'entrée est également différent: au lieu de f = "some_int", il est maintenant f = some_int et la sortie est formatée de manière similaire.

Answer 3

Ce n'est pas une question Python et ce n'est pas vraiment une question de programmation. Ceci est un problème conçu pour vous faire penser.En tant que tel, si vous obtenez simplement la réponse de quelqu'un d'autre, vous n'obtiendrez aucune connaissance ou recul de l'exercice.

Ajoutez simplement un print(m, f) dans votre boucle while et observez comment les nombres évoluent pour les petites entrées. Par exemple, essayez avec quelque chose comme (3, 100): ne voyez-vous pas comment vous pouvez accélérer les choses, plutôt que de supprimer à plusieurs reprises 3 du plus grand nombre?