Задания к лабораторной работе по изучению языка Пролог

1. Определить (и напечатать) координаты концов интервала на оси Х, покрываемого максимальным количеством отрезков из списка o1(X1_1,Х2_1), o2(X1_2,Х2_2), ... ,oN(X1_N,Х2_N).

2. Даны два списка целых чисел A1, ..., AN и B1, ..., BN. Cлить эти списки в один, исключить все повторения чисел и упорядочить их по возрастанию.

3. Для множества точек плоскости p1(X1,Y1), p2(X2,Y2), ..., pN(Xn,Yn) найти диаметр и центр минимальной описанной окружности.

4. В списке символов S1, S2, ..., SN найти первое и последнее вхождения указанного символа и исключить все символы между ними.

5. В списке символов S1, S2, ..., SN исключить все последовательности указанного вида, например [a,b,c,d].

6. В списке символов S1, S2, ..., SN найти длину наибольшей последовательности, построенной повторением одного и того же символа. Вывести эту последовательность.

7. В списке символов S1, S2, ..., SN каждую указанную последовательность символов заменить нв другую указанную последовательность.

8. Из списка символов S1, S2, ..., SN исключить все символы между круглыми скобками. Сами скобки тоже должны быть отброшены. Однако, если внутри круглых скобок есть другая пара круглых скобок, то она и содержащиеся в ней символы должны быть сохранены. И так далее рекурсивно. Например, последовательность "ab(c(d(ef(gh)z)fg)r)dd(ik(l))" преобразуется в "ab(d(gh)fg)dd(l)".

9. В списке символов S1, S2, ..., SN подсчитать количество букв в последнем слове, если разделителем между словами является один или несколько пробелов.

10. В списке символов S1, S2, ..., SN подсчитать количество слов, если разделителем между словами является один или несколько пробелов.

11. Вдоль доски расположены лунки и в каждой лунке лежит шар белого или черного цвета. Одним ходом разрешается менять местами два соседних шара. Добиться того, чтобы в лунках сначала лежали белые, а потом черные шары.

12. В списке символов S1, S2, ..., SN найти число слов, начинающихся с заданной буквы, если разделителем между словами является один или несколько пробелов.

13. В списке символов S1, S2, ..., SN найти длину самого короткого слова, если разделителем между словами является один или несколько пробелов. Вывести это слово.

14. В списке символов S1, S2, ..., SN найти все вхождения указанного слова, если разделителем между словами является один или несколько пробелов.

15. Вдоль доски расположены лунки и в каждой лунке лежит шар белого, синего или красного цвета. Одним ходом разрешается менять местами два соседних шара. Добиться того, чтобы в лунках сначала лежали белые, затем красные, а потом синие шары.

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

17. В списке символов S1, S2, ..., SN найти среднюю длину слов, если разделителем между словами является один или несколько пробелов. Вывести все слова, имеющие эту длину.

18. В списке символов S1, S2, ..., SТ найти длину самого длинного слова, если разделителем между словами является один или несколько пробелов. Вывести это слово.

19. Преобразовать список целых чисел A1, А2, ..., AN следующим образом:

20. Каждый элемент списка целых чисел A1, A2, ..., AN помножить на квадрат наименьшего элемента и представить этот список в упорядоченном виде.

21. Из списка целых чисел A1, А2, ..., AN исключить все элементы, совпадающие со значением [(A_max + A_min + A_ср) / 3].

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

23. Список целых чисел A1, A2, ..., AN оставить без именений, если он упорядочен по возрастанию или убыванию. В противном случае:

24. Список отрезков o1(X1_1,X2_1), o2(X1_2,X2_2), ..., oN(X1_N,X2_N) упорядочить и найти отрезки с минимальной и максимальной длиной.

25. Даны два списка целых чисел A1, ..., AN и B1,...,BN найти

26. В каждой из девяти клеток квадрата 3х3 разместить одно из чисел 1, 2 или 3 так, чтобы сумма чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду и на каждой главной диагонали равнялась 6.

27. В квадрате размером 3х3 расставить числа 1, 2, 3, 4, 5, 6, 7, 8 и 9 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду и на каждой главной диагонали были равны.

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

Стол Стул   Шкаф  
Стул
Кресло

29. Решить упрощенный вариант головоломки "пятнашки" (поле размером 3х3, номер старшей фишки - 8) для указываемой начальной позиции. (Литература: Н.Нильсон. Принципы искусственного интеллекта. - М.: Радио и связь, 1985.)

30. Для N произвольно заданных костяшек домино необходимо найти все возможные цепочки из этих костяшек длиной N. Если таких цепочек нет, то выдать максимально длинную возможную цепочку.

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

32. Для двух произвольно введеных строк символов определить может ли быть одна строка получена из другой перестановкой символов (без учета пробелов).

33. Для произвольно введеной последовательности целых чисел определить (и напечатать) максимально длинную подпоследовательность чисел, расположенных в возрастающем порядке.

34. Для произвольно введеной последовательности символов определить содержатся ли в ней все символы указанного слова в той же последовательности, что и в самом слове. Например: после-довательность "development" содержит в себе символы слова "dont".

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

36. Написать программу, реализующую беспроигрышную стратегию игры "в крестики-нолики" на поле 3х3. Организовать вывод текущей позиции после каждого хода программы и человека.

37. Для списка пар целых чисел р1(Х1,Y1), p2(X2,Y2), ..., pN(XN,YN), рассматриваемых как координаты точек на плоскости, найти и вывести все прямоугольники и квадраты, все четыре вершины которых располагаются в этих точках. Определить фигуру наибольшей площади.

38. Написать программу шифрации последовательности А нулей и единиц в последовательность В также нулей и единиц, реализующую следующий алгоритм шифрации:

Написать также программу дешифрации В в А.

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

40. Написать программу отыскания кратчайшего пути коня из позиции a1 на стандартной шахматной доске в произвольную позицию.

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

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

  1. ни один ферзь не бил другого;
  2. все не занятые ферзями позиции бились по крайней мере одним ферзем.
43. На шахматной доске размером 4x4 расположены 4 коня. Верхний левый и вехний правый углы заняты двумя черными конями. Нижний левый и нижний правый углы заняты двумя белыми конями. Написать программу поиска последовательности ходов минимальной длины, обеспечивающей инверсию расположения коней.

44. Написать программу решения "японской" головоломки (кроссворда) для сетки произвольного размера. Подготовить исходные данные для тестов размером 8x8, 8x16 и 16x16. Задание уточнить у преподавателя.

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

-(*(+(1,2),3),/(4,5)) => (1+2)*3-4/5

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

-(*(+(1,2),3),/(4,5)) => 1 2 + 3 * 4 5 / -

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

(1+2)*3-4/5 => -(*(+(1,2),3),/(4,5))

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

(1+2)*3-4/5 => 1 2 + 3 * 4 5 / -

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

50. Написать программу символьного дифференцирования арифметических выражений, представленных в канонической (в виде структур) для языка Пролог форме. При этом единственная переменная (по которой производится дифференцирование) обозначается буквой x, а константы - всеми иными строчными (маленькими) буквами.

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

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

ACHS / DD = NXS
DX *  S = DOC
HOB ? SS = HXN
ACHS / DX = HOB
DD * S = SS
NXS - DOC = HXN

53. Дано алгебраическое уравнение над целыми числами, в котором знаки операций (+, -, *, /) заменены буквами (например, Z, Y, X, ...). Написать универсальную программу, отыскивающую подстановку для букв, превращающую уравнение в тождество. Пример.
Уравнение: (3 Z 5) Y 12 = 27
Подстановка: Z = *, Y = +

54. Задача А.Эйнштейна.
Основные условия.

  1. Есть 5 стоящих вдоль улицы домов разного цвета.
  2. В каждом доме живет по 1 человеку уникальной национальности.
  3. Каждый жилец пьет только один определенный напиток, курит сигареты только одной марки и держит одно животное.
  4. Никто из 5 человек не пьет одинаковый с другими напиток, не курит сигарет одинаковой марки и не держит одинаковое животное.
Дополнительные условия. Вопрос: кто держит рыбу?

Написать универсальную программу решения этой и подобных ей задач.
Примечание: А.Эйнштейн полагал, что только 2% жителей земли способны решить эту задачу.
 

55. Побеждай или проигрывай. Именно такой лозунг (в переводе с английского) записан в клетках таблицы где представлены результаты однокругового турнира четырех футбольных команд, получавших по три очка за победу и по одному очку за ничью. Каждой букве соответствует своя цифра. Попробуйте расшифровать этот ребус и выяснить результаты всех шести игр, состоявшихся на турнире. Счет, с которым они заканчивались, устанавливать не надо, достаточно будет узнать, кто у кого выиграл, кто с кем сыграл в ничью.
Команды Победы Поражения Ничьи Забито мячей Пропущено мячей Очки
A     W I N  
B   O R      
C     L O S E
D            

56. Ферзь находится на поле A7 шахматной доски. Необходимо найти последовательность из четырех ходов, обеспечивающую прохождение ферзем следующих девяти полей: A6, A7, F8, B6, B7, B8, C6, C7, C8.
57. Ферзь находится на поле D1 шахматной доски. Необходимо найти последовательность из пяти ходов, обеспечивающую прохождение ферзем максимального количества полей доски. При этом ферзь не имеет права останавливаться на любом поле более одного раза и пересекать уже пройденный маршрут последующими ходами.
58.  Ферзь находится на поле C3 шахматной доски. Необходимо найти последовательность из 15 ходов, завершающуюся в поле F6 и обеспечивающую прохождение всех полей шахматной доски . При этом ни одно поле нельзя проходить более одного раза.
59.  Ферзь находится на поле A1 шахматной доски. Необходимо найти замкнутый маршрут из 14 ходов, обеспечивающий прохождение всех полей доски. При этом любые поля допускается проходить более одного раза.
60. Восемь шахматных фигур (без пешек) одного цвета необходимо расставить на шахматной доске так, чтобы они в сумме угрожали минимальному количеству полей (не обязательно свободных). Поле, битое двумя и более фигурами, учитывается единожды. Решить задачу в двух вариантах: а) слоны строго разнопольны, б) слоны могут быть однопольными.
61. Восемь шахматных фигур (без пешек) одного цвета необходимо расставить на шахматной доске так, чтобы они в сумме угрожали максимальному количеству полей (не обязательно свободных). Поле, битое двумя и более фигурами, учитывается единожды. Решить задачу в двух вариантах: а) слоны строго разнопольны, б) слоны могут быть однопольными.
62. Даны 3 сосуда, имеющие целочисленные объемы V1, V2 и V3. При этом V1 >= V2+V3, а V2 и V3 не имеют общих делитей, отличных от 1. Сосуд V1 полностью заполнен водой. Переливая воду из сосуда в сосуд (и выливая ее из сосудов в "космос"), необходимо отмерить в одном из сосудов заданное (целочисленное) количество воды.
63. Даны 2 сосуда, имеющие целочисленные объемы V1 и V2. При этом V1 и V2 не имеют общих делитей, отличных от 1. Имеется также "безразмерный" пруд, из которого можно черпать воду сосудами, и в который можно выливать воду из сосудов. Определить последователность переливаний, необходимую для получения заданного (целочисленного) количества воды в одном из сосудов.
64. Задача о центре полного графа (полным называется граф, имеющий ребро между каждыми двумя вершинами). Вершины графа задаются их координатами (X,Y) расположения на плоскости, вес ребра между вершинами i и j определяется эвклидовой метрикой на плоскости Wij=sqrt((Xi-Xj)**2+(Yi-Yj)**2). Найти вершину, для которой расстояние до самой дальней вершины явдяется самым коротким.
65. Задача о медиане полного графа (полным называется граф, имеющий ребро между каждыми двумя вершинами). Вершины графа задаются их координатами (X,Y) расположения на плоскости, вес ребра между вершинами i и j определяется эвклидовой метрикой на плоскости, Wij=sqrt((Xi-Xj)**2+(Yi-Yj)**2). Найти вершину, для которой сумма расстояний до всех остальных вершин является наименьшей.
66. Для представленного ниже лабиринта найти путь из вершины "Start" в вершину "Finish". При этом вершины "A"..."C" имеют внутреннюю структуру, аналогичную структуре основного лабиранта.