Отчеты по лабораторным работам
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Отчет по лабораторной работе дисциплины: Автоматическое проектирование вычислительных систем

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

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

Условно считать, что

- максимальное число функций не должно превышать 16;

- максимальное число переменных не должно превышать 16.

Исходными данными является текстовый файл со следующей структурой:

- число функций

- число переменных

- количество единичных наборов

- количество х-наборов

- список единичных наборов (хn…x1)

- список х-наборов (хn…x1)

- список принадлежности набора функции (f1…fm).

Выходными данными тоже является текстовый файл следующей структуры:

- вектор а

- вектор b

- бит присутствия набора a-b в функции.

Бит вектора а и b имеют следующую структуру:

Если 1 => a=1, b=0;

Если 0 => a=0, b=1;

Если - => a-1, b=1.

Алгоритм решения задачи

I Ищем и проставляем максимально количество соседей для каждой единичной точки.

II 1 Выбираем точку, еще не использованную, с минимальным количеством соседей.

   2 Заносим в дерево решения.

   3 Ищем ближайшего соседа, получаем новый интервал и записываем его в дерево решения.

III 1 Вновь полученный интервал расширяем по одной из переменных и проверяем есть ли в новом точки принадлежащие новому интервалу, если нет то п. п II, иначе III.1.

IV 1 В дереве решения ищем интервалы, принадлежащие разным функциям и объединяем их.

Метод решение задачи.

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

struct CInfo - характеристика для каждого элемента

{

WORD data;//интервал

WORD function;// флаги функций, в которых присутствует интервал

WORD used; //использование интервала

vector <byte> neighbo; // количество соседей

};

struct CTable – для данных, считанных из файла

{

byte number_func;//кол. функций

byte number_var;//кол. переменных

byte number_one;//кол. единичных наборов

byte number_x;//кол. Х-наборов

vector <CInfo> one;//список един. наборов

vector <CInfo> x;//список х-наборов

};

struct CTreeSolution - структура дерева решения

{

WORD a;

WORD b;

WORD num_function;

bool ok;

};

Для реализации данной задачи был разработан класс CRoughMethod.

class CRoughMethod

{

public:

CRoughMethod();

~CRoughMethod(void);

WORD num_string;

private:

CTable table;

vector <CData> listString;

vector <CTreeSolution> treeSolution;

bool CheckInretval(WORD a, WORD b, byte var); - проверяет, можно ли склеить две точки

с координатами a и b по переменной var

public:

byte CheckSourceFile(ifstream *file); - проверяет файл file на правильность исходных

данных

void FindNeighbo(void); - поиск соседей для всех единичных наборов

void SearchSolution(void); - функция выполнения всего алгоритма поиска

private:

WORD count_interval;

int FindPoint(byte numFucnction); - поиск координаты точки, принадлежащей функции

numFunction, по критерию: не использованная,

максимум соседей.

bool FindPointOfInterval(WORD mask_a, WORD mask_b, WORD count_interval, WORD num_function); - проверка на присутствие интервала, удовлетворяющего маске mask_a,

mask_b, количество точек count_interval, в функции num_function.

public:

void FindMainIntervalForFunction(void); - поиск и объединение интервалов,

принадлежащих нескольким функциям.

void SaveTreeSolution(void); - сохранение результатов в файл.

};

Тестовые примеры

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

Результат

a

b

Func

2

4

7

2

0101

1111

1000

1001

1011

1010

0110

1001

1110

11

11

11

11

01

01

01

10

10

6 (0110)

5 (0101)

15 (1111)

9 (1001)

15 (1111)

11 (1011)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9 (1001)

10 (1010)

1 (0001)

7 (0111)

4 (0100)

7 (0111)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

3

1

1

2

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тестовые примеры

Текст программы

#include "StdAfx. h"

#include ".\roughmethod. h"

#include <math. h>

CRoughMethod::CRoughMethod()

{

}

CRoughMethod::~CRoughMethod(void)

{

}

byte CRoughMethod::CheckSourceFile(ifstream *file)//проверяем исходный файл

{

if(!file->is_open()) return ERROR_FILE_NOTOPEN;

char s[255];

char *p;

CData el;

num_string=0;

while(!file->eof())

{

file->getline(s,255);

num_string+=1;

p = strtok(s," \t\r\n");

if(p)

{

el. str. Format(p);

el. num_string = num_string;

listString. push_back(el);

p = strtok(NULL, " \t\r\n");

if(p) return ERROR_DATA;

}

}

if(listString. size()>4)

{

if((atoi(listString[0].str)>0)&&(atoi(listString[0].str)<16))

table. number_func = atoi(listString[0].str);

else return ERROR_FUNCTION;

if((atoi(listString[1].str)>0)&&(atoi(listString[1].str)<16))

table. number_var = atoi(listString[1].str);

else return ERROR_VAR;

int a = (int)pow(2,table. number_var)*table. number_func;

if((atoi(listString[2].str)>=0)&&(atoi(listString[2].str)<a))

table. number_one = atoi(listString[2].str);

else return ERROR_ONE;

a = a - atoi(listString[2].str);

if(atoi(listString[3].str)<=a)

table. number_x = atoi(listString[3].str);

else return ERROR_X;

}else return ERROR_STRUCT;

if(2*(table. number_one+table. number_x)+4==listString. size())

{

// единичные наборы

for(byte i=4; i<table. number_one+4; i++)

{

CInfo item;

item. data=0;

if(listString[i].str. GetLength()==table. number_var)

{

for(byte j=0; j<table. number_var; j++)

{

if(listString[i].str. GetAt(j)=='0') item. data = item. data <<1;

else if(listString[i].str. GetAt(j)=='1')

{

item. data = item. data << 1;

item. data |= 1;

}else

{

num_string = listString[i].num_string;

return ERROR_DATA;

}

}

table. one. push_back(item);

}

else if(listString[i].str. GetLength()>table. number_var)

{

num_string = listString[i].num_string;

return ERROR_STRING_BIG;

}

else

{

num_string = listString[i].num_string;

return ERROR_STRING_LITLE;

}

}

// x - наборы

for(byte i=table. number_one+4; i<listString. size()-(table. number_one+table. number_x); i++)

{

CInfo item;

item. data=0;

if(listString[i].str. GetLength()==table. number_var)

{

for(byte j=0; j<table. number_var; j++)

{

if(listString[i].str. GetAt(j)=='0') item. data = item. data <<1;

else if(listString[i].str. GetAt(j)=='1')

{

item. data = item. data << 1;

item. data |= 1;

}else

{

num_string = listString[i].num_string;

return ERROR_DATA;

}

}

table. x.push_back(item);

}

else if(listString[i].str. GetLength()>table. number_var)

{

num_string = listString[i].num_string;

return ERROR_STRING_LITLE;

}

else

{

num_string = listString[i].num_string;

return ERROR_STRING_BIG;

}

}

// признак присутствия точки в функции

WORD item=0;

WORD shift=1;

bool ok=true, er=true;

for(byte i=table. number_one+4+table. number_x; i<listString. size(); i++)

{

WORD count=table. number_func;

if(ok)

{

table. one[item].function=0;

table. one[item].used=0;

}

else

{

table. x[item].function=0;

table. x[item].used=0;

}

if(listString[i].str. GetLength()==count)

{

for(byte j=0; j<count; j++)

{

if(listString[i].str. GetAt(j)=='1')

{

shift=1;

shift = shift << j;

}

if(ok)

{

int aa = table. one[item].function;

if(listString[i].str. GetAt(j)=='1') table. one[item].function |= shift;

aa = table. one[item].function;

table. one[item].neighbo. push_back(0);

}

else

{

if(listString[i].str. GetAt(j)=='1') table. x[item].function |= shift;

table. x[item].neighbo. push_back(0);

}

er=false;

}

item+=1;

if((item==table. number_one)&&(ok))

{

ok=false;

item=0;

}

if(er)

{

num_string = listString[i].num_string;

return ERROR_DATA;

}

}else if(listString[i].str. GetLength()>count)

{

num_string = listString[i].num_string;

return ERROR_STRING_BIG;

}else

{

num_string = listString[i].num_string;

return ERROR_STRING_LITLE;

}

}

}

else if(2*(table. number_one+table. number_x)+4 > (byte)listString. size()) return ERROR_LITTLE;

else return ERROR_MANY;

return 0;

}

void CRoughMethod::FindNeighbo(void)

{

for(int ii=0; ii<table. number_func; ii++)

for(DWORD i=0; i<table. number_one; i++)

{

///////

WORD shift=1;

shift = shift << ii;

//////

if(!(table. one[i].function & shift)) continue;

int data = table. one[i].data;

for(DWORD j=0; j<table. number_one; j++)

if((i==j)&&(table. one[j].function & shift))

{

WORD shift_=1;

for(WORD jj=0; jj<table. number_func; jj++)

{

WORD a = table. one[i].function;

if(shift==shift_)

{

shift_<<=1;

continue;

}

else if(a & shift_)

{

table. one[i].neighbo[ii]+=1;

shift_<<=1;

}

}

//continue;

}

else if((table. one[j].function & shift)&&(CheckInretval(table. one[i].data, table. one[j].data, table. number_var)))

{

table. one[i].neighbo[ii]+=1;

}

}

}

bool CRoughMethod::CheckInretval(WORD a, WORD b, byte var)

{

byte res;

_asm

{

mov ax, a

mov bx, b

xor ax, bx

xor ecx, ecx

mov cl, var

mov bx, 1

mov dx, ax

lab1:

xor ax, bx

jz lab2

shl bx, 1

mov ax, dx

loop lab1

xor bl, bl

jmp lab3

lab2:

mov bl, 1

lab3:

mov res, bl

}

if(res) return true;

return false;

}

void CRoughMethod::SearchSolution(void)

{

CTreeSolution element;

CKoord *ptrKord;

int ii=1;

//ii <<= i;

count_interval=1;

ptrKord = FindPoint();

ii = ptrKord->func;

while(ptrKord->item!=-1)

{

if(count_interval==1)

{

element. a=0;

element. b=0;

element. ok=false;

element. num_function=0;

element. num_function = element. num_function | ii;

WORD data = table. one[ptrKord->item].data;

WORD shift=1;

for(WORD item=0; item<table. number_var; item++)

{

if(data & shift)

{

element. a |= shift;

element. b &= (~shift);

}else

{

element. b |= shift;

element. a &= (~shift);

}

shift <<= 1;

}

treeSolution. push_back(element);

element. a=0;

element. b=0;

element. ok=false;

count_interval<<=1;

}

else//поиск интервала, где более двух точек

{

element. a=treeSolution[treeSolution. size()-1].a;

element. b=treeSolution[treeSolution. size()-1].b;

element. num_function=treeSolution[treeSolution. size()-1].num_function;

WORD mask_a = element. a;

WORD mask_b = element. b;

WORD shift=1;

WORD a = mask_a, b=mask_b, a1, b1;

for(WORD item=0; item<table. number_var; item++)

{

a1 = a & shift;

b1 = b & shift;

if(a1 && b1)

{

mask_a &= (~shift);

mask_b &= (~shift);

}

shift<<=1;

}

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

shift=1;

for(WORD item=0; item<table. number_var; item++)

{

a = mask_a;

b = mask_b;

a &= (~shift);

b &= (~shift);

if(FindPointOfInterval(a, b,count_interval, ii))

{

element. a |= shift;

element. b |= shift;

treeSolution. push_back(element);

count_interval<<=1;

break;

}else shift<<=1;

// покидаем функцию, если нельзя больше расширить интервал

if(item==table. number_var-1)

{

count_interval=1;

treeSolution[treeSolution. size()-1].ok=true;

ptrKord = FindPoint();

ii = ptrKord->func;

break;

}

}

}

}

// }

}

CKoord* CRoughMethod::FindPoint()

{

CKoord *kord = new CKoord;

kord->item=0;

kord->func=0;

byte i=0;

WORD item=0;

byte shift=1;

WORD _i=0;

bool ok=true;

for(i=0; i<table. number_func; i++)

{

shift=1;

shift<<=i;

while(item<table. one. size())

{

byte a = table. one[item].function & shift;

WORD b = table. one[item].used & shift;

if((a)&&(!b))

{

//min = item;

kord->func = shift;

kord->item = item;

_i=i;

ok = false;

break;

}

item+=1;

}

if(!ok) break;

item=0;

}

if(ok)

{

kord->func = 0;

kord->item = -1;

return kord;

}

//////////////

item+=1;

for(;i<table. number_func; i++)

{

shift=1;

shift<<=i;

for(item; item<table. one. size(); item++)

{

int a = table. one[item].function;

int c = table. one[item].neighbo[i];

int b = table. one[item].used;

int d = table. one[kord->item].neighbo[_i];

if((a & shift)&&(!(b & shift))&&(c<d))

{

kord->func = shift;

kord->item = item;

_i=i;

}

}

item=0;

}

table. one[kord->item].used |= kord->func;

return kord;

}

bool CRoughMethod::FindPointOfInterval(WORD mask_a, WORD mask_b, WORD count_interval, WORD num_function)

{

WORD count=0;

vector <WORD> mas_used1,mas_usedx;

WORD inv_point, point;

WORD func;

for(WORD i=0; i<table. number_one; i++)//ищем точки среди единичных наборов

{

inv_point = ~(table. one[i].data);

point = table. one[i].data;

func = table. one[i].function;

WORD a = point & mask_a;

WORD b = inv_point & mask_b;

if((a == mask_a)&&(b == mask_b)&&(func & num_function))

{

count+=1;

mas_used1.push_back(i);

if(count==count_interval)

{

for(WORD i=0; i<mas_used1.size(); i++) table. one[mas_used1[i]].used |= num_function;

return true;

}

}

}

//////////////////////////////////////

for(WORD i=0; i<table. number_x; i++)//ищем точки среди х наборов

{

inv_point = ~(table. x[i].data);

point = table. x[i].data;

func = table. x[i].function;

WORD a = point & mask_a;

WORD b = inv_point & mask_b;

if((a == mask_a)&&(b == mask_b)&&(func & num_function))

{

count+=1;

mas_usedx. push_back(i);

if(count==count_interval)

{

for(WORD i=0; i<mas_usedx. size(); i++) table. x[mas_usedx[i]].used |= num_function;

for(WORD i=0; i<mas_used1.size(); i++) table. one[mas_used1[i]].used |= num_function;

return true;

}

}

}

return false;

}

void CRoughMethod::FindMainIntervalForFunction(void)

{

for(int i=0; i<treeSolution. size(); i++)

{

for(int j=i+1; j<treeSolution. size(); j++)

{

if((treeSolution[j].ok==true)&&(treeSolution[i].ok==true)&&(treeSolution[i].a==treeSolution[j].a)&&(treeSolution[i].b==treeSolution[j].b))

{

treeSolution[i].num_function |= treeSolution[j].num_function;

treeSolution[j].ok=false;

}

}

}

}

void CRoughMethod::SaveTreeSolution(void)

{

ofstream fout("res. txt");

for(WORD i=0; i<treeSolution. size(); i++)

if(treeSolution[i].ok==true)

{

fout<<(int)treeSolution[i].a<<"\t"<<(int)treeSolution[i].b<<"\t"<<(int)treeSolution[i].num_function<<endl;

}

fout. close();

}

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство

Агрономия

Преподавателям

Юридические темы

Google