Решение модуля 7.9 Инди-курс программирования на Python

Модуль 7.9 (Рекурсия в Python. Рекурсивная функция Часть 2).

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

Учитывая указанные выше условия, ваша задача состоит в том, чтобы преобразовать этот вложенный словарь в плоский (состоящий только из одного уровня), где ключи формируются конкатенацией вложенных ключей, соединенных знаком _

Для этого необходимо определить рекурсивную функцию flatten_dict. Она должна принимать вложенный словарь и возвращать плоский

Ниже приведены несколько способов решения вышеуказанной задачи.

nested = {'Germany': {'berlin': 7},
          'Europe': {'italy': {'Rome': 3}},
          'USA': {'washington': 1, 'New York': 4}}

flatten_dict(nested) => {'Germany_berlin': 7,
                         'Europe_italy_Rome': 3,
                         'USA_washington': 1,
                         'USA_New York': 4}

nested = {'Q': {'w': {'E': {'r': {'T': {'y': 123}}}}}}

flatten_dict(nested) => {'Q_w_E_r_T_y': 123}

not_nested = {'a': 100, 'b': 200}

flatten_dict(not_nested) => {'a': 100, 'b': 200}

Ваша задача только написать определение функции flatten_dict

def flatten_dict(a: dict, key: str = '') -> dict:       # добавил ключ(что-бы передавать внешний ключ)
    c = {}                                              # пустой словарь для возврата готового списка
    for k, v in a.items():                              # проходимся по эл-м словаря(достаем ключ и значение)
        if type(v) == int:                              # если значение число
            c.update({(key+'_'+k)[1:]: v})              # обновляем словарь (ключ без первого эл-та "_")
        else:
            c.update(flatten_dict(v, key=key+'_'+k))    # иначе обновляем словарь вызывая фун-ю
    return c

Сортировка слиянием (merge sort)

Есть несколько типов сортировки, которые используют рекурсию. Одна из них называется сортировка слиянием

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

Также для реализации функции merge_sort вам понадобится реализовать функцию merge_two_list. Функция merge_two_list должна принимать два отсортированных по неубыванию списка, сливать их в один большой список также отсортированный по неубыванию (задача Слияние списков ) и возвращать его.

Ваша задача написать только определение функций merge_sort и merge_two_list, при этом нельзя пользоваться встроенными сортировками в Python

# функция merge_two_list должна объединить два списка
def merge_two_list(a, b):
    i=j=0
    c=[]
    while i<len(a) and j<len(b):  # сравниваем длину списков
        if a[i]<b[j]:
            c.append(a[i])
            i+=1
        else:
            c.append(b[j])
            j+=1
    c+=a[i:]+b[j:]
    return c

# функция merge_sort должна выполнить сортировку
def merge_sort(s):
    if len(s)==1:
        return s
    middle=len(s)//2
    left=merge_sort(s[:middle])
    right=merge_sort(s[middle:])
    return merge_two_list(left,right)

Быстрая сортировка (quick sort)

Быстрая сортировка — еще один вид сортировки, который использует рекурсию. 

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

Необходимо написать только определение функций quick_sort, при этом нельзя пользоваться встроенными сортировками в Python

# функция quick_sort должна выполнить сортировку
def quick_sort(s):
	if len(s) <= 1:				# Если длина списка меньше 1
		return s			# То список является отсортированным.

	n = s.pop(len(s)//2)			# Выбираем "опорный" элемент , выберем средниЙ(медианный) как опорный
	less = [i for i in s if i <= n]		# Элементы меньше выбранного элемента
	more = [i for i in s if i > n]		# Элементы больше выбранного элемента
    
	return quick_sort(less) + [n] + quick_sort(more)  # Возвращаем левую отсортированную часть опорный элемент и правую отсортированную часть