Введение и история | Скачать лекции | Лекции on-line | Список литературы | Примеры приложений | Презентации | Тестирование

Арифметика и простейшие алгоритмы

1. Наибольший общий делитель - алгоритм Евклида.

   Алгоритм Евклида гласит: для нахождения наибольшего общего делителя двух целых положительных чисел нужно подменять большее число его остатком от деления на меньшее до тех пор, пока большее и меньшее числа не будут равны.

   Реализуем это через лямбда-функции.

   Главное правило при программировании в лямбда-функциях питона: не использовать никаких условий. Всё должно быть ясно еще на момент начала выполнения. Поэтому нужно подумать, за сколько шагов (под шагом понимаем взятие остатка от деления) мы гарантированно доберемся до цели.

   Математическое ожидание NmodM равно M/2, т.е. на каждом шаге, начиная со второго, оба аргумента уменьшаются приблизительно в два раза. Hо это получится нечто вроде оценки сверху мат.ожидания числа шагов алгоритма, а не оценка сверху. Оценку сверху можно получить так: худший случай - это когда NmodM принадлежит (M/2,2*M/3). Почему плохо это и особенно это? Потому что если остаток будет меньше М/2, то оценка логарифмом по основанию 2 будет хорошей, а если больше 2*М/3, то эта же оценка станет хорошей на следующем шаге. Получаем, что число шагов ограничено логарифмом по основанию 3/2 от меньшего аргумента.

   Итак, организуем цепочечные вычисления, строя остатки от деления чисел, начиная с двух данных. Кроме того, следует застраховаться от деления на ноль. Последний полученный элемент и будет нашим наибольшим общим делителем.

2. Наименьшее общее кратное.

   Лучший способ для математика решить задачу - это свести её к предыдущей. Применив наши знания в теории, мы легко поймем, что наименьшее обще кратное - это отношение произведения чисел к их наибольшему общему делителю. Задача решена.

3. Факториал.

   Идеальная задача для функционального программирования - можно считать, что список целых чисел, не превосходящих данное, у нас уже есть, осталось лишь применить к нему перемножающую функцию.

4. Поиск простых чисел.

   Формулу для k-го простого числа мы выводить не будем, хотя бы потому, что эта задача до сих пор считается нерешенной. Попробуйте поразмышлять над этой проблемой на досуге - если получите формулу, вас сразу примут в Академию Наук.

   Что такое простое число? Согласно определению, простое число не делится без остатка ни на какое другое число. Понятно, что нет смысла проверять делимость на числа, превышающие исходное. Более того, простой делитель числа не может превышать его корня. Hапишем сначала функцию, составляющую список всех остатков от деления данного числа на другие:
   Z=lambda n:map(lambda a,b=n:b%a,range(2,pow(n,0.5)+1))
   Если в этом списке есть хотя бы один ноль, это означает, что число n делится без остатка на какое-то другое число, то есть, что n не простое. Построим функцию, возвращающую 1, если в данном ей списке нет нулей и 0 в противном случае:
   Y=lambda l:reduce(lambda c,d:c*d!=0,l,1)
   Теперь Y(Z(n)) возвращает 1, если n - простое и 0 в противном случае. Половина дела уже сделана. Осталось реализовать перебор всех чисел из какого-то промежутка, то есть построить отображение (map) списка последовательных чисел в список нулей и единиц. В таком случае единицы будут стоять на местах, обозначающих номер простого числа. Будет лучше, если вместо единиц мы будем выдавать само число, тогда, удалив все нули и списка, мы получим список простых чисел без лишних усилий.
   X=lambda m:map(lambda e:e*Y(Z(e)),range(2,m))
   Hу и не забываем удалить нули - это для нас проще простого:
   W=lambda k:filter(None,X(k))

   Теперь подставим Z в Y, Y в X, а X в W (не забывая, что разные переменные из разных областей действия имён могут иметь одинаковые имена), а затем ужаснемся результату наших усилий.
   

5. Разложение целого числа на множители.

   Аналитическое решение этой задачи также достойно будущих академиков. Мы же пока что решим её перебором - медленно, но верно. Воспользуемся функцией проверки числа на делимость другим (она была написана нами в предыдущем примере). Только не стоит забывать, что множители могут (и должны) превосходить корень исходного числа. Чтобы не менять концептуальные части, будем добавлять вместе с каждым делителем результат деления исходного числа на него. Это обнаружит маленькую проблему: если число имеет целый корень, он будет включен в список дважды. Не ограничивая себя функциональным программированием (мы же на питоне пишем, а не на лиспе!), напишем обрамляющую подпрограмму, удаляющую повторное вхождение корня и сортирующую список по возрастанию. Готово! Как мы и задумывали в самом начале, медленно.

#!/usr/bin/env python
"""
 Секция 1. Работа с числами.
 В данный модуль входят следующие функции:

  primes(x) - поиск простых чисел, не превосходящих данное
  nod(a,b) - наибольший общий делитель двух чисел
  nok(a,b) - наименьшее общее кратное двух чисел
  factorial(n) - факториал целого положительного числа
  factors(N) - разложение числа на множители

"""

# Пошли лямбда-функции

# 1
primes=lambda x:filter(None,map(lambda x:x*reduce(lambda x,y:x*y!=0,
                map(lambda y,x=x:x%y,range(2,1+pow(x,0.5))),1),range(2,x)))
nod=lambda x,y:reduce(lambda a,N:a+[(a[N]-1)%a[N+1]+1],
               range(0,log(max(x,y))/log(1.5)),[x,y]).pop()
nok=lambda A,B:A*B/nod(A,B)
factorial=lambda n:reduce(lambda x,y:x*y,range(2,n+1),1L)
facts=lambda N:reduce(lambda a,n,N=N:a+[n,N/n],
      filter(None,map(lambda k,N=N:(not(N%k))*k,range(1,pow(N,0.5)+1))),[])

# Лямбда-функции кончились, начались обычные (обрамляющие)

# 1
def factors(N):
 a=facts(N)
 if a[-1]!=pow(N,0.5): a+=[pow(N,0.5)]
 a.pop()
 a.sort()
 return a

if __name__ == "__main__":
 print primes(50)