Laboratornye raboty i ukazaniq k ih vypolneniu

Лабораторная работа № 1.

Тема: Изучение среды С++. Составление и отладка первых программ на языке С++.

Задание: Составить, отладить и выполнить в различных отладочных режимах следующие программы на С++.

1) вывести на экран фразу “Hello, World!”;

2) вывести на экран коды всех символов таблицы ASCII, включая управляющие символы;

3) найти наибольший общий делитель двух заданных целых чисел;

4) сложить, вычесть, умножить и разделить дроби a/b, c/d (a,b,c,d вводятся с клавиатуры);

5) разложить заданное целое число на множители;

6) найти все простые делители заданного целого чила;

7) вывести два столбика (по выбору студента) таблицы умножения в шестнадцатеричной системе счисления;

8) найти индекс и значение наибольшего и наименьшего элементов массива;

9) найти количество различных элементов в массиве;

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

Лабораторная работа №2.

Тема: Часть 1. Битовые операции.

Задание:

1) запрограммировать функцию, которая выдаст на экран содержимое байта с заданным адресом;

2) написать функции для установки, сброса, изменения и опроса p- го бита в байте с заданным адресом; предложить систему тестов, написать тестирующую программу;

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

Часть 2. Битовые массивы.

Задание: разработать программу, которая выдаст все простые числа из диапазона [2; N] (N<=100000), используя для поиска простых чисел алгоритм «Решето Эратосфена».

Указание: использовать для хранения множества простых чисел битовый массив.

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

Тема: Работа с массивами. Методы сортировки массивов. Организация ввода- вывода.

Задание:

Запрограммировать три метода сортировки массива чисел.

Реализовать следующие возможности:

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

инициализацией в момент объявления;

2) интерпретацию методов сортировки в текстовом или графическом режиме.

Лабораторная работа № 4.

Тема: Работа со строками. Циклы. Использование указателей и кучи. Тестирование программ.

Задание:

Запрограммировать следующие функции для работы со строками:

- strlen(s), вычисляющую длину строки s;

- strcpy(s, p, k), возвращающую часть строки s с p- ой позиции длины не более k;

- strdel(s, p, k), удаляющую часть строки s с p- ой позиции длины не более k;

- strins(sub, s, p), вставляющую строку sub в строку s с p- ой позиции (если p больше длины строки s, strins(sub, s, p) конкатенирует s и sub);

- strops(sub, s), определяющую позицию первого вхождения строки sub в строку s (если sub не входит в s, функция strops(sub, s) возвращает ноль);

- strcmp(s1, s2), сравнивающую строки s1 и s2 и возвращающую -1, если s1<s2,

1, если s1>s2,

0, если s1=s2.

Каждая из функций должна быть реализована в четырех вариантах:

1) с помощью цикла while;

2) c помощью цикла do- while;

3) c помощью цикла for;

4) c использованием указателей.

Разработать тестирующую программу и систему тестов для каждой из функций.

Лабораторная работа № 5.

Тема: Задачи на графах. Алгоритм Дейкстры.

Задание: по заданной матрице связности, содержащей стоимости проезда из одного пункта в другой, определить матрицу наилучшей достижимости, элемент i- строки и j-столбца которой равен минимальной стоимости проезда из i- пункта в j- пункт, возможно с пересадками. Для заданных i0, j0 найти маршрут из i0- пункта в jo- пункт минимальной стоимости.

Лабораторная работа № 6.

Тема: Работа с двумерными массивами. Инициализация, развертка, копирование, преобразование двумерных массивов.

Задание:

1) Задана квадратная матрица. Найти соответствующую ей обратную матрицу.

2) По заданной матрице А (не обязательно квадратной) и вектору В решить систему линейных уравнений АХ=В.

Указание: для нахождения обратной матрицы использовать метод пополнения;

для решения системы линейных уравнений использовать метод Гаусса.

Лабораторная работа № 7.

Тема: Графика. Движение объекта в графическом режиме под управлением спец. клавиш.

Задание: Запрограммировать движение графического объекта под управлением клавиш

, , , . Предусмотреть запрет выхода объекта за пределы экрана монитора. Использовать функции getimage(), putimage() для запоминания и перерисовки объекта.

Лабораторная работа № 8.

Тема: Длинная арифметика.

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

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

Лабораторная работа № 9.

Тема: организация перебора в оптимизационных задачах выбора.

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

1) суммарный вес положенных в рюкзак объектов не превышал заданного порога R (вместимости рюкзака);

2) незаполненная часть рюкзака R- достигала минимума.

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

Запрограммировать решение задачи о загрузке рюкзака следующими способами:

1) использовать для перебора вариантов бинарную строку:

2) использовать для перебора вариантов алгоритм с возвратами (обход дерева в глубину):

3) при дополнительных исходных данных о стоимости объектов использовать метод ветвей и границ (отсекать неперспективные ветви, оценивая их с помощью удельных цен объектов)

Лабораторная работа № 10.

Тема: методы динамического программирования при решении задач оптимизации.

Задание: Используя методы динамического программирования, запрограммировать решение следующих задач.

1) Найти наибольшей длины возрастающую подпоследовательность чисел (не обязательно подряд идущих) в заданной последовательности из N чисел (N<200).

2) Известен двоичный шифр K символов (K<=10). Найти количество способов расшифровки заданной двоичной строки при использовании данного шифра.

Лабораторная работа № 11.

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

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

1) создание;

2) вывод;

3) вставка элемента;

4) удаление элемента;

5) поиск элемента по ключу (для списков и дерева).

Указание: для представления стека и очереди использовать круговой массив- буфер.