Методические указания к занятию № 3

Работа со списками

 

Цель СРСП

 

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

 

Задание для подготовки к работе

 

Изучить лекции по теме "Списки".

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

 

1. Выполнить контрольные примеры.

2. Создать программу на языке Пролог, которая решает задачи согласно варианту.

3. Составить отчет о проделанной работе.

 

Задание и методические рекомендации

 

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

 

Контрольный пример

 

Создание списка всех натуральных чисел не превосходящих заданного.

 

create([],0).

create([X|T],X):-X>0, X1=X-1, create(T,X1).

 

Задание к работе

 

1. Реализовать набор функций для обработки списков, используя возможности языка:

- Добавление элемента к списку.

- Удаление элемента из списка.

- Конкатенация списков.

- Определение длины списка.

- Выделение подсписка.  

2. Решить дополнительные задачи согласно варианту, используя построенные функции.

3. Подобрать тестовые данные и оформить отчет.

 

Варианты заданий

 

1. Решить следующие задачи:

а) проверить является ли список палиндромом;

б) упорядочить список методом вставки;

в) добавить к каждому элементу списка 1;

г) выделить из списка подсписки положительных и отрицательных чисел.

2. Решить следующие задачи:

а) добавить элемент в i -ю позицию списка;

б) подсчитать сумму всех элементов списка;

в) инвертировать список;

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

3. Решить следующие задачи:

а) удалить из списка все повторяющиеся подсписки;

б) подсчитать количество положительных чисел в списке;

в) подсчитать сумму положительных и произведение отрицательных элементов списка;

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

4. Решить следующие задачи:

а) удвоить элемент списка, если он положительный и утроить, если он отрицательный;

б) упорядочить список по убыванию с помощью сортировки (не вставкой);

в) объединить три списка;

г) выделить подсписки, содержащие букву «а» и объединить их.

5. Решить следующие задачи:

а) добавить элемент в i -ю позицию списка;

б) подсчитать сумму целых чисел в списке;

в) выделить из списка подсписки положительных и отрицательных чисел;

г) упорядочить список по возрастанию.

6. Решить следующие задачи:

а) составить список, состоящий из натуральных чисел, лежащих на числовой оси между двумя заданными;

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

в) инвертировать список;

г) утроить список.

7. Решить следующие задачи:

а) удалить из списка заданный подсписок;

б) упорядочить список по убыванию;

в) заменить каждый элемент списка, состоящий из символов, на следующий символ алфавита;

г) удалить повторяющиеся элементы в списке.

8. Решить следующие задачи:

а) упорядочить список по возрастанию;

б) подсчитать в списке количество отрицательных, положительных и

нулевых элементов;

в) инвертировать список;

г) отнять от каждого элемента списка 1.

9. Решить следующие задачи:

а) выделить из списка буквы и числа;

б) проверить список на симметричность;

в) определить количество уровней вложенности списка;

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

10. Решить следующие задачи:

а) инвертировать список на всех уровнях вложенности;

б) найти суммы всех подряд идущих пар чисел в списке;

в) определить длину списка;

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

11. Решить следующие задачи:

а) добавить подсписок в указанную позицию;

б) инвертировать список;

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

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

12. Решить следующие задачи:

а) удаление подсписков указанной глубины;

б) выдать подсписок, компоненты которого принадлежат заданному

  интервалу;

в) выделить из списка все элементы, которые делятся на 2 и на 3;

г) проверить список на симметричность.

13. Решить следующие задачи:

 

а) инвертировать список;

б) подсчитать сумму положительных элементов списка;

в) выделить положительные, отрицательные и нулевые элементы списка;

г) объединить 3 списка.

14. Решить следующие задачи:

а) упорядочить список по возрастанию методом простой вставки;

б) определить кратность вхождения подсписка в список;

 

в) подсчитать среднее значение списка;

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

 

Содержание отчета

 

1. Исходные тексты программ на языке Пролог.

2. Наборы тестовых данных и результаты работы программ.

3. Перечень и анализ ошибок.

4. Выводы по работе.

 

Методические указания к занятию №4.

Бинарные деревья

 

Цель СРСП

 

1. Научиться описывать рекурсивные типы данных.

2. Выработать навыки представления структур в виде дерева.

 

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

 

1. Решить задачу соответствующего варианта.

2. Подобрать тестовые данные и протестировать программу на компьютере.

3. Составить отчет о проделанной работе.