Алгоритм покриття за методом "мінімальній стовпець - максимальний рядок". Підпрограми основного алгоритму. Розробка програми сортування методом простих включень (бульбашковим методом). Словесний опис алгоритму, його контрольний приклад та ефективність.
Мій варіант алгоритму покриття визначається як залишок від ділення мого індивідуального числа Y на 4: А = (Y mod 4) 1 = (303 mod 4) 1 = 4, отже, розроблюваний алгоритм є за методом «мінімальний стовпець - максимальний рядок». IMG_0b46bb68-4fff-4548-bc1e-018999e70311 називається рішенням задачі про покриття, або просто покриттям, якщо виконується умова Безнадлишковим називається покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Покриття, близьке до найкоротшим, дає алгоритм перетворення таблиці покриттів - «мінімальний стовпець - максимальна рядок»: 1) Вихідна таблиця вважається поточної перетворюваної таблицею покриттів, безліч рядків покриттів - порожньо. Цей рядок включається до покриття, поточна таблиця скорочується викреслюванням всіх стовпців, в яких обрана рядок має одиницю, якщо в таблиці є не викреслені стовпчики, то виконується п.У цій роботі розробляються алгоритми сортування сортування за методом простого обміну (бульбашкове сортування) та покриття за методом «мінімальній стовпець - максимальний рядок». Розглянуто ефективність роботи алгоритмів, способи її підвищення. Розроблений алгоритм сортування методом простих включень (бульбашковий метод) виконує сортування елементів масиву.void Min_column (int**A, int N, int M, int* Sum, int**B, int c); {int *Sum = new int[N]; // в массиве Sum будем хранить колво единиц в каждом столбце матрицы for (int j = 0; j <N; j ) delete[] Sum; } void Min_column (int**A, int N, int M, int* Sum, int**B, int c) {int MCS = 0; // Переменная для хранения колва единиц в минимальном столбце int MCN = 0; // Переменная для хранения номера минимального столбца for (int j = 0; j <N - 1; j ) // организовано для того, чтобы мин. столбцом стал первый обнаруженный мин. столбец
Вывод
У цій роботі розробляються алгоритми сортування сортування за методом простого обміну (бульбашкове сортування) та покриття за методом «мінімальній стовпець - максимальний рядок». Алгоритми виконані з достатньою для розуміння деталізацією виконуваних операцій. Розглянуто приклади використання розроблених алгоритмів.
Розглянуто ефективність роботи алгоритмів, способи її підвищення.
Розроблений алгоритм сортування методом простих включень (бульбашковий метод) виконує сортування елементів масиву. Недоліком його є те, що іноді масив може вийти відсортованим раніше останньої ітерації циклу сортування. Для вирішення цієї проблеми, наприклад, можна перевіряти, чи були проведені переміщення елементів на кожному кроці сортування, і, якщо вони не були зроблені, слід, що масив відсортований. У цьому випадку сортування припиняється.
Розроблений алгоритм знаходження найкоротшого покриття за методом «мінімальний стовпець - максимальний рядок». Цей алгоритм є найбільш ефективним тому, що швидко знаходить найбільш значущі для знаходження найменшого покриття підмножини. На мою думку, алгоритм не потребує вдосконалення.
Список литературы
1. Вирт Н. Алгоритмы и структуры данных. - С.-П.: Невский диалект, 2001. - 350 с.
2. Новиков Ф.А. Дискретная математика для программистов. - С.-П.: Питер, 2003. - 292 с.
