Математический алгоритм не работает, но кажется правильным

Question

Мне задали проблему, в которой функция подается в A и B. Это целевые номера от 1, 1, при которых B может увеличиваться только на A и A, может увеличиваться только на B (Ex, 1 1 -> 2 1 или 1 2. 2 1 -> 3 1 или 2 3. 2 3 -> 5 3 или 2 5). Это создает двоичное дерево. В задаче, заданной целевыми номерами, мне нужно найти «минимальное» количество поколений, прошедшее для достижения этого числа, или если число можно достичь (например, невозможно достичь 2 4). Вот решение, которое я придумал, и это проходит каждый тест, я бросить на нее:

import math 

def answer(M, F): 
    m = int(M) 
    f = int(F) 
    numgen=0 
    if f==1 and m==1: 
     return "0" 
    while f>=1 and m>=1: 
     if f > m: 
      m, f = f, m 
     if f==1: 
      return str(numgen + m - 1) 
     if m>f: 
      numgen += math.floor(m/f) 
      m = m % f 
    return "impossible" 

Я пол-коду играть в гольф, и я чувствую, что мое решение является очень элегантным и довольно эффективным , Все, что я набрасываю на него в течение десяти поколений, является правильным, и если я бросаю большие числа (верхние пределы указаны на уровне 10^50 на входах), они тоже работают отлично. При представлении и запуске против неизвестных тестовых случаев три из пяти сбой. По сути, мой вопрос больше хочет узнать, какие случаи терпят неудачу здесь.

У меня есть несколько предположений, я не могу доказать, но я абсолютно уверен, являются точными:

• Там нет дубликатов в пределах бинарного дерева. Я не обнаружил никаких случаев, и я подозреваю, что это математически обосновано.
• Правая и левая половины дерева могут быть зеркально отражены, не влияя на количество поколений - это на самом деле довольно доказано.
• Существует только один маршрут для достижения любой комбинации (свойство двоичных деревьев, где нет дубликатов). Это зависит от предположения 1, но если предположение 1 истинно, то это также должно быть правдой.
• Одно из двух чисел всегда является простым. Это не влияет на алгоритм, и я не доказал этого, но это всегда так. Интересный лакомый кусочек.

Где это решение неправильно?

Answer 1

Вы не сказали, используете ли вы Python 2 или Python 3, но math.floor(m/f) имеет смысл только в Python 3. Там m/f является поплавок, который является неточным. Лучше просто использовать целочисленное деление: numgen += m // f. Пример, где это имеет значение, - M, F = str(10**30), '3', где вы вычисляете 333333333333333316505293553666, но с целым делением вы получите 333333333333333333333333333335.

Answer 2

Ваше решение было слишком сложным для того, что я считаю своим честным мнением. Посмотрите на это:

def answer(M, F): 
    my_bombs = [int(M), int(F)] 
    my_bombs.sort() 
    generations = 0 
    while my_bombs != [1, 1]: 
     if my_bombs[0] == 1: 
      return str(generations + my_bombs[1] - 1) 
     if my_bombs[0] < 1 or my_bombs[0] == my_bombs[1]: 
      return "impossible" 
     print(my_bombs, generations) 
     n = my_bombs[1] // my_bombs[0] 
     my_bombs[1] -= my_bombs[0] * n 
     generations += n 
     my_bombs.sort() 
    return str(generations)