Наименьшее количество повторений для получения входных номеров с заданной функцией - PullRequest
Новая
       23

Наименьшее количество повторений для получения входных номеров с заданной функцией

0 голосов
/ 11 сентября 2018

Я выполняю задание Google foo.bar и создал этот код на python, чтобы ответить на него. Проблема состоит в том, что когда число ввода превышает 16 цифр, ответ всегда возвращается невозможным. Мне кажется очевидным, что это неверно, потому что, когда я проверяю числа, я обнаружил повторение в некоторых входных числах и количестве повторений, где добавление еще одной цифры всегда будет возвращать другую цифру значения места.

Например:
ввод 3 и 94 вернет 33
ввод 3 и 994 вернет 333
ввод 3 и 99999999994 вернет 33333333333
ввод 3 и 99999999999999994 вернет «невозможно»

Я не понимаю, почему что-то в определенном количестве мест вернет "невозможное" в моем коде.

Этот код принимает в качестве входных данных два случайных числа вплоть до размера 10 ^ 50 в виде строк, представленных как M и F. С этим числом вы должны найти наименьшее количество циклов, необходимое для достижения обоих чисел. Каждый цикл выполняет либо функцию F, либо функцию M. Функция F равна currentFnum + currentMnum, а функция M равна currentMnum + currentFnum.

Например, если у вас есть 3 M и 2 F, вы можете получить либо 5 M и 2 F, либо 3 M и 5 F. 

def answer(M, F):

    count = 0
    currentM = int(M)
    currentF = int(F)
    listCycleType = []

    def getGreater(currentF, currentM):
        if currentM > currentF:
            greater = [currentM, "M"]
            return greater
        elif currentM == currentF:
            greater = [currentM, "M"]
            return greater
        else:
            greater = [currentF, "F"]
            return greater

    def getLesser(currentF, currentM):
        if currentM < currentF:
            lesser = [currentM, "M"]
            return lesser
        elif currentM == currentF:
            lesser = [currentM, "M"]
            return lesser
        else:
            lesser = [currentF, "F"]
            return lesser

    greater = getGreater(currentF, currentM)
    lesser = getLesser(currentF, currentM)


    for x in range(1000000):
        greater = getGreater(currentF, currentM)
        lesser = getLesser(currentF, currentM)

        if currentF > 1 and currentM > 1 and currentF == currentM:
            return "impossible"


        if currentM < 1 or currentF < 1:
            return "impossible"


        if currentM == 1:
            count = count + currentF - 1
            return str(count)
        elif currentF == 1:
            count = count + currentM - 1
            return str(count)


        yes = float(greater[0]) / lesser[0]
        if not yes.is_integer():
            yes = greater[0] / lesser[0]
            count = count + yes
            if greater[1] == "M":
                currentM = currentM - yes * currentF
                continue
            else:
                currentF = currentF - yes * currentM
                continue


        if greater[1] == "M":
            currentM = currentM - currentF
            count = count + 1
        elif greater[1] == "F":
            currentF = currentF - currentM
            count = count + 1
        else:
            currentM = currentM - currentF
            count = count + 1


        if currentM == 1 and currentF == 1:
            return str(count)

    return "impossible"


print answer("3", "99999999999999994")

1 Ответ

0 голосов
/ 11 сентября 2018

Если вы измените
, если не yes.is_integer ():
На
, если больше [0]%, меньше [0]! = 0:
Тогда это работает отлично.

...