Задание на лабораторную работу 2.

⇐ ПредыдущаяСтр 7 из 13Следующая ⇒

1. Определите функции для вычисления чисел Фибоначчи по номеру и для вычисления факториала. С помощью них определите собственную функцию, записанную в условной математической нотации. (fib(n) - означает n-е число Фибоначчи).

2. Определите рекурсивные функции (задание в варианте) для решения задачи, постарайтесь по возможности не использовать встроенные списочные функции.

3. В задании описаны правила составления некоторого пароля. Написать функцию, проверяющую удовлетворяет ли заданная строка данным правилам, используя различные функции из модуля Char.

4. Зашифруйте заданную строку с помощью шифра Цезаря с ключом, соответствующим номеру варианта. Напишите функцию для расшифровки (можно одну функцию с дополнительным аргументом, задающим режим шифровки или расшифровки). Внимание! Шифроваться должны только буквы, все остальные символы должны оставаться без изменений. Шифр Цезаря означает циклический сдвиг каждого символа в строке на число, равное коду.

5. Дано универсальное множество U={1,2,…,10} и некоторые его подмножества A,B,C. Найти множество D, заданное в варианте. Реализовать множества списками и использовать функции из модуля List.

6. Написать функцию двух аргументов строкового типа, для выполнения арифметической операции. Вид операции, представление аргументов(система счисления) и результат в варианте задан в следующем виде:

Операция	1-й аргумент	2-й аргумент	Результат

При выполнении непосредственно арифметической операции разрешается использовать любую систему счисления (в т.ч. десятичную).

7. Используя функции show, read, error, undefined (не обязательно все сразу) напишите функцию, выполняющую указанные действия.

Вариант 1.

1. F(n,m)=fib(n+m+1)-min{n!,m!}

2. а) Удалить из числового списка все элементы, кратные 4;

б) вывести номер последнего вхождения в список натуральных чисел четного элемента. При отсутствии четных элементов вывести -1.

3. а)первый символ не может быть цифрой; б) пароль содержит не более двух заглавных букв; в)сумма встречающихся цифр должна быть четна.

Операция	1-й аргумент	2-й аргумент	Результат
сложение	римская	двоичная	16-ричная

7. По введенному возрасту печатает статус человека: дошкольник(0-6), школьник(7-17), студент(18-22), работник(23-55), пенсионер(55-90). При значении возраста вне данных интервалов выводит соответствующие сообщения об ошибках.

Вариант 2.

1. F(n)=(n-1)! - fib(2*n+1)

2. а) Вычислить сумму элементов списка, кратных 3;

б) получить список индексов элементов числового списка, меньших 5.

3. а)должен содержаться знак подчеркивания, но не на первом и не на последнем месте; б)количество заглавных букв не должно превышать количество строчных.

Операция	1-й аргумент	2-й аргумент	Результат
умножение	8-ричная	римская	16-ричная

7. По введенной строке формата «hh:mm» печатает сообщение о номере пары или перерыва в УГАТУ, соответствующих данному времени (10:21 – вторая пара; 15:55 – второй большой перерыв и т.п.). При введенных значениях вне учебного времени (либо не являющихся временем суток – 52:81, например) выводит соответствующие сообщения об ошибках.

Вариант 3.

1. F(n,m,l)= fib(n!+2*max{m,l}-min{m,l})

2. а) Удалить из строки все элементы, равные заданному символу;

б) найти произведение индексов (начиная с 1) четных элементов числового списка, при отсутствии четных элементов вывести -1.

3.а)не должен содержать латинских заглавных букв, стоящих в алфавите после ‘T’ б) содержит только четные цифры.

Операция	1-й аргумент	2-й аргумент	Результат
вычитание	8-ричная	двоичная	римская

7. По введенным датам рождения и смерти в формате «dd.mm.yyyy» вычисляет продолжительность жизни человека в годах, месяцах и днях. Выводит соответствующие сообщения об ошибках в данных.

Вариант 4.

2. а) Вычислить количество вхождений в числовой список минимальных элементов;

б) найти сумму индексов нечетных элементов числового списка.

3. а) должен начинаться с нечетной цифры; б) содержать не менее трех строчных букв; в) не содержать более одного символа, не являющегося ни цифрой и ни буквой.

Операция	1-й аргумент	2-й аргумент	Результат
сложение	16-ричная	двоичная	римская

7. По введенной дате в формате «dd.mm» определяет знак гороскопа(зодиакального). Выводит соответствующие сообщения об ошибках в данных.

Вариант 5.

1. F(n,m,l)=min{m!,l!}-fib(max{n,m})

2. а) Вычислить количество вхождений в строку (общее) символов «а», «b», «с»;

б) получить список индексов тех элементов числового списка, которые кратны трем.

3. а) содержит только двоичные цифры; б) заканчивается заглавной буквой .

Операция	1-й аргумент	2-й аргумент	Результат
умножение	римская	двоичная	16-ричная

7. По введенной дате в формате «dd.mm» выводит сообщение о номере учебной четверти или о виде каникул для школьников ( 07.01 – «зимние каникулы», 24.10 – первая учебная четверть и т.п.). Выводит соответствующие сообщения об ошибках в данных.

Вариант 6.

1. F(n)=min{fib(n!),(fib(n)+n)!}

2. а) Вычислить количество элементов числового списка, не превышающих заданного числа;

б) найти индекс первого вхождения в числовой список максимального элемента.

3. а)число символов ‘(’ равно числу символов ‘)’ ; б)не содержит гласных строчных латинских букв.

Операция	1-й аргумент	2-й аргумент	Результат
вычитание	4-ричная	римская	16-ричная

7. Составить расписание на день (6-10 пунктов, например 00:00 – 07:00 Сон. 07:00-08:00 Завтрак, поездка в университет и т.д.). По введенному времени в формате «hh:mm» напечатать соответствующий пункт расписания. Вывести соответствующие сообщения об ошибках в данных.

Вариант 7.

1. F(n,m)=(n mod m)! +fib(m mod n)

2. а) Вычислить произведение четных элементов числового списка;

б) преобразовать список в кортеж двух списков – с нечетными и четными индексами соответственно.

3. а) не содержит символов строчных латинских букв, предшествующих ‘k’; б) сразу после любой точки(если таковые есть) должна следовать цифра.

Операция	1-й аргумент	2-й аргумент	Результат
сложение	римская	двоичная	8-ричная

7. По вводимой температуре наружного воздуха в градусах выводит сообщения о реакции человека (реакции написать самостоятельно – например, «Лютый мороз», «Немного жарко» и т.п.). Выводит соответствующие сообщения об ошибках в данных.

Вариант 8.

1. F(n,m,l)= ! - fib( )

2. а) Вернуть первый элемент списка натуральных чисел, кратный 5. При отсутствии такого элемента вернуть 0;

б) удалить из списка элементы, индексы которых кратны 3.

3. а) не должен содержать двух символов ‘=’ идущих подряд ; б) последней должна быть заглавная согласная буква.

Операция	1-й аргумент	2-й аргумент	Результат
умножение	двоичная	16-ричная	римская

7. По вводимым в билете пригородной электрички временам отправления и прибытия в формате «hh:mm» выводит время пути в часах и минутах. Выводит соответствующие сообщения об ошибках в данных.

Вариант 9.

1. F(n,m)=(min{n,m})!-fib( )

2. а) Найти произведение элементов списка, больших заданного числа;

б) найти номер последнего вхождения в список нечетного числа.

3. а) должен содержать четное количество цифр; б) код второго символа не должен превышать кода первого; в) содержит хотя бы одну строчную букву.

Операция	1-й аргумент	2-й аргумент	Результат
вычитание	16-ричная	римская	8-ричная

7. .По введенной дате в формате «dd.mm» выводит сообщение о празднике (определить самостоятельно 5-10 праздников.). Выводит соответствующие сообщения об ошибках в данных.

Вариант 10.

1. F(n,m)=НОД(fib(n),(n mod m)!)

2. а) Найти количество вхождений последнего элемента;

б) получить список элементов числового списка, совпадающих со своими индексами.

3. а)должен содержать хотя бы один из четырех символов основных арифметических операций; б) не может заканчиваться заглавной буквой.

Операция	1-й аргумент	2-й аргумент	Результат
умножение	римская	16-ричная	4-ричная

7. По введенному году рождения определяет знак восточного гороскопа. Выводит соответствующие сообщения об ошибках в данных.

Пример выполнения работы

1. F(n,m)=max (fib(n+m),|n-m|!)

Решение.

Исходный код:

Пример работы:

2. а) Найти произведение элементов числового списка, кратных 3.

Решение.

Для написания рекурсивной функции сразу определим т.н. базу рекурсии – момент, когда алгоритм должен остановиться. Обычно это должно происходить в случае пустого списка или одноэлементного. Напишем базу рекурсии для пустого списка, пусть функция в этом случае возвращает 1 (почему именно 1? Можно сказать, это начальное значение аккумулирующей переменной, так как нам нужно вычислить произведение, то следует взять 1. Если бы мы вычисляли сумму, следовало бы взять 0).

foo7 [] = 1

Далее рассуждаем так: мы видим в списке первый элемент и все остальные, можно обращаться к ним через функции head и tail, но проще в объявлении сразу «расчленить» список на голову x и хвост xs таким образом:

foo7 (x:xs) = …

Анализируя голову списка х можно выделить 2 варианта:

1) х кратно 3. В этом случае нам надо умножить этот элемент на результат «обработанного хвоста», то есть на произведение элементов, кратных 3 в хвосте списка. Как его получить? Очень просто, вызвать рекурсивно нашу функцию с аргументом, равным хвосту списка xs.

2) х не кратно 3. Ситуация еще проще, достаточно вычислить нашу функцию для хвоста списка, не обращая внимания на х.

Окончательно, запишем код (используя рассмотренные условия и результаты):

б) Найти номер последнего вхождения минимального элемента.

Напишем следующие функции (без пояснений, разберитесь самостоятельно) :

mymin l - находит в списке l минимальный элемент

search l a n – находит в списке l позицию первого вхождения элемента а (при отсутствии элемента возвращает - 1)

myreverse l – переворачивает список l

foo7a l – основная функция

б) еще один пример задания 2:

Получить список индексов элементов числового списка, кратных 4 .

Решение.

В том случае, когда мы пишем рекурсивную программу, работающую с индексами списка, необходимо завести дополнительный аргумент для определения того, с каким именно элементом по номеру (индексу) мы сейчас работаем. С другой стороны, по тексту задания наша функция должна иметь один входной аргумент – список. Для решения этой проблемы пусть наша главная функция с одним аргументом (нерекурсивная) будет вызывать вспомогательную (рекурсивную) уже с двумя аргументами – исходным списком и начальным значением индекса.

foo2b l = fooо2b l 0

Теперь будем работать с этой вспомогательной функцией. Напишем базу рекурсии для пустого списка. Очевидно, результатом в этом случае будет также пустой список. Заметим, что значение второго аргумента – индекса нам совершенно не нужно, в этом случае можно объявить его как анонимную переменную, знаком подчеркивания:

fooо2b [] _ = []

Теперь напишем обработку непустого списка. Итак, мы видим голову списка – x, его хвост – xs, а также знаем индекс головы – n.

fooо2b (x:xs) n

Нам надо проверить, кратен ли элемент x четырем и….Вот тут возникает самый сложный вопрос – и что сделать? При написании рекурсивных программ тут следует задать себе вопрос – пусть есть уже результат для хвоста списка, что следует сделать с этим результатом и нашими текущими аргументами? Поясним на примере для этого задания. Пусть список у нас [8,3,5,24,16], результатом должен быть список [0,3,4]. Если у нас в начале вызова функции голова х=8, хвост xs=[3,5,24,16] и индекс головы n=0, то результатом для хвоста xs=[3,5,24,16] является список индексов [3,4]. Как из списка [3,4] и знания x=8 и n=0 получить результат [0,3,4]? Ответить уже просто – проверить элемент x=8 на кратность четырем и в случае положительного ответа присоединить к списку [3,4] в качестве головы индекс n=0, это делается с помощью функции (:). При рекурсивном вызове функции не забываем, что индекс должен увеличиться на единицу:

fooо2b (x:xs) n

| (x `mod` 4 == 0) = n: fooо2b xs (n+1)

Осталось дописать обработку головы в том случае, если голова списка не кратна четырем. Очевидно, достаточно ничего не присоединять к результату обработки хвоста:

fooо2b (x:xs) n

| (x `mod` 4 == 0) = n: fooо2b xs (n+1)

| оtherwise = fooо2b xs (n+1)

Итак, исходный код:

Пример работы:

3. В задании описаны правила составления некоторого пароля. Написать функцию, проверяющую удовлетворяет ли заданная строка данным правилам, используя различные функции из модуля Char.

а) не должен содержать двух подряд идущих гласных букв б) должен содержать хотя бы один знак пунктуации в) все входящие символы – цифры должны быть кратны трем

Решение:

Приведем код без подробных объяснений:

а) не должен содержать двух подряд идущих гласных букв

б) должен содержать хотя бы один знак пунктуации

Можно написать рекурсивную функцию так:

А можно (ознакомившись с функциями модуля List и не забыв его подключить) написать так:

в) все входящие символы – цифры должны быть кратны трем

вариант рекурсивной функции:

вариант с использованием функций модуля List:

Окончательно, создадим проверяющую все условия одновременно функцию (в случаях б и в вариант выбран произвольно):

Полный код программы:

Пример выполнения:

4. Покажем пример шифровки, производящейся по следующему правилу: каждая буква , стоящая на n-м месте в латинском алфавите заменяется на букву, стоящую на (26-n) месте, т.е. «a» заменяется на «z» ,«b» на «y» и так далее. Договоримся, что шифровать будем только буквы, прочие символы будем оставлять без изменений. Запишем нашу функцию так (основную часть - обработку букв пока заменим многоточием, вернемся к этому позже):

foo4 [] = [] {база рекурсии: если аргумент – пустая строка, результат также пустая строка}

foo4 (x:xs)

| isAlpha x = … {тут будет обработка букв}

| otherwise = x: foo4 xs {если символ – не буква , просто переписываем его в результирующую строку и переходим к обработке хвоста}

Не забываем написать в начале базу рекурсии, так как мы работаем со строкой посимвольно, и рано или поздно строка станет пустой.

Итак, пусть у нас есть символ x, являющийся буквой. Как получить её номер в алфавите? Функция ord, определенная в модуле Char, вернет нам номер символа в таблице ASCI. Латинские буквы в таблице ASCI идут подряд, поэтому для получения номера в алфавите следует написать следующее выражение:

ord x – ord 'a' + 1

(единицу добавляем для того, чтобы нумерация начиналась с единицы, а не с нуля). Соответственно, чтобы получить номер буквы, которой мы собираемся заменить текущий символ, надо от 26 отнять последнее выражение. Затем прибавить снова код буквы 'a', чтобы получить код буквы в таблице, и преобразовать номер в символ с помощью функции chr:

chr (25- ord x + 2*(ord 'a')) .

Следует учесть, что сейчас мы написали правильную шифровку только строчных букв. Для прописных букв необходимо написать аналогичное выражение, но использовать код символа 'A', дело в том, что строчные и прописные буквы в таблице расположены не подряд. Окончательно, функция шифровки примет вид:

foo4 [] = []

foo4 (x:xs)

| isAlpha x = if isLower x then chr (25- ord x + 2*(ord 'a')) : foo4 xs

else chr (25- ord x + 2*(ord 'A')) : foo4 xs

| otherwise = x: foo4 xs

Пример выполнения:

В данном примере видно, что для обратной дешифровки достаточно повторно применить функцию шифровки. При работе же с шифром Цезаря вам предлагается самостоятельно продумать вопрос о функции дешифровки.

5. Дано универсальное множество U={1,2,…,10} и некоторые его подмножества A,B,C. Найти множество D, заданное в варианте. Реализовать множества списками и использовать функции из модуля List.

Решение. В модуле List определены следующие функции работы со списками, как с множествами:

union - объединение множеств,

intersect – пересечение множеств,

\\ - разность множеств.

Для реализации симметрической разности, вспомним её свойство:

Функцию для вычисления дополнения множества напишем самостоятельно:

complement x = [1..10] \\ x .

Окончательно, наша функция будет иметь вид:

Пример выполнения:

Операция	1-й аргумент	2-й аргумент	Результат
вычитание	16-ричная	римская	2-ичная

Решение.

Приведем код без подробных объяснений:

1) перевод строки – числа в 16-ричном представлении в десятичное число:

2) перевод строки- римского числа в десятичное число (строго говоря, здесь для простоты не проводится проверка правильности числа, записанного в римской системе. Например, строка «IL» будет преобразована в число 49, хотя на самом деле 49 должно быть записано как «XLIX». Если студент при выполнении работы учтет все правила для римской системы счисления, это будет только приветствоваться.):

3) перевод десятичного числа в двоичную строку:

Окончательно, функция, выполняющая все преобразования и вычисления:

Пример выполнения:

(здесь из 26 вычитается 14 и результат 12 преобразуется в двоичное представление)

7. По введенной дате в формате «dd.mm» выводит количество полных прошедших недель с начала года. Выводит соответствующие сообщения об ошибках в данных

Решение.

Локальные функции m и d выдают, соответственно, номер месяца и дня, а локальная функция list содержит максимальные числа дней для каждого месяца.

Пример выполнения:

Лабораторная работа 3.

Функции высших порядков.

Функции высших порядков являются отличительной особенностью функционального программирования. Кратко дать определение функции высшего порядка можно так – это функция имеющая аргументами другие функции или возвращающая в качестве результата другую функцию.

Рассмотрим сначала две функции, являющиеся предикатами, то есть возвращающими логические значения. Функция any имеет два аргумента и проверяет, содержит ли второй аргумент – список хотя бы один элемент, удовлетворяющий первому аргументу. Первый аргумент этой функции сам является функцией, возвращающей логическое значение.

Функция all проверяет выполнение первого аргумента для всех элементов своего второго аргумента:

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

Одной из важнейших функций высшего порядка является функция map, встречающаяся во всех функциональных языках и даже в декларативных, таких как C++, Ruby, Python и других. Эта функция применяет свой первый аргумент – функцию последовательно к каждому элементу второго аргумента – списка. Вот примеры её вызова:

Функция filter оставляет во втором аргументе списке только элементы, удовлетворяющие первому аргументу – предикату:

Функция zip, вообще говоря, не являющаяся функцией высшего порядка, позволяет из двух списков создать список кортежей, объединяющих попарно элементы списков:

Заметьте, что длина результирующего списка будет равна длине кратчайшего из списков аргументов. Если же списки у нас одного типа, то к ним можно применить функцию высшего порядка zipWith, которая применяет свой первый аргумент-функцию к каждой паре элементов второго и третьего аргументов – списков:

Функцией, производящей обратное к zip преобразование, является функция unzip:

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

Функция $ понижает приоритет функции, в данном примере использована как замена вложенных скобок. Функция (.) означает композицию функций в математическом смысле, её определение в Haskell:

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

Также в модуле List определена функция sort, сортирующая числовой список в порядке неубывания. Но во многих случаях требуется сортировать более сложные структуры данных, чем простой список. В этом случае надо воспользоваться функцией высшего порядка sortBy, первым аргументом которой будет функция сравнения. Например, для сортировки списка строк по длине можно написать так:

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

Аналогично, существуют функции высшего порядка nubBy, deleteBy, deleteFirstsBy (By-вариант \\), unionBy, intersectBy, groupBy, sortBy, insertBy, maximumBy, minimumBy. Например, для удаления из списка кортежей элементов с повторяющейся суммой можно использовать:

При выполнении третьего задания данной лабораторной работы будут полезны функции высшего порядка из модуля Prelude, позволяющие разбивать или делить список на части по какому-либо условию, приведенные в таблице 3.1.

Таблица 3.1. Функции высшего порядка разделения списка.

Описание	Имя функции	Пример
Получает список первых элементов, удовлетворяющих условию	takeWhile
Отбрасывает первые элементы, удовлетворяющие условию	dropWhile
Разбивает список на кортеж двух списков – первый содержит первые элементы, удовлетворяющие условию, второй – все остальные элементы	span
Разбивает список на кортеж двух списков – в первом первые элементы, не удовлетворяющие условию, во втором – все остальные элементы	break
Разбивает список на кортеж двух списков – в первом первые n элементов, во втором – все остальные элементы	splitAt

Среди функций высшего порядка модуля Prelude есть несколько функций, называемых свертками. Они позволяют применять функцию-параметр последовательно к элементам списка. В зависимости от порядка применения функции к аргументу-списку есть левая и правая свертки. Многие стандартные функции, например, sum, product, maximum, minimum, reverse определены с помощью функций-сверток. Ознакомьтесь с ними в таблице 3.2.

Таблица 3.2. Функции-свертки.

Описание	Имя функции	Пример	Примечание
Правая свертка с аккумулятором	foldr		foldr f a [x₁,x₂,..,x_n] = =f x₁ (f x₂ (..(f x_n a))..) foldr (-) 20 [2,5,3] = 2-(5-(3-20))
Левая свертка с аккумулятором	foldl		foldl f a [x₁,x₂,..,x_n] = =f (f (f a x₁) x₂)..) x_n) foldl (-) 20 [2,5,3] = ((20-3)-5)-2
Правая свертка	foldr1		foldr f a [x₁,x₂,..,x_n] = =f x₁ (f x₂ (..(f x_n-1 x_n ))..) foldr1 (-) [20,5,3] = (20-(5-3))
Левая свертка	foldl1		foldl f a [x₁,x₂,..,x_n] = =f (f (f x₁ x₂) x₃)..) x_n) foldl1 (-) 20 [2,5,3] = ((20-5)-3)

При выполнении заданий 5 и 7 следует помнить, что в Haskell можно работать с функциями, как с данными. Функции могут быть элементами списков или кортежей, и подвергаться применению списочных или кортежных функций. При вызове функций с аргументами–функциями последние могут заключаться в круглые скобки. Например, применение каждой из списка функций к аргументу 5:

Дата добавления: 2019-03-09; просмотров: 845; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒

Мы поможем в написании ваших работ!