9. Задача Джонсона. Обработки n деталей на 2 станках.

Исходные данные:

n – количество деталей

T = ||t_ij|| - матрица времён обработки i –ой детали на j – м станке

Требуемый результат

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

2. Построить график Ганта – графическое изображение последовательности выполнения работ.

Алгоритм решения задачи (точный алгоритм):

• Ищем минимальный элемент в матрице (если таких несколько, то выбираем 1-ый).

• Если минимум в 1-ом столбце, то соответствующая деталь запускается в обработку первой (от уже имеющейся в последовательности обработки – от начала), если минимум во 2-м столбце, то соответствующая деталь запускается в обработку последней (от уже имеющейся в последовательности обработки – от конца).

• Эту деталь из рассмотрения исключаем.

• Алгоритм продолжается до тех пор, пока все детали не будут рассмотрены.

Пример: n = 6.

Матрица времён обработки:

2	1
3	5
1	3
4	7
3	8
3	2

Решение

1 деталь	7	1	Удалён на 1 шаге (конец)
2 деталь	3	5	Удалён на 4 шаге (начало)
3 деталь	1	2	Удалён на 2 шаге (начало)
4 деталь	6	4	Удалён на 6 шаге (начало)
5 деталь	3	3	Удалён на 5 шаге (начало)
6 деталь	3	2	Удалён на 3 шаге (конец)

Р = (3, 2, 5, 4, 6, 1)

График Ганта

1 станок: 32225554444446661111111

2 станок: 33 22222555 444466 1

Время обработки = 24

9. Модификация задачи Джонсона.

   • Информация вводится из файла: в 1-ой строке – количество станков, в последующих строках – времена обработки соответственно на 1-м т 2- м станках (количество строк зависит от того, как осуществляется чтение из файла).

   • Предусмотреть динамическое выделение память для двумерного массива.

10. Программа сортировки строк текста в алфавитном порядке. Количество строк не известно. Определяется в программе по мере ввода. Признак конца ввода – пустая строка. Для доступа к отдельным строкам используется массив указателей. Каждый элемент массива указателей указывает на начало (на 1-ый символ) соответствующей строки. Строки при сортировке не меняются местами, а меняются значения в массиве указателей.

Необходимо реализовать 2 функции:

1. sort (любой метод сортировки) вызывается из функции main;

2. strcmp_my (собственная функция реализует сравнение строк) вызывается из функции sort.

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

Предусмотреть проверку, выделена память или нет.

Результат выполнения программы:

• Печать исходного текста

• Печать отсортированного текста

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

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

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

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

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

Сортировка вставками:

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

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

9. Определяемые пользователями типы данных. Используя структуры, создать простейшую базу данных, состоящую из одного файла. Структуру придумать самостоятельно.

В программе предусмотреть следующие функции:

• Создание новой БД.

• Чтение из файла уже существующей БД.

• Сохранение в файле.

• Ввод новых записей

• Поиск по ключу.

• Модификация.

• Просмотр.

• Удаление записи.

9. Структуры данных – очередь. Структура имеет поле fam, являющееся указателем на строку с фамилией и поле next, которое содержит указатель на следующий элемент. У последнего элемента этот указатель имеет значение NULL. По этому признаку определяется последний элемент очереди.

• Программа должна состоять из 3 файлов:

• заголовочный файл, содержащий объявление структуры и прототипы функций;

#define QUE struct queue

QUE { char *fio;

QUE *next;

};

extern void insert(QUE ** , char *); //вставка в конец очереди

extern char *take(QUE **); / извлечение 1-го элемента из начала очереди;

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

• файл, содержащий функцию main.

При добавлении нового элемента динамически выделяем память. При извлечении – освобождаем. В функции main создаётся очередь, а затем делится на 2 очереди: элементы с нечётными номерами остаются в 1-ой очереди, а с чётными переходят во 2-ую с сохранением порядка следования.

9. Структуры данных – бинарное дерево. Программа подсчета частоты встречаемых слов в тексте, читаемом из файла.

При моделировании деревьев их узлы представляют в виде структуры:

• поле для хранения информации

• поле с указателем на левое поддерево

• поле с указателем на правое поддерево

#define TREE struct tree

TREE { char * wrd;

int count;

TREE *left;

TREE *right;

};

Для очередного слова динамически выделять память.