Проект: Рекурсия

Не забывайте использовать Git для фиксации изменений в ваших проектах!

На разогрев: Фибоначчи

Последовательность Фибоначчи, каждое число в которой является суммой двух предыдущих, является прекрасной задачей, которую можно решить методом рекурсии.

Задание

1. Напишите метод #fibs, который получает число и возвращает такое же количество чисел, соблюдая последовательность Фибоначчи. Используйте для решения итерацию.
2. Затем напишите другой метод #fibs_rec, который делает то же самое, но используя рекурсию. Это реализуемо всего в 3 строчках кода (или в 1, если вы сумасшедший). Не рассматривайте количество строк как требование... просто выполните задание.

Решения студентов

• Решение 1
• Решение 2
• Решение 3
• Решение 4
• Решение 5

Проект: Сортировка слиянием

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

Background Viewing

Первый шаг для понимания, что же делает алгоритм этой сортировки:

1. Посмотрите это видео из курса CS50.
2. Сортировка слиянием - как это работает, часть I и Сортировка слиянием - как это работает, часть II на YouTube даст вам более формальный взгляд на эту проблему, если вам еще что-то неясно.

Задание

1. Создайте метод #merge_sort, принимающий массив и возвращающий его в отсортированном виде, используя сортировку слиянием.

2. Подсказки:

   1. Подумайте, какова основная цель, и какая операция повторяется снова и снова, и может быть делегирована чему-то другому (этому же методу!).
   2. Возможно, будет полезно пересмотреть видеоматериалы, если будете испытывать затруднения.

Решения студентов

• Решение 1
• Решение 2
• Решение 3
• Решение 4
• Решение 5

Дополнительные ресурсы

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

• Другой взгляд на сортировку слиянием
• Если хотите попробовать свои силы далее, решите первые 5 проблем здесь