Блог для маленьких школьников и их родителей
ШколаЛа

ЗАДАЧИ НА ПИТОНЕ 1. Дано число. Реализовать рекурсивный алгоритм по развороту этого числа (1234->4321)…

Автор:
Предмет: Информатика
Уровень: студенческий

ЗАДАЧИ НА ПИТОНЕ

1. Дано число. Реализовать рекурсивный алгоритм по развороту этого числа (1234->4321)

2. Дано число x(целое). Реализовать рекурсивный алгоритм для вывода на экран всех чисел от 1 до x

3. Дано число. Реализовать рекурсивный алгоритм, который будет возвращать слово “Да” если это число равно степени 2(2,4,8,16,32,64 и тд), и “Нет” в противном случае

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

Ответов к вопросу: 1
  • Kitten175
    20.08.2024 | 16:28

    Прикрепляю файл с сохранением форматирования. Его же можно переименовать в файл с расширением .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)

Ответить на вопрос:
:p :-p 8) 8-) :lol: =( :( :-( :8 ;) ;-) :(( :o:
Нажимая на кнопку я даю согласие на обработку персональных данных и принимаю политику конфиденциальности.