Министерство  образования Республики Беларусь 

Учреждение  образования

«Полоцкий государственный университет» 
 
 
 
 

Кафедра технологий программирования 
 
 

КОНТРОЛЬНАЯ РАБОТА 

По курсу: «Функциональное программирование» 
 
 
 

    Группа 09-ИТз1   

Зачетная  книжка № 09101119 

    Вариант № 20    
 

Выполнил               Терешков А.С. 

Проверил                 Кухта С.В. 
 
 
 
 
 

Полоцк

2011

Содержание 

 

Задача № 1

1.1 Анализ задания и постановка задачи

 

     Построить рекурсивную функцию для вычисления n-го члена последовательности, в которой каждый следующий четный член равен произведению двух предыдущих, а каждый следующий нечетный член равен сумме двух предыдущих, а первые 2 члена равны соответственно 1 и 2. (Например: 1 2 3 6 9 54 63 ...)

     1.2 Проектирование  программы

 

     Принцип работы программы следующий.  Пользователь вызывает функцию со следующими переданными параметрами: n-ый член последовательности, который необходимо вычислить; первые 2 члена последовательности, которые соответственно равны 1 и 2; и номер шага равный 1. Если текущий элемент последовательности чётный, то каждый следующий будет равен сумме двух предыдущих, в противном случае произведению двух предыдущих. Рекурсивная функция будет работать до тех пор, пока количество шагов не будет равно n-1. 

     1.3 Реализация программы

 

func :: (Integer, Integer, Integer, Integer) -> Integer

func (n, i1, i2, i) = if i == n-1 then i2

                      else

                              if n < 2 then -1

                      else 

                              if even i2 == True then

                                    func(n, i2, i1+i2, i+1)

                              else

                                    func(n, i2, i1*i2, i+1) 

main = func (7, 1, 2, 1)

     1.4 Методика и результаты тестирования

 

     Тесты показали стабильную работу при корректных входных данных.

      Пример:

      

 

Задача  № 2

     2.1 Анализ задания и постановка задачи

 

     Для заданных полиномов  P_n(x)  и   Q_n(x) найти полином   R - сумму полиномов P и Q. Каждый полином представить в виде списка

     2.2 Проектирование программы

 

     Принцип работы программы следующий. Пользователь с клавиатуры вводит два списка. Функция s определяет список максимальной длины и передает его в первом параметре функции suml. Далее в функции suml к элементам первого списка прибавляются элементы второго списка.

     2.3 Реализация программы

 

suml :: [Int]->[Int]->[Int]

suml xs ys = zipWith (+) xs ys 

s a b = let n = length a;

                  m = length b;

                  c = max n m;

                  comp [] o = take o $ repeat 0;

                  comp (g:h) o = g : (comp h $ o-1) in suml (comp a c) (comp b c) 

     main = s [1, 2, 3] [4, 5]

     2.4 Методика и результаты тестирования

 

     Тесты показали стабильную работу при корректных входных данных.

 

Задача  № 3

     3.1 Анализ задания и постановка задачи

 

     Составить программу, реализующую сортировку линейного числового списка на основе бинарного отсортированного дерева.

     3.2 Проектирование программы

 
 

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

     3.3 Реализация программы

 

data Tree a = Leaf | Node (Tree a) a (Tree a)

 

insert :: Ord a => a -> Tree a -> Tree a

insert x Leaf = Node Leaf x Leaf

insert x (Node t y t') | x <= y = Node (insert x t) y t'

insert x (Node t y t') | x > y = Node t y (insert x t')

 

flatten :: Tree a -> [a]

flatten Leaf = []

flatten (Node t x t') = flatten t ++ [x] ++ flatten t'

 

treesort :: Ord a => [a] -> [a]

treesort = flatten . foldr insert Leaf 

main = (readLn::IO[Int]) >>= print . treesort

     3.4 Методика и результаты тестирования

 

     Тесты показали стабильную работу при корректных входных данных.

 
Задача  № 4

     4.1 Анализ задания и постановка задачи

 

     Найти с точностью 0.001 корни уравнения  на отрезке [2.5, 3.5]: .

     4.2 Проектирование программы

 

     Принцип работы программы следующий.  Пользователь с клавиатуры вызывает рекурсивную функцию, в которую передаёт начало отрезка, на котором необходимо найти корни уравнения.  Далее путем вычисления функции и проверки заданной точности происходит поиск корней, если значение корня больше конца отрезка, то выводится сообщение «Net kornei», в противном случае найденный корень.

     4.3 Реализация программы

 

f :: Float -> Float

f x = logBase(10)(x*x+1)-2/logBase(10)(x*x+1)+logBase(10)(6) 

main = search (2.5) 

search x | x > 3.5 = print ("net kornei")

search x = do if abs (f x) < 0.001 then

                  print (x)

                    else

                     search (x+0.001)

     4.4 Методика и результаты тестирования

 

     Тесты показали стабильную работу при корректных входных данных.

 

Литература

 

1. Роганова  Н. А. Функциональное программирование: Учебное пособие для студентов высших учебных заведений – М.: ГИНФО, 2002. – 260 с.
2. Душкин Р. В. Текст лекций по курсу «Функциональное программирование».
3. Гордон М. Введение в функциональное программирование.