Различия между версиями 2 и 19 (по 17 версиям)
Версия 2 от 2010-11-24 14:48:25
Размер: 1066
Редактор: PavelSutyrin
Комментарий:
Версия 19 от 2010-12-01 14:42:10
Размер: 3908
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 9: Строка 9:
  * Рекурсивные определения и рекурсивные вычисления
  * Перебор с возвратами
Строка 13: Строка 15:
  * Функции-генераторы, оператор yield
  * Выражения-генераторы
Строка 19: Строка 19:
  1. {i} Прочитать в учебнике про [http://ru.wikibooks.org/wiki/%D0%A3%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA_Python_2.6#.D0.93.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.82.D0.BE.D1.80.D1.8B генераторы]   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 различных путей коня.
    * Решение без использования рекурсии. тем не менее всё ещё не эффективное. Почему? [[attachment:konjK.py]]
   

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

  • {o} — тема по Linux

  • <!> ­— необязательная тема

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

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

  • {i} — теоретическое задание

  • {*} — новая тема

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

  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 с коэффициентами 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())
  5. Решить следующую задачу методом рекурсивного перебора с возвратами. Найти путь (список координат полей), по которому шахматный конь, начав в левом верхнем углу доски (NxN полей, N > 5) обойдет ее всю, побывав на каждом поле всего один раз.

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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/2010-11-24 (последним исправлял пользователь FrBrGeorge 2010-12-01 14:42:10)