Напиши рекурсивную функцию на Python, которая переставляет цифры в десятичном…
- User
Напиши рекурсивную функцию на Python, которая переставляет цифры в десятичном представлении числа в порядке неубывания.
- Assistant
Конечно! Вот рекурсивная функция на Python, которая переставляет цифры числа в порядке неубывания:
def sort_digits(n): # Базовый случай: если число однозначное, возвращаем его if n < 10: return n # Рекурсивно сортируем все цифры, кроме последней rest_sorted = sort_digits(n // 10) last_digit = n % 10 # Вставляем последнюю цифру в отсортированное число на нужное место rest_str = str(rest_sorted) inserted = False result = '' for ch in rest_str: if not inserted and int(ch) > last_digit: result += str(last_digit) inserted = True result += ch if not inserted: result += str(last_digit) return int(result) # Пример использования: print(sort_digits(31452)) # Выведет: 12345Пояснения:
- Функция
sort_digitsпринимает целое числоn. - Базовый случай: если число однозначное, оно уже отсортировано.
- Рекурсивно сортируем все цифры, кроме последней.
- Вставляем последнюю цифру в нужное место в уже отсортированной последовательности (по принципу сортировки вставками).
- Возвращаем новое число.
Если есть вопросы — спрашивайте!
- Функция
- User
а можно реализовать такой функционал без преобразования к строке?
- Assistant
Да, можно реализовать сортировку цифр числа по неубыванию без преобразования к строке. Для этого можно использовать рекурсию и работать только с числами. Вот один из способов — рекурсивно извлекать минимальную цифру и строить новое число:
def min_digit_and_rest(n): """Возвращает минимальную цифру и число без одной такой цифры""" min_d = 10 temp = n count = [0]*10 while temp > 0: d = temp % 10 count[d] += 1 if d < min_d: min_d = d temp //= 10 # Удаляем одну минимальную цифру count[min_d] -= 1 # Собираем оставшееся число rest = 0 for d in range(9, -1, -1): for _ in range(count[d]): rest = rest * 10 + d # Переворачиваем rest, чтобы порядок был правильный rev = 0 while rest > 0: rev = rev * 10 + rest % 10 rest //= 10 return min_d, rev def sort_digits(n): if n < 10: return n min_d, rest = min_digit_and_rest(n) # Рекурсивно сортируем оставшееся число и добавляем минимальную цифру слева return min_d * (10 ** (len(str(sort_digits(rest))))) + sort_digits(rest) # Пример использования: print(sort_digits(31452)) # Выведет: 12345Пояснения:
min_digit_and_rest(n)находит минимальную цифру и возвращает её вместе с числом, из которого удалена одна такая цифра.sort_digits(n)рекурсивно строит новое число, добавляя минимальную цифру слева.- Преобразование к строке используется только для вычисления длины числа (чтобы правильно поставить разряд), но не для работы с цифрами.
Если совсем не использовать строки, можно написать функцию для подсчёта количества цифр в числе:
def num_length(n): if n == 0: return 0 return 1 + num_length(n // 10)И заменить
len(str(...))наnum_length(...).Вариант без строк вообще:
def min_digit_and_rest(n): min_d = 10 temp = n count = [0]*10 while temp > 0: d = temp % 10 count[d] += 1 if d < min_d: min_d = d temp //= 10 count[min_d] -= 1 rest = 0 for d in range(9, -1, -1): for _ in range(count[d]): rest = rest * 10 + d # Переворачиваем rest rev = 0 temp = rest while temp > 0: rev = rev * 10 + temp % 10 temp //= 10 return min_d, rev def num_length(n): if n == 0: return 0 return 1 + num_length(n // 10) def sort_digits(n): if n < 10: return n min_d, rest = min_digit_and_rest(n) length = num_length(sort_digits(rest)) return min_d * (10 ** length) + sort_digits(rest) print(sort_digits(31452)) # 12345Теперь строк нет вообще!
Если что-то неясно — спрашивайте!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.