Ім'я файлу: 12_100229_1_57214.doc
Розширення: doc
Розмір: 135кб.
Дата: 12.01.2021
скачати
Лабораторная работа № 1.
Программирование с использованием рекурсии
1.1. Индивидуальные задания.

Решить задачу двумя способами – с применением рекурсии и без нее.

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

2. В упорядоченном массиве целых чисел ai, i=1...n найти номер элемента c методом двоичного поиска, используя очевидное соотношение: если , тогда , иначе . Если элемент c отсутствует в массиве, то вывести соответствующее сообщение.

3. Найти наибольший общий делитель чисел M и N. Теорема Эйлера: если M делится на N, то НОД (N, M)=N, иначе НОД (N, M)=НОД (MmodN, N).

4. Вычислить число Фибоначчи Fb(n). Числа Фибоначчи определяются следующим образом: Fb(0)=0; Fb(1)=1; Fb(n)=Fb(n–1)+Fb(n–2).

5. Решить задачу о Ханойской башне. Имеются три стержня: s1, s2, s3. На первом из них нанизаны n дисков различных диаметров, образующих правильную пирамиду (чем выше расположен диск, тем меньше его диаметр). Требуется переместить всю башню на второй стержень, причем диски можно переносить по одному, нельзя помещать диск на диск меньшего диаметра, для промежуточного хранения можно использовать третий диск.

6. Вычислить значение полинома степени nпо схеме

.

7. Вычислить значение , используя формулу , в качестве начального приближения использовать значение x0=0.5(1+a).

8. Найти максимальный элемент в массиве a1...an, используя очевидное соотношение max (a1...an)=max (max (a1...an-1), an).

9. Найти максимальный элемент в массиве a1...an, используя соотношение (метод деления пополам) max (a1...an)=max (max (a1...an/2), max (an/2+1, an)).

10. Вычислить .

11. Вычислить произведение n  2 (n четное) сомножителей

12. Вычислить по следующему алгоритму: , если N четное; , если N нечетное.

13. Вычислить

14. Вычислить .

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

A(0, n) = n+1; A(m,0) = A(m – 1, 1); (m > 0);

A(m, n) = A(m – 1, A(m, n – 1)); ( m> 0; n > 0).
1.2. Пример выполнения индивидуального задания.

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

#include

#include

double sum(int);

double sumr(int);

int main ()

{

int n;

cout << "vvedite n "; cin >> n;

cout << "s (ne rekurs) = " << sum(n) << endl;

cout << "s (rekurs) = " << sumr(n) << endl;

return 0;

}




double sum(int n)

{

for (double s=0, int i=1; i<=n; i++) s+=(pow(i+1,2))/i;

return s;

}

double sumr(int n)

{

if (n==1) return 4;

else return sumr(n-1)+pow(n+1,2)/n;

}

Лабораторная работа № 2.
Программирование с использованием
структур и файлов
2.1. Индивидуальные задания.

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

Внимание! Разработанная программа будет использоваться в других лабораторных работах.

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

2. Для получения места в общежитии формируется список студентов, который включает Ф.И.О. студента, группу, средний балл, доход на члена семьи. Вывести информацию о студентах, у которых доход на члена семьи менее двух минимальных зарплат.

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

4. Информация о сотрудниках фирмы включает Ф.И.О., количество проработанных часов за месяц, почасовой тариф. Рабочее время свыше 144 часов считается сверхурочным и оплачивается в двойном размере. Вывести размер заработной платы каждого сотрудника фирмы за вычетом подоходного налога, который составляет 12 % от суммы заработка.

5. Информация об участниках спортивных соревнований содержит название команды, Ф.И.О. игрока, возраст. Вывести информацию о спортсменах, возраст которых не достиг 18 лет.

6. Для книг, хранящихся в библиотеке, задаются автор, название, год издания, количество страниц. Вывести список книг изданных после заданного года.

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

8. Информация о сотрудниках предприятия содержит Ф.И.О., номер отдела, должность, дату начала работы. Вывести списки сотрудников заданного отдела, проработавших на предприятии более 20 лет.

9. Ведомость абитуриентов содержит: Ф.И.О., город проживания, суммарный балл. Вывести абитуриентов, проживающих в г. Минске и имеющих балл больше 300.

10. В справочной аэропорта хранится расписание вылета самолетов на следующие сутки. Для каждого рейса указаны номер рейса, пункт назначения, время вылета. Вывести все номера рейсов и время из вылета для заданного пункта назначения.

11. У администратора железнодорожных касс хранится информация о свободных местах в поездах. Информация представлена в следующем виде: номер поезда, пункт назначения, время отправления, число свободных мест. Вывести информацию о поездах до заданного пункта назначения в которых имеются свободные места.

12. Ведомость студентов, сдававших сессию, содержит Ф.И.О. и оценки по четырем предметам. Вывести список студентов, сдавших сессию со средним баллом больше 7.

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

14. На АТС информация о разговорах содержит номер телефона абонента, время разговора и тариф. Вывести для заданного абонента сумму, которую ему следует оплатить за разговоры.

15. В магазине имеется список лиц, которым выдана карта постоянного покупателя. Каждая запись этого списка содержит номер карточки, Ф.И.О., предоставляемая скидка. Вывести информацию о покупателях, имеющих 10% скидку в магазине.

2.2. Пример выполнения индивидуального задания.

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

#include

#include

#include

#include

#include

FILE *fl;

typedef struct

{

char fio[30];

unsigned char matem;

unsigned char oaip;

} TStudent;

TStudent stud[30]; // Массив структур

char name[20]; // Имя файла

int nst=0; // Число введенных структур

int menu(); // Меню

void nnf(); // Ввести имя файла

void newf(); // Создать новый файл

void spisok(); // Ввести список

void opf(); // Открыть файл

void resc(); // Вывести результат на экран

void resf(); // Вывести результат в файл

int main()

{

while (true)

{

switch (menu())

{

case 1: nnf(); break;

case 2: newf(); break;

case 3: spisok(); break;

case 4: opf(); break;

case 5: resc(); break;

case 6: resf(); break;

case 7: return 0;

default: "Viberete pavilno!";

}

puts("Press any key to continue");

getch();

system("cls");

}

}

int menu() // Меню

{

cout << "VIBERITE:" << endl;

cout << "1. Vvod file name" << endl;

cout << "2. New file" << endl;

cout << "3. Vvesti spisok" << endl;

cout << "4. Open file" << endl;

cout << "5. Vivesti result" << endl;

cout << "6. Vivesti v fail" << endl;

cout << "7. Exit" << endl;

int i;

cin >> i;

return i;

}

void nnf() // Ввести имя файла

{

cout << "Vedite file name" << endl;

cin >> name;

}

void newf()// Создать новый файл

{

if ((fl = fopen(name,"wb"))==NULL)

{

cout << "Oshibka pri sozdanii"<

exit(1);

}

cout << "OK" << endl;

fclose(fl);

}

void spisok() // Ввести список

{

if ((fl = fopen(name,"rb+"))==NULL)

{

cout << "Oshibka pri sozdanii"<

exit(1);

}

cout << "Vedite chislo studentov " << endl;

cin >> nst;

for (int i=0; i

{

cout << "Vedite imya: ";

cin >> stud[i].fio;

cout << "Vedite otcenku po matem.: ";

cin >> stud[i].matem;

cout << "Vedite otcenku po OAiP: ";

cin >> stud[i].oaip;

fwrite( &stud[i], sizeof(TStudent), 1, fl );

}

fclose(fl);

}

void opf() // Открыть файл

{

if ((fl = fopen(name,"rb"))==NULL)

{

cout << "Oshibka pri otritii"<

exit(1);

}

nst=0; TStudent std;

while(true)

{

int nwrt = fread( &std, sizeof(TStudent), 1, fl );

if (nwrt!=1) break;

stud[nst]=std;

cout << stud[nst].fio << " " << stud[nst].matem << " " << stud[nst].oaip << endl;

nst++;

}

fclose(fl);

}

void resc() // Вывести результат на экран

{

for (int i=0; i

if (stud[i].oaip=='4')

cout << stud[i].fio << endl;

}

void resf() // Вывести результат в файл

{

char namet[30];

FILE *ft;

cout << "Vedite imya faila" << endl;

cin >> namet;

if ((ft = fopen(namet,"w"))==NULL)

{

cout << "Oshibka pri sozdanii "<

exit(1);

}

char s[80];

for (int i=0; i

if (stud[i].oaip=='4')

{

strcpy(s, stud[i].fio);

strcat(s, "\n"); // добавление разделителя строк

fputs(s, ft);

}

fclose(ft);

}




Лабораторная работа № 3.
Сортировка по ключу одномерных массив структур
3.1. Индивидуальные задания.

Использовать программу, из л. р. № 2. Отсортировать массив структур по заданному ключу указанными в индивидуальном задании методоми сортировки.

1. Ключ: цена товара. Методы сортировки: QuickSort и сортировка выбором.

2. Ключ: средний балл. Методы сортировки: QuickSort и сортировка вставкой.

3. Ключ: время отправления. Методы сортировки: QuickSort и пузырьковая сортировка.

4. Ключ: количество проработанных часов за месяц. Методы сортировки: QuickSort и сортировка выбором.

5. Ключ: возраст. Методы сортировки: QuickSort и сортировка вставкой.

6. Ключ: год издания. Методы сортировки: QuickSort и пузырьковая сортировка.

7. Ключ: код детали. Методы сортировки: QuickSort и сортировка выбором.

8. Ключ: дата начала работы. Методы сортировки: QuickSort и сортировка вставкой.

9. Ключ: суммарный балл. Методы сортировки: QuickSort и пузырьковая сортировка.

10. Ключ: время вылета. Методы сортировки: QuickSort и сортировка выбором.

11. Ключ: время отправления. Методы сортировки: QuickSort и сортировка вставкой.

12. Ключ: средний балл. Методы сортировки: QuickSort и пузырьковая сортировка.

13. Ключ: дата приемки в ремонт. Методы сортировки: QuickSort и сортировка выбором.

14. Ключ: номер телефона абонента. Методы сортировки: QuickSort и сортировка вставкой.

15. Ключ: номер карточки. Методы сортировки: QuickSort и пузырьковая сортировка.
3.2. Пример выполнения индивидуального задания

Функция для сортировки методом QuickSort. Сортировка ведется по ключу – оценка по ОАиП (см. предыдущий пример).
void s_qs(TStudent st[], int n)

{

struct

{

int l;

int r;

} stack[20];

int i,j, left, right, x, s=0;

TStudent t;
stack[s].l=0; stack[s].r=n-1;
while (s != -1)

{

left=stack[s].l; right=stack[s].r;

s--;

while (left < right)

{

i=left; j=right; x=st[(left+right)/2].oaip;

while (i <= j)

{

while (st[i].oaip < x) i++;

while (st[j].oaip > x) j--;

if (i<=j) {

t=st[i]; st[i]=st[j]; st[j]=t;

i++; j--;

}

}
if ((j-left)<(right-i))

{

if (i
right=j;

}

else {

if (left
left=i;

}

}

}

}
Подключение функции: s_qs(stud,nst);
Лабораторная работа № 4.
Поиск по ключу одномерном массиве структур
4.1. Индивидуальные задания.

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

1. Найти товар ценой равной 150 000. Методы поиска: полного перебора и двоичный.

2. Найти студента имеющего средний балл, равный 7,3. Методы поиска: полного перебора и интерполяционный.

3. Найти автобус с временем отправления: 13 часов. Методы поиска: полного перебора и двоичный.

4. Найти сотрудника отработавшего за месяц 156 часов. Методы поиска: полного перебора и интерполяционный.

5. Найти спортсмена, котором 28 лет. Методы поиска: полного перебора и двоичный.

6. Найти книгу 1966 года издания. Методы поиска: полного перебора и интерполяционный.

7. Найти деталь с кодом 09383. Методы поиска: полного перебора и двоичный.

8. Найти сотрудника, работающего с 1975 года. Методы поиска: полного перебора и интерполяционный.

9. Найти абитуриента с баллом 287. Методы поиска: полного перебора и двоичный.

10. Найти самолет, вылетающий в 14 часов. Методы поиска: полного перебора и интерполяционный.

11. Найти поезд, отправлющийся в 21 час. Методы поиска: полного перебора и двоичный.

12. Найти студента со редним баллом 8,3. Методы поиска: полного перебора и интерполяционный.

13. Найти телевизор, сданный в ремонт 25 числа. Методы поиска: полного перебора и двоичный.

14. Найти абонента с номером 21603 Методы поиска: полного перебора и интерполяционный.

15. Найти покупателя с карточкой 00458. Методы поиска: полного перебора и двоичный.

Лабораторная работа № 5.
Программирование с использованием Однонаправленных списков типа «стек»
5.1. Индивидуальные задания.

Создать стек со случайными числами из диапазона от –50 до +50. После создания стека выполнить индивидуальное задание. В конце работы все стеки должены быть удалены.

1. Преобразовать стек в два стека. Первый должен содержать только положительные числа, а второй – отрицательные.

2. Создать новый стек, содержащий только четные числа из первого стека.

3. Создать новый стек, содержащий только те числа из первого стека, которые больше среднего значения всех элементов первого стека.

4. Создать новый стек, содержащий только положительные числа из первого стека.

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

6. Найти максимальное и минимальное значение стека.

7. Опрелить, сколько элементов стека, начиная с вершины, находится до элемента с максимальным значением.

8. Опрелить, сколько элементов стека, начиная от вершины, находится до элемента с минимальным значением.

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

10. Опрелить, сколько элементов стека имеют значения меньше среднего значения от всех элементов стека.

11. Создать новый стек, содержащий только нечетные числа из первого стека..

12. Преобразовать стек в два стека. В первый поместить все четные, а во второй – нечетные числа.

13. Создать новый стек, порядок следования элементов в котором, обратный относительно первого стека.

14. Создать новый стек, в который поместить него каждый третий элемент первого стека.

15. Создать новый стек, в который поместить элементы лежащие во второй половите первого стека.

Лабораторная работа № 6.
Программирование с использованием Однонаправленных списков типа «ОЧЕРЕДЬ»
6.1. Индивидуальные задания.

Создать однонапревленную очередь со случайными числами из диапазона от –50 до +50. После создания очереди выполнить индивидуальное задание. В конце работы все очереди должены быть удалены.

1. Удалить из очереди все четные числа.

2. Удалить из очереди все отрицательные числа.

3. Поменять местами крайние элементы очереди.

4. Поменять местами минимальный и максимальный элементы очереди.

5. Удалить из очереди каждый второй элемент.

6. Удалить из очереди все элементы, расположенные до минимального элемента очереди.

7. Поменять местами наибольший среди отрицательных и наименьший среди положительных элементов очереди.

8. Поместить максимальный элемент очереди на первую позицию.

9. Поменять местами минимальный и первый элементы очереди.

10. Поменять местами первый и последний элементы очереди.

11. Удалить первый и последний элементы очереди.

12. Удалить из очереди все элементы, расположенные между минимальным и максимальным элементами очереди.

13. Удалить из очереди все элементы, стоящие после максимального элемента очереди.

14. Найти среднее значение всех элементов очереди, и удалить все элементы , которые меньше среднего значения.

15. Найти среднее значение всех элементов очереди. Поместить блажайший к среднему значению элемент очереди на первую позицию.


Лабораторная работа № 7.
Программирование с использованием двунаправленных списков
7.1. Индивидуальные задания.

Создать двунаправленный список со случайными числами из диапазона от –50 до +50. После создания списка выполнить индивидуальное задание и вывести результат. Написать программу сортировки и поиска в двунаправленном списке. Осортировать список и вывести его на экран. Найти элемент списка равный номеру варианта и вывести его порядковый номер, либо сообщение о том, что такого элемента нет. В конце работы все списки должены быть удалены.
1. Найти минимальный элемент и сделать его первым.

2. Создать два списка. Первый должен содержать только положительные числа, а второй – отрицательные.

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

4. Переместить во второй список, все элементы, находящиеся после элемента с максимальным значением..

5. Сместить по кольцу элементы списка на заданное число позиций.

6. Удалить все отрицательные элементы списка.

7. Из элементов, расположенных между максимальным и минимальным, создать кольцо. Остальные элементы должны остаться в первом списке.

8. Удалить первый и последний элементы списка.

9. Удалить по одному элементу, справа и слева от минимального. Если элементы справа или слева отсутствуют, то удалить сам минимальный элемент.

10. Удалить элеметны, заключенные между максимальным и минимальным значениями.

11. Удалить из списка элементы с повторяющимися более одного раза значениями.

12. Поменять местами элементы с максимальным и минимальным значениями, при этом элементы не должны перемещаться в памяти.

13. Преобразовать список в в кольцо. Предусмотреть возможность движения по кольцу в обе стороны с отображением места положения текущего элемента. В конце работы восстановить начальный список.

14. Поменять местами первый и максимальный элементы списка.

15. Поменять местами первый и последний элементы списка.

Лабораторная работа № 8.
Программирование с использованием древовидных структур данных
8.1. Индивидуальные задания.

Создать сбалансированное дерево поиска со случайными числами из диапазона от –50 до +50 и распечатать информацию прямым, обратным обходом и в порядке возрастания. Написать функции добавления нового значения, удаления значения, поиска значения. Выполнить индивидуальное задание и вывести результат. Вся выделенная память должна быть освобождена.
1. Поменять местами информацию, содержащую максимальный и минимальный ключи.

2. Подсчитать число листьев в дереве. (Лист – это узел, из которого нет ссылок на другие узлы дерева.)

3. Удалить из дерева ветвь с вершиной, имеющей заданный ключ.

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

5. Определить число узлов на каждом уровне дерева.

6. Удалить из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы.

7. Определить количество символов во всех строках, находящихся в узлах дерева.

8. Определить число листьев на каждом уровне дерева.

9. Определить число узлов в дереве, в которых есть указатель только на одну ветвь.

10. Определить число узлов в дереве, у которых есть две дочери.

11. Определить количество записей в дереве, начинающихся с определенной буквы (например ‘a’).

12. Найти среднее значение всех ключей дерева и найти узел, имеющий ближайший к этому значению ключ.

13. Найти запись с ключом, ближайшим к среднему значению между максимальным и минимальным значениями ключей.

14. Определить количество узлов в левой ветви дерева.

15. Определить количество узлов в правой ветви дерева.






скачати

© Усі права захищені
написати до нас