Кафедра ЕОМ
Звіт
з лабораторної роботи № 4
з дисципліни: “Алгоритми та методи обчислень” Варіант № 7
Мета роботи: виконати зменшення часової складності методом «гілок і границь».
Вхідні дані
Лістинг програми:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define SIZE 4
#define ELEMENTS_COUNT 5
#define PERMITTED_POSITIONS_COUNT ELEMENTS_COUNT
#define PERMITTED_POSITION_FLAG 0x00000001
#define DEFINED_POSITION_FLAG 0x00000002
#define ELEMENT_INDEX_TO_ELEMENT_ID(INDEX) ((INDEX) + 1)
#define POSITION_INDEX_TO_POSITION_ID(INDEX) ((INDEX) + 1)
#define POSITIONS_DEFINITIONS { \
{{ PERMITTED_POSITION_FLAG }, { 0 }, { 0 }, { 0 }}, \
{{ 0 }, { PERMITTED_POSITION_FLAG }, { 0 }, { 0 }}, \
{{ 0 }, { 0 }, { PERMITTED_POSITION_FLAG }, { PERMITTED_POSITION_FLAG
}}, \
{{ 0 }, { PERMITTED_POSITION_FLAG }, { 0 }, { 0 }} \}
#define R_DEFINITIONS { \
{0, 5, 3, 0, 1}, \
{5, 0, 3, 0, 2}, \
{3, 3, 0, 1, 2}, \
{0, 0, 1, 0, 5}, \
{1, 2, 2, 5, 0} \} typedef struct PositionStruct{ unsigned int positionIndex; unsigned int positionIIndex; unsigned int positionJIndex; unsigned int elementIndex;
} Position;
typedef struct TablePositionStruct{
unsigned int flags; unsigned int positionIndex; unsigned int elementIndex;
} TablePosition;
int compareForNormalSorting(const void * a, const void * b){ long long int difference = (long long int)*(unsigned int*)a - (long long int)*(unsigned int*)b; difference < INT_MIN ? difference = INT_MIN : 0;
difference > INT_MAX ? difference = INT_MAX : 0; return (int)difference;
}
int compareForReverseSorting(const void * a, const void * b){ long long int difference = (long long int)*(unsigned int*)a - (long long int)*(unsigned int*)b; difference < INT_MIN ? difference = INT_MIN : 0;
difference > INT_MAX ? difference = INT_MAX : 0; return (int) - difference;
}
int comparePositionsForNormalSorting(const void * a, const void * b){ long long int difference = (long long int)((Position*)a)->positionIndex - (long long int)((Position*)b)-
>positionIndex; difference < INT_MIN ? difference = INT_MIN : 0; difference > INT_MAX ? difference = INT_MAX : 0; return (int)difference;
}
void printTablePositions(const char const * space, TablePosition(*tablePositions)[SIZE]){
TablePosition currentTablePosition;
for (unsigned int iIndex = 0; iIndex < SIZE; iIndex++){
printf("%s|", space);
for (unsigned int jIndex = 0; jIndex < SIZE; jIndex++){ currentTablePosition = tablePositions[iIndex][jIndex];
if (!(currentTablePosition.flags ^ (DEFINED_POSITION_FLAG |
PERMITTED_POSITION_FLAG))){
printf("| %4d |",
ELEMENT_INDEX_TO_ELEMENT_ID(currentTablePosition.elementIndex));
}
else if (currentTablePosition.flags & PERMITTED_POSITION_FLAG){
printf("| |");
} else{ printf("|XXXXXX|");
}
}
printf("|\n");
}
}
void markFreePositions(TablePosition(*tablePositions)[SIZE], unsigned int firstJ){
unsigned int positionIndex = 0;
for (unsigned int iIndex = 0; iIndex < SIZE; ++iIndex){ for (unsigned int jIndex = 0; jIndex < SIZE; ++jIndex){
TablePosition * currentTablePositionPointer = firstJ ? &tablePositions[jIndex][iIndex] :
&tablePositions[iIndex][jIndex]; if (currentTablePositionPointer->flags & PERMITTED_POSITION_FLAG){ currentTablePositionPointer->positionIndex = positionIndex++; }
}
}
}
unsigned int getPositionsByFlags(Position * usedPositions, TablePosition(*tablePositions)[SIZE], unsigned int flagsFilter, unsigned int flags){ unsigned int usedPositionsIndex = 0; TablePosition currentTablePosition;
for (unsigned int iIndex = 0; iIndex < SIZE; ++iIndex){ for (unsigned int j...
