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

Список индивидуальных данных

Общая постановка задачи

Теоретическая часть

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

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

Как дополнительное задание рекомендуется разработать

· Алгоритм порождения размещений.

· Алгоритм порождения сочетаний с повторениями.

· Алгоритм порождения композиций n.

· Алгоритм порождения композиций n из k частей при рi>0.

· Алгоритм порождения композиций n из k частей при рi³0.

В разд.2.2 рассмотрены следующие алгоритмы:

1. Алгоритм порождения подмножеств по 1-й схеме

2. Алгоритм порождения подмножеств по 2-й схеме

3. Алгоритм порождение двоично-отраженного кода Грея

4. Алгоритм порождения сочетаний в лексикографическом порядке

5. Алгоритм порождения перестановок в лексикографическом порядке

6. Алгоритм порождения перестановок в порядке минимального изменения

7. Алгоритм порождения разбиений в словарном порядке

Номера данных алгоритмов используются для выбора индивидуального задания по таблице

Таблица Л1

Индивидуальные задания ко 2 лабораторной работе

№ варианта	№ алгоритма, который требуется реализовать
	Ö	Ö
	Ö		Ö
	Ö			Ö
	Ö				Ö
	Ö					Ö
	Ö						Ö
		Ö	Ö
		Ö		Ö
		Ö			Ö
		Ö				Ö
		Ö					Ö
			Ö	Ö
			Ö		Ö
			Ö			Ö
			Ö				Ö
				Ö	Ö
				Ö		Ö
				Ö			Ö
					Ö	Ö
					Ö		Ö
						Ö	Ö

Для примера реализуем алгоритм генерации сочетаний и построим график временной характеристики данного алгоритма.

Текст программы на языке Си следующий:

#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;

}

Программа может работать в двух режимах:

1. Вывод всех сочетаний из n по k на экран;

2. Оценка времени генерации всех сочетаний из n.

Первый режим используется для демонстрации работы алгоритма генерации сочетаний.

Второй режим используется для построения графика времени работы алгоритма. В этом режиме генерируются все сочетания n, при этом сами сочетания на экран не выводятся. Для каждой группы сочетаний из n по k на экран выводятся время генерации данной группы. Время измеряется в миллисекундах с помощью функции GetTickCount(), которая возвращает количество миллисекунд, прошедших с момента старта операционной системы. Если максимальное время генерации группы сочетаний из n по k меньше 500 миллисекунд, то программа выдает сообщение "Введите большее значение n". Это связано с тем, что в данном случае точность эксперимента может оказаться низкой.

Для построения графика можно использовать Excel или любую другую программу, позволяющую отображать числовой ряд в виде графика и поддерживающую режим вставки числовых данных из буфера обмена. В данном примере результаты вывода программы во втором режиме при n=30 были скопированы в буфер обмена и вставлены в Excel. Затем эти результаты были отображены на графике Excel (рис. Л.3). Объяснение вида данного графика выполните самостоятельно.

Контрольные вопросы к защите

Список контрольных вопросов совпадает с вопросами для повторения темы 2.

Дата добавления: 2014-12-27