Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 19=1×24+0×23+0×22+1×21+1×20 в двоичной системе запишется как 100112). Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким: 10011 11001 11100 01110 00111 10011 … и результатом игры, следовательно, окажется число 1×24+1×23+1×22+0×21+0×20=28. Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы Юрию Петровичу получать результат игры без утомительных ручных вычислений.Питон
```python
def decimal_to_binary(n):
binary = ""
while n > 0:
binary = str(n % 2) + binary
n = n // 2
return binary
def find_cycle(binary):
cycle = binary
while True:
binary = binary[1:] + binary[0]
if binary == cycle:
break
cycle += binary[0]
return cycle
def binary_to_decimal(binary):
decimal = 0
length = len(binary)
for i in range(length):
decimal += int(binary[i]) * 2**(length - i - 1)
return decimal
def find_max_decimal(n):
binary = decimal_to_binary(n)
cycle = find_cycle(binary)
max_decimal = binary_to_decimal(cycle)
return max_decimal
# Пример использования программы
number = 19
max_decimal = find_max_decimal(number)
print("Результат игры:", max_decimal)
```
Теперь давайте посмотрим, как работает этот код пошагово.
1. Сначала у нас есть функция `decimal_to_binary(n)`, которая принимает целое число `n` и переводит его в двоичную систему счисления. Мы используем цикл `while`, чтобы последовательно делить число `n` на 2 и сохранять остатки в строку `binary`. Наконец, мы возвращаем полученное двоичное число.
2. Затем у нас есть функция `find_cycle(binary)`, которая принимает двоичное число в виде строки `binary`. Мы используем цикл `while`, чтобы сдвигать цифры в строке `binary` по циклу. Мы начинаем с `cycle`, равного `binary`, и добавляем первую цифру сдвига в `cycle`. Цикл продолжается до тех пор, пока `binary` не станет равным исходному значению `cycle`. Затем мы возвращаем найденный цикл.
3. Далее у нас есть функция `binary_to_decimal(binary)`, которая принимает двоичное число в виде строки `binary` и переводит его обратно в десятичную систему счисления. Мы использовали счетчик `i` для пробега по цифрам двоичного числа `binary`. Мы умножаем каждую цифру на `2^(length - i - 1)` и добавляем результат к переменной `decimal`. В конце мы возвращаем полученное десятичное число.
4. Наконец, у нас есть функция `find_max_decimal(n)`, которая принимает исходное целое число `n` и использует предыдущие функции для нахождения максимального числа игры. Мы сначала переводим число `n` в двоичную систему счисления, затем находим цикл с помощью `find_cycle()`. Затем мы переводим цикл обратно в десятичное число с помощью `binary_to_decimal()`. И, наконец, мы возвращаем полученный результат.
5. В примере использования программы, мы задаем число 19. Затем мы вызываем функцию `find_max_decimal()` с этим числом и сохраняем результат в переменную `max_decimal`. Наконец, мы выводим полученный результат на экран.
Таким образом, эта программа позволяет найти результат игры для любого произвольного числа, используя вышеуказанные шаги.