Списки и строки
Предисловие
Все представленные ниже лабораторные работы разбиты на четыре темы. Первые три темы, а именно, «Списки и строки», «Бинарные деревья», «Произвольные структуры» включают в себя наборы задач на основной прием программирования в Прологе – рекурсию. При выполнении работ по этим темам допускается использовать любой тип рекурсии (входящую или исходящую). Последняя тема «Файлы и разделы базы данных» предполагает использование в качестве основного приема программирования «вынуждаемый возврат».
Описание каждой задачи состоит из трех частей:
ü словесная формулировка задачи;
ü список аргументов;
ü примеры запросов к разработанной процедуре в среде интерпретатора и получаемые ответы.
При выполнении лабораторных работ требуется строго выполнять два требования:
ü нельзя изменять количество и смысл аргументов;
ü нельзя решать задачу для частных случаев.
Последнее требование означает, что разработанная процедура должна быть универсальна. Так для задачи № 1 (см. ниже) процедура должна работать со списками произвольной длины, содержащими любые термы Пролога.
В примерах запросов все процедуры имеют имя pred. Это не является требованием. Напротив, рекомендуется называть процедуру так, чтобы в наименовании отражался смысл ее работы. Для задачи № 1, например, диалог в интерпретаторе Пролога может быть таким:
?- sorted([a,b,d,f]).
yes
?- sorted([[a,f,b,d]).
no
?-
Списки и строки
1. Определить, является ли список упорядоченным по возрастанию.
Аргументы: исходный список.
?- pred([a,b,d,f]).
yes
?- pred([[a,f,b,d]).
no
?-
2. Определить, имеет ли список четное число элементов, не прибегая к подсчету длины списка.
Аргументы: исходный список.
?- pred([a,b,d,f]).
yes
?- pred([[a,b,d]).
no
?-
3. Перевести число из десятичной системы счисления в двоичную.
Аргументы: число в десятичной с.с.;
число в двоичной с.с. (список).
?- pred(26,X).
X = [1,1,0,1,0]
yes
?-
4. Найти в неупорядоченном списке вещественных чисел ближайших соседей – два числа, расстояние между которыми на вещественной оси является минимальным среди всех возможных пар.
Аргументы: исходный список;
ближайшие соседи (список из двух чисел).
?- pred([0.1,0.04,8.6,7.56,8.11],X).
X = [8.6,8.11]
yes
?-
5. Перевести число из двоичной системы счисления в десятичную.
Аргументы: число в двоичной с.с. (список);
число в десятичной с.с.
?- pred([1,1,0,1,0],X).
X = 26
yes
?-
6. Перевести число из десятичной системы счисления в римскую.
Аргументы: число в десятичной с.с.;
число в римской с.с. (список).
?- pred(24,X).
X = [x,x,i,v]
yes
?-
7. Перевести число из римской системы счисления в десятичную.
Аргументы: число в римской с.с. (список);
число в десятичной с.с.
?- pred([x,x,i,v],X).
X = 24
yes
?-
8. Перевести число из двоичной системы счисления в шестнадцатеричную.
Аргументы: число в двоичной с.с. (список);
число в шестнадцатеричной с.с. (список).
?- pred([1,1,0,1,0],X).
X = [1,a]
yes
?-
9. Перевести число из шестнадцатеричной системы счисления в двоичную.
Аргументы: число в шестнадцатеричной с.с. (список);
число в двоичной с.с. (список).
?- pred([1,a],X).
X = [1,1,0,1,0]
yes
?-
10. Определить, является ли первый список подмножеством второго. Списки не имеют дубликатов.
Аргументы: первый список;
второй список.
?- pred([a,b,c],[s,a,e,c,d,b]).
yes
?-
11. Удалить из списка элементы с четными номерами.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [a,c,e]
yes
?-
12. Удалить из списка те элементы, которые не имеют дубликатов.
Аргументы: исходный список;
результирующий список.
?- pred([a,e,c,d,e],X).
X = [e,e]
yes
?-
13. Дан числовой список – [A,B,C,D,E,…]. Посчитать результат по формуле R=A+B−C+D−E+… .
Аргументы: исходный список;
результат вычислений.
?- pred([1,2,3,4,5],X).
X = -1
yes
?-
14. Сформировать по заданному мужскому имени отчество.
Аргументы: исходная строка (имя);
результирующая строка (отчество).
?- pred(’Иван’,X).
X = Иванович
yes
?-
15. Дан список, содержащий списки одинаковой длины (матрица). Построить транспонированную матрицу.
Аргументы: матрица (список);
транспонированная матрица (список).
?- pred([[1,2,3],[4,5,6],[7,8,9]],X).
X = [[1,4,7],[2,5,8],[3,6,9]]
yes
?-
16. Дан список, содержащий списки одинаковой длины (квадратная матрица). Посчитать детерминант.
Аргументы: матрица (список);
детерминант.
?- pred([[1,2],[4,5]],X).
X = -3
yes
?-
17. Удалить из числового списка элементы, меньшие заданного числа.
Аргументы: исходный список;
число;
результирующий список.
?- pred([3,1,5,4,8],5,X).
X = [5,8]
yes
?-
18. Удалить из списка элемент с заданным порядковым номером.
Аргументы: исходный список;
порядковый номер;
результирующий список.
?- pred([a,b,c,d,e],4,X).
X = [a,b,c,e]
yes
?-
19. Поместить в результирующий список каждый элемент исходного списка с заданной вероятностью.
Аргументы: исходный список;
вероятность вхождения;
результирующий список.
?- pred([a,b,c,d,e],0.5,X).
X = [a,c,d]
yes
?- pred([a,b,c,d,e],0.5,X).
X = [b,c,d,e]
yes
?-
20. Выполнить циклический сдвиг списка влево на заданное количество элементов.
Аргументы: исходный список;
количество элементов;
результирующий список.
?- pred([a,b,c,d,e],3,X).
X = [d,e,a,b,c]
yes
?-
21. Выполнить циклический сдвиг списка вправо на заданное количество элементов.
Аргументы: исходный список;
количество элементов;
результирующий список.
?- pred([a,b,c,d,e],3,X).
X = [c,d,e,a,b] -> ;
yes
?-
22. Получить целое число из строки, использующей числительные русского языка.
Аргументы: строка;
целое число.
?- pred(’Пять тысяч восемьсот одиннадцать’,X).
X = 5811
yes
?-
23. Даны два списка. Каждый из списков не имеет дубликатов и, следовательно, их можно рассматривать как множества. Построить симметрическую разность (объединение минус пересечение) списков.
Аргументы: первый список;
второй список;
результирующий список.
?- pred([a,b,c,d,e],[e,w,q,c],X).
X = [a,b,d,w,q] -> ;
yes
?-
24. Дан список, содержащий числовые списки одинаковой длины (матрица), и числовой список (вектор). Перемножить матрицу и вектор.
Аргументы: матрица (список);
вектор (список);
результат перемножения (список).
?- pred([[1,2],[4,5]],[2,3],X).
X = [8,23]
yes
?-
25. Дан числовой список [a,b,c,d,…] и число x. Посчитать значение полинома R = a+bx+cx2+dx3+… .
Аргументы: список;
число;
результат вычислений.
?- pred([1,2,4,1],3,X).
X = 70
yes
?-
26. Преобразовать целое число в строку с использованием числительных русского языка.
Аргументы: целое число;
строка.
?- pred(5811,X).
X = Пять тысяч восемьсот одиннадцать
yes
?-
27. Выполнить циклический сдвиг списка влево.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [b,c,d,e,a] -> ;
X = [c,d,e,a,b] -> ;
X = [d,e,a,b,c] -> ;
X = [e,a,b,c,d] -> ;
X = [a,b,c,d,e] -> ;
X = [b,c,d,e,a] -> ;
…
…
?-
28. Выполнить циклический сдвиг списка вправо.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c,d,e],X).
X = [e,a,b,c,d] -> ;
X = [d,e,a,b,c] -> ;
X = [c,d,e,a,b] -> ;
X = [b,c,d,e,a] -> ;
X = [a,b,c,d,e] -> ;
X = [e,a,b,c,d] -> ;
…
…
?-
29. Найти порядковый номер максимального элемента числового списка.
Аргументы: исходный список;
порядковый номер.
?- pred([3,5,8,1,4],X).
X = 3
yes
?-
30. Найти все возможные пары элементов списка.
Аргументы: исходный список;
пара элементов (список).
?- pred([a,b,c,d,e],X).
X = [a,b] -> ;
X = [a,c] -> ;
X = [a,d] -> ;
X = [a,e] -> ;
X = [b,c] -> ;
X = [b,d] -> ;
X = [b,e] -> ;
X = [c,d] -> ;
X = [c,e] -> ;
X = [d,e] -> ;
no
?-
31. Найти все возможные перестановки элементов списка.
Аргументы: исходный список;
результирующий список.
?- pred([a,b,c],X).
X = [a,b,c] -> ;
X = [a,c,b] -> ;
X = [b,a,c] -> ;
X = [b,c,a] -> ;
X = [c,a,b] -> ;
X = [c,b,a] -> ;
no
?-
32. Строка текста на русском языке содержит «лишние» пробелы. Удалить избыточные пробелы.
Аргументы: исходная строка;
результирующая строка.
?- pred(’Мы будем рады узнать ваше мнение!’,X).
X = ’Мы будем рады узнать ваше мнение!’
yes
?-
33. Даны два числовых списка, содержащие коэффициенты двух полиномов. Соответствие между элементами списка и коэффициентами полинома можно отобразить следующим образом: a0+a1x+a2x2+a3x3+a4x4+… ®[a0,a1,a2,a3,a4,…]. Перемножить полиномы. Результирующий полином должен представлять собой список коэффициентов, составленный по тому же правилу, что и списки для исходных полиномов.
Аргументы: первый полином (список);
второй полином (список);
результирующий полином.
?- pred([3,5,8],[1,4],X).
X = [3,17,28,32]
yes
?-
34. Дан список и число N. Построить сочетания по N элементов из исходного списка.
Аргументы: исходный список;
целое число;
результирующий список.
?- pred([3,5,8,1],3,X).
X = [3,5,8]
X = [3,5,1]
X = [3,8,1]
X = [5,8,1]
no
?-
35. Преобразовать предложение на русском языке в список слов.
Аргументы: исходная строка;
список слов (строк).
?- pred(’Это будет работать, но возникнут две проблемы.’,X).
X = [Это,будет,работать,но,возникнут,две,проблемы]
yes
?-
36. Восстановить по отчеству имя.
Аргументы: исходная строка (отчество);
результирующая строка (имя).
?- pred(’Иванович’,X).
X = Иван
yes
?-
37. Подсчитать количество вхождений каждой буквы в строку текста на русском языке и собрать результаты в список.
Аргументы: исходная строка;
список пар вида «Буква : целое число».
?- pred(’Это будет работать’,X).
X = [Э:1,т:4,о:2,б:2,у:1,д:1,е:1,р:1,а:2,ь:1]
yes
?-
38. Произвести перекодировку строки текста на русском языке из кодировки DOS в кодировку Windows.
Аргументы: исходная строка (DOS);
результирующая строка (Windows).
?- pred(’Перевод получен’,X).
X = ??а?ўR¤ ЇR<гз?-
yes
?-
39. Дан числовой список, содержащий первые N членов ряда, и порядковый номер элемента ряда K. Расчитать K-ый элемент ряда при условии, что каждый член ряда равен сумме N предыдущих его членов (за исключением N первых членов).
Аргументы: список первых членов ряда;
порядковый номер члена ряда;
член ряда.
?- pred([0,1,2],4,X).
X = 3
yes
?-
40. Произвести замену всех вхождений заданной подстроки в исходную строку на новую подстроку.
Аргументы: исходная строка;
подстрока для поиска;
подстрока для замены;
результирующая строка.
?- pred(’голод, холод’, ’од’, ’одом’,X).
X = ’голодом, холодом’
yes
?-
41. Дано предложение на русском языке. Построить список слов предложения. Список не должен содержать повторов слов и знаков препинания.
Аргументы: исходная строка;
список слов.
?- pred(’Что воля, что неволя...’,X).
X = [’что’,’воля’,’неволя’]
yes
?-
42. Дан список точек плоскости. Каждая точка задается парой координат (X,Y) и, таким образом, исходный список имеет вид [(X1,Y1),(X2,Y2),(X3,Y3),…]. Преобразовать исходный список в список относительных координат вида [(X1,Y1),(DX2,DY2),(DX3,DY3),…], где первая точка задается абсолютными координатами, а все последующие – в виде пары (сдвиг по оси X, сдвиг по оси Y) относительно предыдущей точки (DXk=Xk−Xk-1,DYk=Yk−Yk-1).
Аргументы: исходный список абсолютных координат;
список относительных координат.
?- pred([(1,2),(3,5),(2,0),(0,0)],X).
X = [(1,2),(2,3),(1,-5),(-2,0)]
yes
?-