В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
SamaraArtem24
SamaraArtem24
10.12.2021 03:00 •  Информатика

ЗАДАЧИ НА ПИТОНЕ 1. Дано число. Реализовать рекурсивный алгоритм по развороту этого числа (1234->4321)
2. Дано число x(целое). Реализовать рекурсивный алгоритм для вывода на экран всех чисел от 1 до x
3. Дано число. Реализовать рекурсивный алгоритм, который будет возвращать слово “Да” если это число равно степени 2(2,4,8,16,32,64 и тд), и “Нет” в противном случае

НАПИСАТЬ К КАЖДОЙ ЗАДАЧЕ, КАКОВА ЕЕ АСИМПТОТИЧЕСКАЯ СЛОЖНОСТЬ В ПОСЛЕДНЕЙ СТРОКЕ КОММЕНТАРИЕМ (речь об О-нотации)

Показать ответ
Ответ:
kurroro
kurroro
02.07.2021 13:39

Прикрепляю файл с сохранением форматирования. Его же можно переименовать в файл с расширением .py и запустить в интерпретаторе, проверить работо .

И да, единица тоже является степенью двойки, так что checkBy2(1) выдаст "да"

def reverseNumber(x, n=0):

s = list(str(x)) if type(x) == int else x

if n*2 >= len(s):

 return int(''.join(s))

else:

 s[n],s[len(s)-n-1] = s[len(s)-n-1],s[n]

 return reverseNumber(s, n+1)

# Сложность O(n), где n - количество символов в строковом представлении x

# либо, если n воспринимать как число, O(logn)

print(reverseNumber(12345))

def printBelow(x, current=1):

if x > 0 and current <= x:

 print(current)

 printBelow(x, current+1)

# Сложность O(n), если считать сложность перевода числа в строку константной

printBelow(10)

def checkBy2(x):

if x == 1:

 print("Да")

elif x % 2 != 0 or x < 1:

 print("Нет")

else:

 checkBy2(x//2)

# Сложность O(logn), если не используется длинная арифметика, т.к. в худшем случае

# для увеличения рекурсивных вызовов на n нужно увеличить число в 2^n раз

checkBy2(31)

checkBy2(32)

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота