Python-сообщество

Saint · Март 8, 2017 15:48:36

Вынуждена просить у вас помощи. Надо написать программу, которая переводит число (число целое, может быть и отрицательным) из 10сс в 16сс, с помощью рекурсии. Рекурсии в целом понимаю плохо, поэтому прошу помощи у Всевышних.

py.user.next · Март 8, 2017 17:15:35

  
>>> def to_base(n, base):
...     def f(n, base, acc):
...         if n == 0:
...             return acc
...         return f(n // base, base, [n % base] + acc)
...     alpha = '0123456789abcdefghijklmnopqrstuvwxyz'
...     out = ''.join(alpha[i] for i in f(n, base, [])) or '0'
...     return out
... 
>>> to_base(12345, 16)
'3039'
>>> to_base(128, 16)
'80'
>>> to_base(10, 16)
'a'
>>> to_base(0, 16)
'0'
>>> 
>>> to_base(12345, 2)
'11000000111001'
>>> to_base(12345, 36)
'9ix'
>>>

Знак добавил

  
>>> def to_base(n, base):
...     def f(n, base, acc):
...         if n == 0:
...             return acc
...         return f(n // base, base, [n % base] + acc)
...     alpha = '0123456789abcdefghijklmnopqrstuvwxyz'
...     out = ''.join(alpha[i] for i in f(abs(n), base, [])) or '0'
...     if n < 0:
...         out = '-' + out
...     return out
... 
>>> to_base(12345, 16)
'3039'
>>> to_base(128, 16)
'80'
>>> to_base(10, 16)
'a'
>>> to_base(0, 16)
'0'
>>> to_base(-12345, 16)
'-3039'
>>> 
>>> to_base(12345, 2)
'11000000111001'
>>> to_base(12345, 36)
'9ix'
>>>

Отредактировано py.user.next (Март 8, 2017 17:39:38)

Saint · Март 8, 2017 18:57:06

Огромное Вам спасибо! Правда, я не совсем понимаю, для чего служит параметр “асс”…

Отредактировано Saint (Март 8, 2017 19:00:53)

py.user.next · Март 9, 2017 01:40:18

Saint
для чего служит параметр “асс”…

Это накопитель (accumulator), в нём накапливается результат, который потом и возвращается. Накопитель используется для того, чтобы рекурсия была хвостовой. Хвостовая рекурсия даёт возможность компилятору неявно оптимизировать вызовы таким образом, чтобы потребление оперативной памяти не росло при каждом вызове, а оставалось постоянным. Если же рекурсия не хвостовая, то каждый новый вызов ложится рядом с предыдущим, а не вместо него, и таким образом потребляется всё больше и больше памяти.

  
>>> def f(n, base, acc):
...     if n == 0:
...         return acc
...     return f(n // base, base, [n % base] + acc)
... 
>>> f(12345, 16, [])
[3, 0, 3, 9]
>>> f(123451234512345, 16, [])
[7, 0, 4, 7, 3, 10, 15, 10, 14, 13, 13, 9]
>>>

  
>>> import math
>>> 
>>> def f(n, base, acc):
...     if n == 0:
...         return acc
...     return f(n // base, base, [n % base] + acc)
... 
>>> f(math.factorial(3000), 16, [])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in f
  File "<stdin>", line 4, in f
  File "<stdin>", line 4, in f
  ...

В обычном питоне, конечно, нет таких оптимизаций, но в других языках есть. Да и в самом питоне, вроде, есть компилятор, где есть оптимизации эти. Поэтому надо сразу приучаться писать хвостовую рекурсию, так как она может быть бесконечной в отличие от не хвостовой.

tags: recursion

Отредактировано py.user.next (Апрель 25, 2021 22:03:47)

Python-сообщество

Уведомления

#1 Март 8, 2017 15:48:36

Шестнадцатиричный код

#2 Март 8, 2017 17:15:35

Шестнадцатиричный код

#3 Март 8, 2017 18:57:06

Шестнадцатиричный код

#4 Март 9, 2017 01:40:18

Шестнадцатиричный код

Board footer