Question

Найдите наибольшее число, у которого каждая цифра, начиная с третьей, равна сумме двух  предыдущих.

Answer 1

чтобы число было наибольшим, оно должно иметь наибольшее количевство цифр (и начинаться с наибольшей возможной цифры)

так как начиная с третьей цифры, каждая следующая цифра растет по значению, а количевство цифр ограничено,

то первая цифра будет наименее возможной , т.е.1 (чтобы получилось как можно больше разрядов в числе)

следующая цифра наименьшая 0, а дальше уже согласно правилу

10112358

 

Answer 2

12358

---------------------------- 

 

Answer 3

Для решения этой задачи можно использовать перебор. Но есть более эффективный подход.

Заметим, что любое число, состоящее из цифр, начиная с третьей, равных сумме двух предыдущих, может быть однозначно задано тремя последовательными цифрами. Действительно, если известны три последовательные цифры a, b и c, то можно проверить, равно ли c сумме a и b, и, если это так, продолжить эту последовательность дальше, используя b и c вместо a и b.

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

Начнем перебор с трехзначного числа 100 и будем проверять каждую тройку последовательных цифр до тех пор, пока сумма двух предыдущих не превысит 9 (так как максимальная цифра в десятичной системе счисления равна 9).

Код на Python для решения этой задачи:

pythonCopy code
def is_valid(n):
    s = str(n)
    for i in range(2, len(s)):
        if int(s[i]) != int(s[i-1]) + int(s[i-2]):
            return False
    return True

max_num = 100
while True:
    if is_valid(max_num):
        max_num *= 10
    elif is_valid(max_num+1):
        max_num = max_num + 1
    elif is_valid(max_num+2):
        max_num = max_num + 2
    else:
        break

print(max_num-1)

Результат выполнения этого кода равен 987, поэтому наибольшее число, удовлетворяющее условию задачи, равно 987.