Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Целью лабораторной работы является изучение операций на множествах и приобретение навыков программирования.
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритмов выполнения операций на множествах, и на основе данных алгоритмов разработать алгоритм для решения задачи согласно своему варианту. Разработанный алгоритм требуется реализовать на языке высокого уровня. Алгоритмы рекомендуется оформлять с помощью блок-схем.
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.1.1.1-1.1.2
Требуется разработать и реализовать на языке высокого уровня алгоритмы выполнения следующих операций на множествах: объединение, пересечение, разность, симметрическая разность.
Для хранения множеств можно использовать статические целочисленные массивы, т.е допускается, что множества состоят из натуральных чисел и имеют ограниченную константой мощность.
Элементы массива a, используемого для хранения множества A, могут содержать, как сами элементы A, так и формироваться по правилу: a[i]=1, если iA; a[i]=0, если iA.
В первом случае для хранения множества A={5,2,4} будет использоваться массив a=5,2,4. Во втором случае для хранения того же множества будет использоваться массив a=01011.
Реализацию каждой операции требуется оформить в виде процедуры, входом которой являются два массива, хранящие элементы исходных множеств, а выходом - массив, хранящий элементы множества, полученного в результате выполнения соответствующей операции.
Разработанные процедуры должны использоваться для решения индивидуальной задачи согласно варианту.
Разработайте программу, позволяющую вводить с клавиатуры множества A,B,C и вычисляющую элементы множеств F1 и F2. Элементы множеств F1 и F2 выведите на экран. Выполните тестирование программы на различных входных данных. Обоснуйте полученные результаты.
Разработаем программу, позволяющую вводить с клавиатуры множества A,B,C и вычисляющую элементы множества F1=((AC)\B)(A∆C). Элементы множеств F1 выведем на экран. Для множества F2 требуется выполнить аналогичные действия. Поэтому в данном примере они не рассматриваются.
Для хранения множеств A, B, С будем использовать массивы a,b,c размера mm=10. Также будем считать, что в качестве элементов множеств можно использовать только целые числа от 0 до mm. Массив a формироваться по правилу: a[i]=1, если iA; a[i]=0, если iA. Аналогичным образом формируются массивы B,C.
При таком способе хранения множеств все операции имеют простую реализацию, которая сводится к выполнению логических операций над элементами соответствующих массивов. Если bool mn1[] - массив, хранящий первое множество (первый операнд), а bool mn2[] - массив, хранящий второе множество (второй операнд), то массив bool mn_rez[], хранящий множество, полученное в результате выполнения операции над множествами mn1 и mn2 формируется следующим образом:
Все операции реализуем в виде соответствующих функций. Эти функции будем использовать в основной функции для получения требуемого множества F1=((AC)\B)(A∆C). Для этого будем использовать рабочие массивы, т.е. массивы для хранения промежуточных результатов. В данном примере последовательность вычислений может быть следующей: r1=AC; r2=r1\B; r3=A∆C; r1=r2r3=F1.
Ввод элементов множеств будем осуществлять в консольном режиме. Полностью текст программы приведен ниже.
Для подбора тестовых примеров и наглядного представления результатов рекомендуется нарисовать диаграммы, иллюстрирующие процесс вычисления требуемых множеств. Для рассматриваемого примера данные диаграммы представлены на рис. Л.1.
#include <stdio.h>
#include <stdlib.h>
#define mm 10 // Максимальное число элементов в множествах
typedef int bool;
// Используемые множества целых чисел от 0 до mm
bool a[mm],b[mm],c[mm], r1[mm],r2[mm],r3[mm];
// Функция print_set(char st[], bool mn[])
// Назначение: Печать элементов множества mn,
// состоящего из целых чисел от 0 до mm-1
// Вход: char st[] - строка сообщения;
// bool mn[] - множество.
// Выход: нет
// Возвращает: нет.
void print_set(char st[], bool mn[]) {
int i;
printf("%s{",st);
for (i=0;i<mm;i++)
if (mn[i]) printf("%d ",i);
printf("}\n");
}
// Функция create_keybrd_set(char st[], bool mn[])
// Назначение: Ввод элементов множества mn с клавиатуры,
// состоящего из целых чисел от 0 до mm-1
// Вход: char st[] - строка сообщения;
// Выход: bool mn[] - множество.
// Возвращает: нет.
void create_keybrd_set(char st[], bool mn[]) {
int i,el;
printf("Диапазон элементов: %d..%d ; число вне диапазона - конец ввода элементов\n",0,mm-1);
printf("%s",st);
for (i=0;i<mm;i++) mn[i]=0;
scanf("%d",&el);
while (el>=0 && el<mm)
{mn[el]=1; scanf("%d",&el);}
}
// Функция unite_sets(bool mn1[],bool mn2[],bool mn_rez[])
// Назначение: Объединение двух множеств,
// состоящих из целых чисел от 0 до mm-1
// Вход: bool mn1[] - первое множество;
// bool mn2[] - второе множество;
// Выход: bool mn_rez[] - объединение множеств mn1 и mn2.
// Возвращает: нет.
void unite_sets(bool mn1[],bool mn2[],bool mn_rez[]) {
int i;
for (i=0;i<mm;i++) mn_rez[i]= mn1[i] || mn2[i] ;
}
// Функция intersect_sets(bool mn1[],bool mn2[],bool mn_rez[])
// Назначение: Пересечение двух множеств, состоящих из целых чисел от 0 до mm
// Вход: bool mn1[] - первое множество;
// bool mn2[] - второе множество.
// Выход: bool mn_rez[] - пересечение множеств mn1 и mn2.
// Возвращает: нет.
void intersect_sets(bool mn1[],bool mn2[],bool mn_rez[]) {
int i;
for (i=0;i<mm;i++) mn_rez[i]= mn1[i] && mn2[i];
}
// Функция subtract_sets(bool mn1[],bool mn2[],bool mn_rez[])
// Назначение: Разность двух множеств, состоящих из целых чисел от 0 до mm-1
// Вход: bool mn1[] - первое множество;
// bool mn2[] - второе множество.
// Выход: bool mn_rez[] - разность множеств mn1 и mn2.
// Возвращает: нет.
void subtract_sets(bool mn1[],bool mn2[],bool mn_rez[]) {
int i;
for (i=0;i<mm;i++) mn_rez[i]= mn1[i] && !mn2[i] ;
}
// Функция s_subtract_sets(bool mn1[],bool mn2[],bool mn_rez[])
// Назначение: Симметрическая разность двух множеств,
//состоящих из целых чисел от 0 до mm-1
// Вход: bool mn1[] - первое множество;
// bool mn2[] - второе множество.
// Выход: bool mn_rez[] - симметрическая разность множеств mn1 и mn2.
// Возвращает: нет.
void s_subtract_sets(bool mn1[],bool mn2[],bool mn_rez[]) {
int i;
for (i=0;i<mm;i++) mn_rez[i]= (mn1[i] && !mn2[i]) || (mn2[i] && !mn1[i]);
}
int main( void ) {
setbuf(stdout, NULL); // Отменить буферизацию стандартного
// устройство вывода, т.е. консоли.
create_keybrd_set("a=",a);
create_keybrd_set("b=",b);
create_keybrd_set("c=",c);
printf("Исходные данные:\n");
print_set(" a=",a);
print_set(" b=",b);
print_set(" c=",c);
printf("Результаты:\n");
unite_sets(a,c,r1);
print_set(" r1=",r1);
subtract_sets(r1,b,r2);
print_set(" r2=",r2);
s_subtract_sets(a,c,r3);
print_set(" r3=",r3);
intersect_sets(r2,r3,r1);
print_set(" f1=",r1);
printf("Работа программы завершена.\n");
return EXIT_SUCCESS;
}
Для разработки программ в данном лабораторном практикуме используется среда Wascana Eclipse C/C++ IDE for Windows Developers, с которой можно более детально ознакомиться на сайте (http://code.google.com/a/eclipselabs.org/p/wascana/). Рассмотренная программа и результаты ее работы в данной среде представлены на рис.Л2.
Список контрольных вопросов совпадает с вопросами для повторения темы 1.
При оценке результатов выполнения лабораторной работы оценивается:
Отметка «отлично» выставляется студенту, глубоко и прочно усвоившему программный материал, исчерпывающе, последовательно, грамотно и логически стройно его излагающему, ответившему на все контрольные вопросы, грамотно и аккуратно оформившему лабораторную работу.
Отметка «хорошо» выставляется студенту, твердо знающему программный материал, грамотно и по существу его излагающему, ответившему на все контрольные вопросы, грамотно и аккуратно оформившему лабораторную работу.
Отметка «удовлетворительно» выставляется студенту, который знает только основной материал, но не усвоил его деталей, допускает в ответе неточности, ответившему на большинство контрольных вопросов, оформившему лабораторную работу с нарушением некоторых несущественных требований.
Отметка «неудовлетворительно» выставляется студенту, который не знает значительной части программного материала, допускает существенные ошибки, не ответившему на контрольные вопросы, оформившему лабораторную работу с существенными нарушениями.
Целью лабораторной работы является изучение алгоритмов порождения комбинаторных объектов.
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритмов порождения комбинаторных объектов согласно своему варианту (при описании алгоритмов рекомендуется использовать блок-схемы). Выполнить описание программной реализации алгоритмов. Привести графики времени работы каждой программной реализации алгоритмов. При этом по оси OX следует откладывать некоторую размерность генерируемых объектов, а по оси OY - время, затрачиваемое на генерацию объектов данной размерности. Если генерируются подмножества, перестановки или разбиения, то под размерностью следует понимать число n. Если генерируются сочетания, то здесь две размерности n и k. Поэтому можно построить график при некотором фиксированном значении n. В этом случае k должно изменяться от 0 до n, возможно с некоторым шагом, отличным от 1.
Для программной реализации следует использовать язык высокого уровня. Допустимо создание консольного приложения.
Для снятия временных характеристик следует использовать стандартные функции используемого языка программирования, предназначенные для получения системного времени. Также при снятии временных характеристик следует учитывать, что время, затрачиваемое на порождение очередного комбинаторного объекта, как правило, намного меньше, чем время, затрачиваемое на вывод этого объекта на экран. Поэтому для получения адекватных временных характеристик работы алгоритмов вывод на экран лучше отключить.
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.1-2.2.
Требуется разработать и реализовать на языке высокого уровня алгоритмы порождения комбинаторных объектов, рассмотренные в разд.2.2. Достаточно реализовать два алгоритма согласно своему варианту. Также требуется экспериментально исследовать временные характеристики алгоритмов.
Как дополнительное задание рекомендуется разработать
В разд.2.2 рассмотрены следующие алгоритмы:
Номера данных алгоритмов используются для выбора индивидуального задания по таблице
Таблица Л1
Индивидуальные задания ко 2 лабораторной работе
|
№ варианта |
№ алгоритма, который требуется реализовать |
||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
|
|
|||||
|
2 |
|
|
|||||
|
3 |
|
|
|||||
|
4 |
|
|
|||||
|
5 |
|
|
|||||
|
6 |
|
|
|||||
|
7 |
|
|
|||||
|
8 |
|
|
|||||
|
9 |
|
|
|||||
|
10 |
|
|
|||||
|
11 |
|
|
|||||
|
12 |
|
|
|||||
|
13 |
|
|
|||||
|
14 |
|
|
|||||
|
15 |
|
|
|||||
|
16 |
|
|
|||||
|
17 |
|
|
|||||
|
18 |
|
|
|||||
|
19 |
|
|
|||||
|
20 |
|
|
|||||
|
21 |
|
|
Для примера реализуем алгоритм генерации сочетаний и построим график временной характеристики данного алгоритма.
Текст программы на языке Си следующий:
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
// ЛАБОРАТОРНАЯ РАБОТА №2
// Реализация и исследование временных характеристик
// алгоритмов порождения комбинаторных объектов.
#define mm 30
int c[mm]; // Сочетание из n по k
// Функция print_c(int c[],int k)
// Назначение: Печать текущего сочетания из n по k.
// Вход: int с[] - сочетание из n по k.
// Выход: нет.
// Возвращает: нет.
void print_c(int c[], int k)
{ int i;
for (i=1;i<=k;i++) printf("%d ",c[i]);
printf("\n");
}
// Функция print_all_c(int c[], int n, int k, int re)
// Назначение: Печать всех сочетаний из n по k
// Вход: int c[] - сочетание из n по k;
// int n - число элементов множества;
// int k - число элементов в сочетании;
// int re - режим печати (re=0 - не печатать, re=1 - печатать).
// Выход: нет.
// Возвращает: нет.
void print_all_c(int c[], int n, int k, int re)
{int i,j;
c[0]=-1;
for (i=1;i<=k;i++) c[i]=i;
j=1;
while (j!=0) {
if (re==1) print_c(c,k);
j=k;
while (c[j]>=n-k+j) j=j-1;
c[j]=c[j]+1;
for (i=j+1;i<=k;i++) c[i]=c[i-1]+1;
}
}
int n,k,re,i,beg,end,max;
int main(void) {
setbuf(stdout, NULL); // Отменить буферизацию стандартного
// устройство вывода, т.е. консоли.
printf("СОЧЕТАНИЯ ИЗ N ПО K\n");
printf("Введите режим работы:\n");
printf("1-Вывод сочетаний из n по k\n");
printf("2-Оценка времени генерации всех сочетаний из n\nre=");
scanf("%d",&re);
switch (re) {
case 1 :
printf("N=");
scanf("%d",&n);
printf("K=");
scanf("%d",&k);
print_all_c(c,n,k,1);
break;
case 2 :
printf("N=");
scanf("%d",&n);
max=0;
for (i=0;i<=n;i++) {
beg=GetTickCount(); //возвращает количество миллисекунд,
//прошедших с момента старта ОС.
print_all_c(c,n,i,0);
end=GetTickCount();
if (end-beg>max) max=end-beg;
printf("%d\n",end-beg);
}
if (max<500) printf("Введите большее значение n!\n");
break;
default :
printf("Введен неверный код режима работы!\n");
}
printf("Работа программы завершена.\n");
return EXIT_SUCCESS;
}
Программа может работать в двух режимах:
Первый режим используется для демонстрации работы алгоритма генерации сочетаний.
Второй режим используется для построения графика времени работы алгоритма. В этом режиме генерируются все сочетания n, при этом сами сочетания на экран не выводятся. Для каждой группы сочетаний из n по k на экран выводятся время генерации данной группы. Время измеряется в миллисекундах с помощью функции GetTickCount(), которая возвращает количество миллисекунд, прошедших с момента старта операционной системы. Если максимальное время генерации группы сочетаний из n по k меньше 500 миллисекунд, то программа выдает сообщение "Введите большее значение n". Это связано с тем, что в данном случае точность эксперимента может оказаться низкой.
Для построения графика можно использовать Excel или любую другую программу, позволяющую отображать числовой ряд в виде графика и поддерживающую режим вставки числовых данных из буфера обмена. В данном примере результаты вывода программы во втором режиме при n=30 были скопированы в буфер обмена и вставлены в Excel. Затем эти результаты были отображены на графике Excel (рис. Л.3). Объяснение вида данного графика выполните самостоятельно.
Список контрольных вопросов совпадает с вопросами для повторения темы 2.
Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».
Целью лабораторной работы является приобретение навыков разработки алгоритмов для решения задач выбора.
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритма решения задачи выбора согласно своему варианту (при описании алгоритмов рекомендуется использовать блок-схемы). При разработке алгоритма следует использовать алгоритмы порождения комбинаторных объектов.
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.1-2.2 и 3.1. Также дадим дополнительные понятия необходимые для выполнения данной лабораторной работы.
Многие задачи повседневной жизни и многие математические проблемы можно интерпретировать как задачи выбора. В общую схему задачи выбора укладываются и комбинаторные проблемы. Приведем примеры задач выбора.
Пример 1. Есть множество камней, для каждого из которых задана масса. Нужно ответить на вопрос, можно ли разделить данное множество на две равные по массе части.
Пример 2 (Задача коммивояжера). Коммивояжер (агент по сбыту), отправляясь из своего города, должен ровно по одному разу посетить n-1 заданных городов и вернуться назад, затратив при том минимальную сумму на поездку. Какой маршрут ему выбрать, если затраты на проезд между городами заданы.
Пример 3. Заданные n масс m1,m2,...,mn, требуется распределить в пространстве, в точках M1,M2,…,Mn, так, чтобы их центр тяжести был максимально близок к фиксированной точке M0.
Для задач выбора характерно:
1) конечность множества вариантов выбора (способов разделения камней, маршрутов коммивояжера и т.д.).
2) каждому варианту сопоставлена числовая характеристика (вес камней в какой либо части, стоимость проезда по маршруту и т.д.).
3) требуется выбрать вариант, числовая характеристика которого удовлетворяет некоторому условию, или ответить на вопрос о существовании такого варианта. При этом иногда нужен лишь один вариант, а иногда - все такие варианты или не сам вариант, а лишь значение его числовой характеристики.
Варианты выбора называются траекториями. Числовая характеристика варианта называется его функционалом.
Наиболее очевидный способ решения задач выбора - просмотр всех траекторий и выбор траектории с требуемым значением функционала.
Если для нахождения точного решения задачи выбора требуется организация полного перебора траекторий и перебор траекторий сводится к порождению тех или иных комбинаторных объектов, то можно использовать соответствующий алгоритм порождения таких объектов.
В задаче из примера 1 исходным множеством S (множеством из которого формируются траектории) является совокупность из n камней, а траекторией будет его разбиение на два подмножества S1 и S2, таких, что S1S2=S и S1S2=0. Если {s1,s1,…,sn} - массы камней, то - функционал, а - оптимальное значение функционала. Перебор траекторий осуществляется с помощью систематического порождения подмножеств S1, множества S. Всего траекторий 2n.
В задаче из примера 2 в качестве исходного множества выступают все возможные пары городов. Траекторией будет совокупность этих пар, образующая маршрут из начального города, удовлетворяющий всем перечисленным требованиям. Функционалом является сумма стоимостей проезда между парами городов, образующих траекторию. Оптимальным решением будет траектория с минимальным значением функционала. Для организации полного перебора траекторий в данной задаче необходимо порождение всех перестановок из n-1 элементов. Всякая такая перестановка Р=(р1,р2,…,рn-1) определяет допустимый маршрут:
"начальная вершина"р1р2…рn-1"начальная вершина".
Всего траекторий (n-1)!.
Задача из примера 3 также сводится к порождению всех перестановок n-элементного множества.
Пусть требуется разработать алгоритм решения задачи о рюкзаке. Имеется n различных предметов, известны масса каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общая масса не превышала заданной границы, а общая стоимость была максимальна.
Траекторией данной задачи является подмножество выбранных предметов (предметов положенных в рюкзак), функционалом – стоимость данных предметов. Таким образом, для решения задачи необходимо перебрать все 2n подмножеств предметов и найти подмножество, удовлетворяющее условиям задачи.
Пусть масса и стоимость предметов хранятся в массиве записей MS. Каждая запись содержит два поля: M – масса предмета и S – стоимость предмета. В переменной n хранится число предметов, в переменной MaxSM – максимальная суммарная масса выбранных предметов.
Текущее подмножество предметов будем хранить в массиве b, в котором b[i]=1, если i-й предмет принадлежит подмножеству, и b[i]=0, если i-й предмет не принадлежит подмножеству. Суммарную стоимость и массу предметов составляющих текущее подмножество будем хранить в переменных SS и SM соответственно. Для запоминания подмножества выбранных предметов будем использовать массив b1 аналогичный массиву b. Суммарную стоимость выбранных предметов будем хранить в переменной MaxSS.
Укрупненная блок-схема алгоритма решения задачи представлена на рис.Л4.
Для организации перебора траекторий вначале возьмем алгоритм порождения подмножеств в порядке двоичного счета. Реализация этого варианта алгоритма решения задачи на языке Си будет следующей:
#include <stdio.h>
#include <stdlib.h>
#define maxN 20 //Максимальное число предметов
typedef struct { float M; //Масса предмета
float S; //Стоимость предмета
} t_el_MS;
int n; //Число предметов
t_el_MS MS[maxN]; //Масса и стоимость предметов
int b[maxN+1]; //Текущее подмножество предметов
int b1[maxN]; //Подмножество выбранных предметов
float SM,SS; //Суммарная масса и стоимость предметов,
//составляющих текущее подмножество
float maxSM,maxSS; //Суммарная масса и стоимость выбранных предметов
void Init(int *n, t_el_MS MS[], float *maxSM) {
int i;
printf("Введите число предметов (не более %d)=",maxN);
scanf("%d",n);
printf("Введите массу каждого предмета:\n");
for (i=0;i<*n;i++) { printf("%d:",i+1); scanf("%f",&(MS[i].M));}
printf("Введите стоимость каждого предмета:\n");
for (i=0;i<*n;i++) { printf("%d:",i+1); scanf("%f",&(MS[i].S));}
printf("Введите максимальную суммарную массу выбранных предметов =");
scanf("%f",maxSM);
}
void Print_rez(int n, int b1[], float maxSM, float maxSS) {
int i;
if (maxSS>0) {
printf("Суммарная масса предметов со следующими номерами: ");
for (i=0;i<n;i++) { if (b1[i]==1) printf("%d ",i+1); }
printf("\n");
printf("не превышает установленного предела равного %f,", maxSM);
printf("а суммарная стоимость этих предметов максимальна и равна %f.\n", maxSS);
}
}
void Repl(int b[], int b1[]) {
int i;
for (i=0;i<n;i++) b1[i]=b[i];
}
void Func(int n, t_el_MS MS[], int b[], float *SM, float *SS) {
int i;
*SM=0; *SS=0;
for (i=0;i<n;i++) {
if (b[i]==1) { *SM=*SM+MS[i].M; *SS=*SS+MS[i].S; }
}
}
int i,j;
int main(void) {
setbuf(stdout, NULL);
printf("ЗАДАЧА О РЮКЗАКЕ\n");
Init(&n,MS,&maxSM);
maxSS=0;
for (i=0;i<=n;i++) b[i]=0;
while (b[n]!=1) {
Func(n,MS,b,&SM,&SS);
if ((SM<=maxSM)&&(SS>maxSS)) { maxSS=SS; Repl(b,b1); }
i=0;
while (b[i]==1) { b[i]=0; i++; }
b[i]=1;
}
Print_rez(n,b1,maxSM,maxSS);
printf("Работа программы завершена.\n");
return EXIT_SUCCESS;
}
Если при организации перебора траекторий за основу взять алгоритм порождения подмножеств в порядке минимального изменения, то быстродействие алгоритма может быть повышено. Это достигается за счет более быстрого подсчета функционала.
Действительно если подмножества порождаются в порядке минимального изменения, то текущее подмножество отличается от предыдущего только одним элементом. Поэтому для подсчета суммарной стоимости предметов составляющих текущее подмножество (переменная SS) не надо суммировать стоимость каждого из этих предметов. Достаточно выполнить только одно из действий:
- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем удаления некоторого предмета, то необходимо от стоимости предметов составляющих предыдущее подмножество отнять стоимость данного предмета;
- если переход от предыдущего подмножества предметов к текущему подмножеству осуществляется путем добавления некоторого предмета, то необходимо к стоимости предметов составляющих предыдущее подмножество добавить стоимость данного предмета.
Сказанное относится и к подсчету суммарной массы предметов составляющих текущее подмножество (переменная SM).
Реализация такого варианта алгоритма решения задачи на языке Си будет следующей:
#include <stdio.h>
#include <stdlib.h>
#define maxN 20 //Максимальное число предметов
#define maxStack 20 //Максимальный размер стека
typedef struct { float M; //Масса предмета
float S; //Стоимость предмета
} t_el_MS;
typedef struct { int St[maxStack]; //Элементы стека
int t; //Номер вершины стека
} t_S;
int n; //Число предметов
t_el_MS MS[maxN]; //Масса и стоимость предметов
int b[maxN+1]; //Текущее подмножество предметов
int b1[maxN]; //Подмножество выбранных предметов
float SM,SS; //Суммарная масса и стоимость предметов,
//составляющих текущее подмножество
float maxSM,maxSS; //Суммарная масса и стоимость выбранных предметов
t_S St; //Стек
void Init(int *n, t_el_MS MS[], float *maxSM) {
int i;
printf("Введите число предметов (не более %d)=",maxN);
scanf("%d",n);
printf("Введите массу каждого предмета:\n");
for (i=0;i<*n;i++) { printf("%d:",i+1); scanf("%f",&(MS[i].M));}
printf("Введите стоимость каждого предмета:\n");
for (i=0;i<*n;i++) { printf("%d:",i+1); scanf("%f",&(MS[i].S));}
printf("Введите максимальную суммарную массу выбранных предметов =");
scanf("%f",maxSM);
}
void Print_rez(int n, int b1[], float maxSM, float maxSS) {
int i;
if (maxSS>0) {
printf("Суммарная масса предметов со следующими номерами: ");
for (i=0;i<n;i++) { if (b1[i]==1) printf("%d ",i+1); }
printf("\n");
printf("не превышает установленного предела равного %f,", maxSM);
printf("а суммарная стоимость этих предметов максимальна и равна %f.\n", maxSS);
}
}
void Repl(int b[], int b1[]) {
int i;
for (i=0;i<n;i++) b1[i]=b[i];
}
void Func(int n, t_el_MS MS[], int b[], int num, float *SM, float *SS) {
if (b[num]==0) { *SM=*SM-MS[num].M; *SS=*SS-MS[num].S; }
else { *SM=*SM+MS[num].M; *SS=*SS+MS[num].S; }
}
int EmptyStack(t_S *S) { //Проверка стека на пустоту
return S->t==-1?1:0;
}
void PutStack(t_S *S, int el) { //Помещение в стек
S->t=S->t+1;
if ((S->t)>=maxStack) { printf("Стек переполнен!\n"); exit(1); }
S->St[S->t]=el;
}
void GetStack(t_S *S, int *el) { //Извлечение из стека
if (EmptyStack(S)) {printf("Стек пуст!\n"); exit(1); }
*el=S->St[S->t];
S->t=S->t-1;
}
void InitStack(t_S *S) { //Инициализация стека
S->t=-1; }
int i,j;
int main(void) {
setbuf(stdout, NULL);
printf("ЗАДАЧА О РЮКЗАКЕ\n");
Init(&n,MS,&maxSM);
maxSS=0; SM=0; SS=0;
InitStack(&St);
for (i=n-1;i>=0;i--) { b[i]=0; PutStack(&St,i); }
while (!EmptyStack(&St)) {
GetStack(&St,&i);
b[i]=!b[i];
Func(n,MS,b,i,&SM,&SS);
if ((SM<=maxSM)&&(SS>maxSS)) { maxSS=SS; Repl(b,b1); }
for (j=i-1;j>=0;j--) PutStack(&St,j);
}
Print_rez(n,b1,maxSM,maxSS);
printf("Работа программы завершена.\n");
return EXIT_SUCCESS;
}
Второй вариант реализации более предпочтителен. Он демонстрирует, как за счет использования порядка минимального изменения генерируемых объектов можно сократить время вычисления функционала.
Список контрольных вопросов содержит вопросы для повторения темы 2 и 3 а также следующие вопроосы:
Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».
Рис.Л2. Программа, вычисляющая множество F1=((AC)\B)(A∆C), и результаты ее работы в среде Wascana Eclipse C/C++ IDE for Windows Developers
Рисунок Л3. Временная характеристика алгоритма генерации сочетаний
C
C
C
C
B
B
B
B
A
A
A
A
r1=r2r3=F1
r3=A∆C
r2=r1\B
r1=AC
Рис.Л.1. Последовательность вычисления множества F1
Сформировать некоторое текущее подмножество b множества из n элементов
MaxSS0; b1
Посчитать суммарную массу (SM) и суммарную стоимость (SS) предметов принадлежащих подмножеству b
Все 2n подмножеств b проанализированы?
SS>MaxSS и
SM<MaxSM?
MaxSS0
Запомнить текущее подмножество b в b1
MS, n, MaxSM
Сформировать следующее подмножество b
MaxSS, b1
Да
Нет
Да
Нет
Рис.Л4. Укрупненная блок-схема решения задачи о рюкзаке