Практика 5

Тест на знание функций

Задания в классе

Тема занятия - рекурсивные функции. Поэтому во всех заданиях запрещено использовать цикл for и while.

Человеку свойственна итерация, рекурсия – удел богов. (James O. Coplien, Bell Labs)

Факториал

$n!= \begin{cases} 1 & n = 0,\\ n \cdot (n-1)! & n > 0. \end{cases}$

Если в лоб записать определение факториала на python, то получится линейно рекурсивная функция.

def factorial(n):
    if n == 0:
        return 1

    return n * factorial(n-1)

print(factorial(10) == 3628800)

Нарисуйте на доске процесс вычисления факториала. У вас должна получиться серия расширений, а потом сжатий отложенных операций.

Этот процесс расширения и сжатия называется рекурсивным процессом. В случае с факториалом мы имеем дело с линейнорекурсивным процессом, так как объем информации, требуемый для запоминания отложенных операций растет линейно.

Фибоначчи

Этот вид рекурсии называется древовидным. Нарисуйте процесс порождаемый при вычислении $F(5)$ и вы увидите, что он напоминает дерево. Как вы думаете на сколько это оптимальный процесс?

$F = \begin{cases} F(0)=1; \\ F(1) = 1; \\ F(n) = F(n-1) + F(n-2),\quad n > 1. \end{cases}$

Maximum

Поиск максимального элемента в коллекции

maximum(1, 3, 2, 6, 5, 1) == 6

Summa

Сумма цифр числа рекурсивным методом.

summa(1234) == 1 + 2 + 3 + 4 == 10

Average

Вычисление среднего арифметического чисел в коллекции.

$avg(X) = \frac{1}{N} \sum{N} \ where \ N - is \ a \ number \ of \ elements \ in \ the \ collection \ X$

avg(1,1,1) == 1.0
avg(2,3,4) == 3.0

Домашнее задание

Циклы for и while использовать запрещено. Глобальные переменные использовать тоже запрещено. Классы и статические переменные функции запрещены. У вас есть только рекурсия!

В этот раз вы сами должны написать Unit-тесты. Сигнатуру функции тоже придумайте сами, но предполагайте, что вашу функцию будет использовать кто-то в своей задаче, поэтому она должны быть простой.

Ханойская башня

Даны 1 пирамидка с дисками разного размера, и еще 2 пустые пирамидки.
Надо переместить диски с одной пирамидки на другую.
Перекладывать можно только по одному диску за ход.
Складывать диски можно только меньший на больший.

Хорошее описание тут.

Ханойская башня

Hints

Функция должна возвращать процесс перекладывания дисков.

Напишите сами необходимый набор юнит тестов, чтобы проверить правильность этого процесса.

Обычные реализации используют print, чтобы выводить результаты в консоль. Потом человек смотрит на вывод глазами и понимает, что функция работает верно. Тогда почему мы не можем сделать так, чтобы проверять это автоматически?

Test cases

Вы можете не использовать такой формат тестов, можете придумать свой.

# -*- coding: utf-8 -*-

import unittest


def process_tower(height):
    """
    We have 3 rods.

    The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
        Only one disk can be moved at a time.
        Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
        No disk may be placed on top of a smaller disk.

    :param height: is the count of disks on the first rob of the tower
    :return: process of moving disks
    """
    return []

class TestProcessTower(unittest.TestCase):
    def test_empty(self):
        self.assertListEqual(process_tower(0), [])

    def test_one_height(self):
        self.assertListEqual(process_tower(1), ["0->1. [[], [0], []]"])

    def test_three(self):
        self.assertListEqual(process_tower(3), [
            "0->1. [[2, 1], [0], []]",
            "0->2. [[2], [0], [1]]",
            "1->2. [[2], [], [1, 0]]",
            "0->1. [[], [2], [1, 0]]",
            "2->0. [[0], [2], [1]]",
            "2->1. [[0], [2, 1], []]",
            "0->1. [[], [2, 1, 0], []]"
        ])

    def test_five(self):
        operations = ['0->1. [[4, 3, 2, 1], [0], []]', '0->2. [[4, 3, 2], [0], [1]]', '1->2. [[4, 3, 2], [], [1, 0]]',
                      '0->1. [[4, 3], [2], [1, 0]]', '2->0. [[4, 3, 0], [2], [1]]', '2->1. [[4, 3, 0], [2, 1], []]',
                      '0->1. [[4, 3], [2, 1, 0], []]', '0->2. [[4], [2, 1, 0], [3]]', '1->2. [[4], [2, 1], [3, 0]]',
                      '1->0. [[4, 1], [2], [3, 0]]', '2->0. [[4, 1, 0], [2], [3]]', '1->2. [[4, 1, 0], [], [3, 2]]',
                      '0->1. [[4, 1], [0], [3, 2]]', '0->2. [[4], [0], [3, 2, 1]]', '1->2. [[4], [], [3, 2, 1, 0]]',
                      '0->1. [[], [4], [3, 2, 1, 0]]', '2->0. [[0], [4], [3, 2, 1]]', '2->1. [[0], [4, 1], [3, 2]]',
                      '0->1. [[], [4, 1, 0], [3, 2]]', '2->0. [[2], [4, 1, 0], [3]]', '1->2. [[2], [4, 1], [3, 0]]',
                      '1->0. [[2, 1], [4], [3, 0]]', '2->0. [[2, 1, 0], [4], [3]]', '2->1. [[2, 1, 0], [4, 3], []]',
                      '0->1. [[2, 1], [4, 3, 0], []]', '0->2. [[2], [4, 3, 0], [1]]', '1->2. [[2], [4, 3], [1, 0]]',
                      '0->1. [[], [4, 3, 2], [1, 0]]', '2->0. [[0], [4, 3, 2], [1]]', '2->1. [[0], [4, 3, 2, 1], []]',
                      '0->1. [[], [4, 3, 2, 1, 0], []]']
        self.assertListEqual(process_tower(5), operations)


if __name__ == '__main__':
    unittest.main()