Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи icon

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи



НазваниеЛабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи
страница2/5
Дата конвертации10.09.2012
Размер0.53 Mb.
ТипЛабораторная работа
1   2   3   4   5
1. /C++ - лабы.docЛабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи
Рис.1. Текст программы вывода двух перпендикулярных линий



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

Работа с массивами


Постановка задачи

Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1
Таблица 2.


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



Правило упорядочивания элементов матрицы

1

Упорядочить каждую строку по возрастанию элементов

2

Упорядочить строки по возрастанию последних элементов строк

3

Переместить в каждой строке все отрицательные элементы в начало строки, а неотрицательные – в конец

4

Разместить все положительные элементы в верхнюю левую область матрицы (заполняя ими матрицу по строкам слева направо), а неположительные – в нижнюю правую область

5

Разместить все максимальные элементы в верхнюю левую область матрицы (заполняя ими матицу построчно), а остальные – в нижнюю правую область

6

Упорядочить столбцы по убыванию первых элементов столбцов

7

Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по убыванию массив

8

Упорядочить каждую строку по убыванию элементов

9

Разместить все минимальные элементы в нижнюю правую область матрицы (заполняя ими матицу построчно), а остальные – в верхнюю левую область

10

Упорядочить каждый столбец по возрастанию элементов

11

Упорядочить столбцы по возрастанию последних элементов столбцов

12

Переместить в каждом столбце все отрицательные элементы в начало столбца, а неотрицательные – в конец

13

Разместить все положительные элементы в левую верхнюю область матрицы (заполняя ими матрицу по столбцам сверху вниз), а неположительные – в правую нижнюю область.

14

Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по столбцам ее элементы образовывали отсортированный по возрастанию массив

15

Упорядочить каждый столбец по убыванию элементов

16

Упорядочить столбцы по убыванию последних элементов столбцов

17

Упорядочить строки по возрастанию первых элементов строк

18

Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по возрастанию массив

19

Разместить все максимальные элементы в верхнюю правую область матрицы (заполняя ими матицу по столбцам), а остальные – в нижнюю левую область

20

Разместить все отрицательные элементы в верхнюю левую область матрицы (заполняя ими матицу по строкам), а неотрицательные – в нижнюю правую область


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

Алгоритмы сортировки и поиска


Постановка задачи

Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Варианты заданий приведены в табл. 3.

Таблица 3

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

№.

Метод сортировки (поиска)

1

Сортировка простой (линейной) вставкой

2

Бинарный поиск

3

Сортировка слиянием (метод фон Неймана)

4

Сортировка методом бинарной вставки без использования рабочего массива

5

Сортировка Шелла (слияние с обменом)

6

Быстрая сортировка (метод Хоара)

7

Комбинированный метод быстрой сортировки с методом «пузырька»

8

Внешняя двухфазная сортировка прямым слиянием

9

Челночная сортировка (сортировка с просеиванием)

10

Интерполяционный поиск

11

Сортировка методом центрированной вставки (нахождение медианы)

12

Шейкер – сортировка

13

Сортировка методом бинарной вставки с использованием рабочего массива

14

Обменная сортировка

15

Внешняя однофазная сортировка прямым слиянием

16

Внешняя сортировка естественным слиянием

17

Сортировка Шелла (слияние с обменом)

18

Внешняя сортировка сбалансированным слиянием

19

Сортировка простой (линейной) вставкой

20

Бинарный поиск


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

Алгоритмы сортировки и поиска приведены ниже. В приведенных алгоритмах массивы упорядочиваются по возрастанию. Пример программы, выполняющей сортировку массива методом «пузырька», приведен на рис.2.

Обменная сортировка.

Последовательно сравнивается элемент а0 с каждым последующим ai и, если ai< а0, то эти два элемента меняются местами; таким образом наименьший элемент оказывается на своем месте в начале массива. Затем этот метод применяется к элементу а1 и т. д.

Шейкер – сортировка

В этом методе проходы массива выполняются поочередно: слева направо, а потом справа налево. Последовательно сравниваются пары соседних элементов (а0 и а1, а1 и а2, и т.д.) и, если надо, переставляются. Запоминается индекс последнего переставляемого элемента (right). Далее массив просматривается справа налево, начиная с индекса right. В этом проходе массива также выполняются сравнения соседних элементов и их перестановка. Запоминается индекс последнего переставляемого элемента (left). Далее опять выполняется проход слева направо от индекса left до индекса right и т.д.

Сортировка Шелла.

Выбирается интервал d между сравниваемыми элементами, и выполняется сортировка массива методом «пузырька», но с шагом d. После этапа сортировки массива с выбранным интервалом, этот интервал уменьшается и опять выполняется сортировка массива методом «пузырька». Рекомендуется следующая последовательность значений d: 1, 3, 7, 15, 31, … ,т.е.

dk=(dk-1-1)/2

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

Челночная сортировка

Последовательно сравниваются пары соседних элементов а0 и а1, а1 и а2, и т.д. и если аi>ai+1, то элемент ai+1 продвигается влево насколько это возможно: он сравнивается со своим предшественником и, если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда передвигаемый влево элемент встречает меньшего предшественника, то процесс передвижения влево прекращается и возобновляется просмотр массива слева направо с той позиции, с которой выполнялся обмен при продвижении слева направо.

Быстрая сортировка (метод Хоара)

Идея метода заключается в том, что вначале переставляются элементы, которые находятся друг от друга на больших расстояниях. Выбирается элемент массива (например, центральный), который разбивает массив на два подмножества. Пусть значение этого элемента х. Элементы массива переставляются таким образом, чтобы слева от x находились элементы аi<=x, а справа aj>=x. После перестановок элемент x будет находиться на своем месте. Далее этот алгоритм разделения массива на левую и правую части применяется к левой, а затем к правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из единственного элемента. Таким образом, в этой сортировке используется рекурсия. Алгоритм разделения элементов массива начиная с элемента с индексом left до элемента с индексом right относительно «центрального» элемента x: вводятся два индекса i и j, i=left; j=right. Элементы просматриваются слева направо до тех пор, пока не обнаружится элемент ai>=x, затем массив просматривается справа налево, пока не обнаружится элемент aj<=x. После этого элементы меняются местами. Далее процесс просмотра и перестановки повторяется до тех пор, пока не станет i>j.

Комбинированный метод быстрой сортировки с методом «пузырька»

В этом методе рекурсивный алгоритм разделения массива быстрой сортировки применяется только для подпоследовательностей массива, длина которых не менее определенного размера m (m<=n). Для сортировки коротких подпоследовательностей используется метод «пузырька».

Линейная вставка

Элементы массива делятся на уже упорядоченную последовательность а0, а1, …, аi-1 и неупорядоченную аi, ai+1, …,an-1. В каждом проходе из неупорядоченной последовательности извлекается элемент аi (в первом проходе i=1) и вставляется в упорядоченную последовательность из i элементов без нарушения упорядоченности в ней. Этот алгоритм повторяется для i=2,3,…,n-1. Алгоритм вставки аi в упорядоченную последовательность из i элементов заключается в продвижении вставляемого элемента в начало последовательности, сравнивая его с аi-1, ai-2 и т.д. Продвижение заканчивается на элементе аj<=ai или при прохождении всей последовательности.

Бинарная вставка

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

Центрированная вставка

Алгоритм использует дополнительный рабочий массив. В позицию, расположенную в центре рабочего массива помещается элемент а0. Он будет медианой. Слева от медианы надо расположить все элемент, меньшие медианы, а справа – большие или равные. Из сортируемого массива последовательно выбирается элемент, сравнивается с медианой и вставляется без нарушения упорядоченности в левую или правую части массива. Если область памяти, выделенная для одной из частей, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении и значение медианы изменяется. В конце алгоритма упорядоченные элементы должны быть скопированы в исходный массив.

Метод фон Неймана

Упорядочить пары соседних элементов массива а (а0 и а1, а2 и а3 и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а.

Внешняя двухфазная сортировка прямым слиянием

Внешняя сортировка используется для сортировки файлов, размеры которых не позволяют записать их во временные массивы в оперативной памяти. Для сортировки используются три файла: c (исходный файл), a и b (вспомогательные файлы). Элементы исходного файла с попеременно записываются то в а, то в файл b (фаза разделения). Таким образом, в каждом файле создаются одноэлементные последовательности. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b (фаза слияния). Эти двухэлементные последовательности записываются в файл с. Далее двухэлементные последовательности попеременно записываются то в а, то в файл b (фаза разделения). Затем двухэлементные последовательности из файлов a и b сливаются в упорядоченные четверки и записываются в файл с (фаза слияния). Алгоритм разбиения файла с пополам и формирование упорядоченных последовательностей путем слияния пар последовательностей из файлов a и b повторяется до тех пор, пока в файлах a и b не образуется по одной упорядоченной последовательности, которые окончательно сливаются в отсортированный файл с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя однофазная сортировка прямым слиянием

Для сортировки используются четыре файла: c (исходный файл), a, b и d (вспомогательные файлы). При первом проходе элементы исходного файла с попеременно записываются то в а, то в файл b. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b. Эти двухэлементные последовательности попеременно записываются в файлы с и d. Затем сливаются пары двухэлементных последовательностей из файлов c и d в упорядоченные четверки, которые записываются попеременно в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя сортировка естественным слиянием

Сортировка, при которой сливаются две самые длинные из возможных упорядоченных последовательностей, называется естественным слиянием. В алгоритме используется исходный файл с и два вспомогательных файла a и b. В алгоритме при первом проходе определяются как можно более длинные упорядоченные последовательности файла с. Далее эти последовательности попеременно записываются в файлы a и b. На каждом следующем проходе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и переносятся в файл с, после чего наступает фаза разделения: последовательности попеременно записываются в файлы a. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Внешняя сортировка сбалансированным слиянием

В алгоритме используется исходный файл с и три вспомогательных файла a, b, d. В данном алгоритме при первом проходе определяются как можно более длинные упорядоченные участки файла с. Далее эти участки попеременно записываются в файлы a и b. На следующем этапе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и попеременно переносятся в файлы с и d. Затем сливаются пары последовательностей файлов с и d и попеременно переносятся в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.

В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.

Бинарный поиск

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

Интерполяционный поиск

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Если известно, что х находится между элементами al и ar, то номер очередного элемента для сравнения вычисляется по формуле

m=l+(r-l)*(x-al)/(ar-al)

Если совпадение найдено, то возвращается индекс элемента (m), иначе определяется, в какой части массива следует выполнять поиск, применяя к ней алгоритм интерполяционного поиска.


#include

#include

void sort(int a[], int n)

{

int i,j;

int c;

for(j=1;j<=n-1;j++)

for(i=0;i
if(a[i]>a[i+1])

{c=a[i];a[i]=a[i+1];a[i+1]=c;}

}

void main(void)

{

int a[10];

int n;

int i;

cout<<"n? ";

cin>>n;

cout<<"a?";

for(i=0;i
cin>>a[i];

sort(a,n); //вызов функции сортировки

cout<<"a: ";

for(i=0;i
cout<
getch();

}

Рис. 2. Сортировка массива методом «пузырька»


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

Перегрузка функций


Постановка задачи

Используя алгоритм упорядочивания матрицы, разработанный в лабораторной работе №2, разработать и протестировать две перегруженные функции, одна из которых обрабатывает целочисленную матрицу, другая - вещественную матрицу (варианты 3-5, 9, 12, 13,19, 20) или матрицу, элементы которой строки (варианты 1, 2, 6-8, 10, 11, 14-18).


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

шаблонЫ функций

Постановка задачи

Создать шаблон функции, выполняющей сортировку или поиск элементов в массиве. Протестировать шаблон для массивов с элементами различных типов: для вариантов 2, 10 и 20 – int, short и char, а для остальных вариантов - int, float и char. Варианты заданий приведены в лабораторной работе №3


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

Пример шаблона функции перестановки значения двух числовых переменных приведен на рис. 3.


template

void change (t a, t b)

{

t c;

c=a; a=b; b=c;

}

Рис. 3. Шаблон функции


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

Динамические структуры ДАННЫХ


Постановка задачи

Разработать программу, выполняющую операции со структурами данных, реализованными в виде связанных списков. Алгоритмы выполнения каждой операции оформить в виде функции. Программа должна содержать меню, позволяющее протестировать все операции с динамической структурой. Варианты заданий приведены в табл. 4 -6.

Таблица 4

Варианты структур данных

Структура данных

Операции

Варианты

Линейный список

Добавление элемента в начало, создание списка из n элементов, проверка списка на отсутствие в нем элементов, поиск позиции элемента с заданным значением, удаление элемента после элемента с заданной позицией (вар.1), удаление дубликатов (вар.11), получение значения элемента по его позиции, вывод списка

1, 11

Циклический список

Добавление элемента, создание списка из n элементов, проверка списка на отсутствие в нем элементов, удаление дубликатов (вар. 12), удаление элемента с заданным значением (вар. 2, 18), вывод списка

2, 12, 18

Стек

Добавление элемента, удаление элемента, создание стека из n элементов, проверка стека на отсутствие в нем элементов, получение значения элемента из вершины стека, очистка стека, вывод стека

3, 13

Очередь

Добавление элемента в конец, создание очереди из n элементов, проверка очереди на отсутствие в ней элементов, удаление элемента из начала, удаление всех элементов, получение значения из начала очереди, вывод очереди

4,14, 15

Очередь с приоритетами

Создание пустой очереди, добавление элемента, проверка очереди на отсутствие в ней элементов, удаление элемента с наибольшим приоритетом, получение элемента с наибольшим приоритетом, сцепление двух очередей, вывод очереди

5, 16

Дек

Добавление элемента справа, удаление элемента слева (вар. 17), удаление элемента справа (вар.6), создание списка из n элементов, проверка списка на отсутствие в нем элементов, копирование дека (вар. 6), копирование дека в обратном порядке (вар. 17), получение значения правого элемента, вывод дека

6, 17

Дек с ограниченным выходом

Добавление элемента справа, добавление элемента слева, создание дека из n элементов, проверка дека на отсутствие в нем элементов, удаление элемента справа, удаление всех элементов, получение значения правого элемента, вывод дека

7

Дек с ограниченным входом

Добавление элемента слева, создание дека из n элементов, проверка дека на отсутствие в нем элементов, удаление элемента справа, удаление элемента слева, получение значения левого элемента, удаление всех элементов, сравнение двух деков, вывод дека

8

Множество

Создание пустого множества, проверка вхождения элемента в множество, включение элемента в множество, объединение двух множеств, пересечение двух множеств, разность двух множеств, вывод множества

9, 19

Словарь

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

10, 20


Таблица 5

Варианты способа реализации структуры

Способ реализации

Варианты

Связанный однонаправленный линейный список

1, 3, 4, 5, 19, 20

Связанный однонаправленный линейный список с указателями на данные

13, 15

Связанный упорядоченный однонаправленный линейный список

9, 10

Связанный однонаправленный циклический список

2

Связанный двунаправленный циклический список

12

Связанный двунаправленный линейный список

6, 7, 8, 11, 14, 16, 17

Связанный однонаправленный циклический список с указателями на данные

18


Таблица 6

Варианты элементов данных

Элемент данных

Варианты

Шифр студента – 9 символов, ФИО – 25 символов, средний балл – вещественное число

1, 2, 3, 4, 6,

Авторы – 20 символов, название - 20 символов, год издания – целое число

7, 8, 11, 12, 14, 17

Приоритет – целое число, наименование задания – 20символов, количество страниц - целое

5, 16

Название дисциплины – строка переменной длины

13, 15, 18

Код дисциплины – целое число, название дисциплины – 20 символов

9, 19

Телефон (ключ) – целое число, ФИО абонента (значение)– 25 символов

10, 20

1   2   3   4   5




Похожие:

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconДокументы
1. /OOP/Лабораторная работа ь00-Введение.doc
2. /OOP/Лабораторная...

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconЛабораторная работа: создание мини-презентации «Памятники Кремля»
Лабораторная работа проводится в компьютерном классе, с подключением к сети Internet
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconДокументы
1. /Базовые задачи на обработку массива.doc
2. /ЗадачиНаЛиниВетвление.doc
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconДокументы
1. /Lab1/Лабораторная работа 1.doc
2. /Lab2/Лабораторная...

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconИ я забуду Покажи мне и я запомню, Дай мне действовать самому и я научусь. Китайская мудрость Тема: Лабораторная работа
Тема: «Лабораторная работа «Измерение работы и мощности тока в электрической лампочке»
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconДокументы
1. /C++Builder/15.doc
2. /C++Builder/Алфавитный...

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconЦелью дипломного проекта является разработка базы данных для сотрудников Красногорского управления внутренних дел
Данная пояснительная записка состоит из четырёх основных разделов, которые в общей сложности занимает 83 печатных листов. В состав...
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconДокументы
1. /Nash/lab1/Лабораторная работа ь1.doc
2. /Nash/lab10/Лабораторная...

Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconЛабораторная работа Цель работы: научиться создавать при помощи excel базу данных, содержащую различные сведения о работе фирмы. Задачи: Создание списков
Списком называют таблицу, обязательным атрибутом которой является строка заголовков. Требования к оформлению списка следующие
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconЛабораторная работа №2 «Система безопасности Windows xp»
Лабораторная работа №2 «Система безопасности Windows xp» Цель работы: Изучить систему безопасности Windows xp
Лабораторная работа №1 Разработка консольного приложения в С++ Builder Постановка задачи iconЛабораторная работа Тема: «Приспособление растений к совместному существованию» Задачи: Рассмотреть примеры приспособлений растений к условиям освещённости
Растения, а в частности, деревья полностью приспособились к условиям окружающей среды и поэтому им совсем стало легко выживать в...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов