Тема занятия: Функции, рекурсия и переборная схема

• Рекурсивные определения и рекурсивные вычисления
• Перебор с возвратами
• Параметры функций: позиционные, именованые. Объявление, вызов.
• Работа с группами параметров .format()
• lambda-выражения (безымянные функции)
• map(), zip()

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

1. Почитать О рекурсивных и переборных алгоритмах.

2. Написать рекурсивную функцию factorial(n), без проверки на отрицательный параметр. Выяснить, как ведет себя эта функция в случае "бесконечной рекурсии", т.е. неограниченного уменьшения параметра в рекурсивных вызовах. Поправить функцию так, чтобы при некорректном параметре возвращался None

     def factorial(n):
       if n < 0:
           return None
       elif n < 2:
           return 1
       else:
           return n * factorial(n - 1)
     print factorial(input())

3. Написать рекурсивную функцию для подсчета количества цифр неотрицательного целого n. Подсказка: подумать, как выразить решение всей задачи через подзадачу меньшего размера. Где здесь размер задачи?..

     def ndig(n):
       if n < 10:
           return 1
       else:
           return 1 + ndig(n/10)
     print ndig(input())

4. Дан многочлен степени n с коэффициентами a₀, a₁, a₂, ..., a_n (a_n -- коэффицинт x в степени n). Написать рекурсивную функцию polyval для вычисления его значения в точке x₀. Функция должна поддерживать обращения вида

     polyval(0.5, (1,2,3)) # 1+2x+3x^2 в точке x=0.5

   для любого n.

   • вариант: поддерживать обращения вида

       polyval(0.5, 1, 2, 3) # 1+2x+3x^2 в точке x=0.5

     для любого n.

       def polyval(x, *coeff):
           '''1+2x+3x^2 == 1+x(2+x(3))'''
           if len(coeff)==1:
               return coeff[0]
           else:
               return coeff[0]+x*polyval(x,*coeff[1:])
       print polyval(*input())

5. Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз.

   • Довольно неэффективное решение konj.py

   • вариант: Дополнительно дано K > 0, найти K различных путей коня.

     • Решение без использования рекурсии. тем не менее всё ещё не эффективное. Почему? konjK.py

CategoryClass CategoryVmsh