590
Комментарий:
|
3730
|
Удаления помечены так. | Добавления помечены так. |
Строка 6: | Строка 6: |
Какое-нибудь описание. | |
Строка 10: | Строка 9: |
* Подтема 1 * {o} Подтема 2 |
* Рекурсивные определения и рекурсивные вычисления * Перебор с возвратами * Параметры функций: позиционные, именованые. Объявление, вызов. * Работа с группами параметров .format() * lambda-выражения (безымянные функции) * map(), zip() |
Строка 16: | Строка 19: |
1. {i} Первое 1. Второе |
1. {i} Почитать [[http://kufas.ru/programming167.htm|О рекурсивных и переборных алгоритмах]]. 1. Написать рекурсивную функцию 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()) }}} 1. Написать рекурсивную функцию для подсчета количества цифр неотрицательного целого n. Подсказка: подумать, как выразить решение всей задачи через подзадачу меньшего размера. Где здесь размер задачи?.. {{{ def ndig(n): if n < 10: return 1 else: return 1 + ndig(n/10) print ndig(input()) }}} 1. Дан многочлен степени n с коэффициентами a,,0,,, a,,1,,, a,,2,,, ..., a,,n,, (a,,n,, -- коэффицинт x в степени n). Написать рекурсивную функцию {{{polyval}}} для вычисления его значения в точке x,,0,,. Функция должна поддерживать обращения вида {{{ 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()) }}} 1. Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз. * Довольно неэффективное решение [[attachment:konj.py]] * вариант: Дополнительно дано K > 0, найти K различных путей коня. |
Тема занятия: Функции, рекурсия и переборная схема
— тема по Linux
— необязательная тема
- Рекурсивные определения и рекурсивные вычисления
- Перебор с возвратами
- Параметры функций: позиционные, именованые. Объявление, вызов.
- Работа с группами параметров .format()
- lambda-выражения (безымянные функции)
- map(), zip()
Домашнее задание
— теоретическое задание
— новая тема
Почитать О рекурсивных и переборных алгоритмах.
Написать рекурсивную функцию 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())
Написать рекурсивную функцию для подсчета количества цифр неотрицательного целого n. Подсказка: подумать, как выразить решение всей задачи через подзадачу меньшего размера. Где здесь размер задачи?..
def ndig(n): if n < 10: return 1 else: return 1 + ndig(n/10) print ndig(input())
Дан многочлен степени n с коэффициентами a0, a1, a2, ..., an (an -- коэффицинт x в степени n). Написать рекурсивную функцию polyval для вычисления его значения в точке x0. Функция должна поддерживать обращения вида
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())
Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз.
Довольно неэффективное решение konj.py
вариант: Дополнительно дано K > 0, найти K различных путей коня.