Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Кафедра ЕОМ
Звіт
з лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень” Варіант № 7
Львів 2018
7:
/
Відповідно до варіанту завдання для заданих функцій часової складності L(n) визначити асимптотичні характеристики O(n).
L(log2(log2n2) + n2) --> O(n2)
L(n2n-1) --> O( 2n)
L((n+1)3/n + n3) --> O(n3)
L(3√n + 3n) --> O( 3n)
Розташувати отримані функції в порядку зростання асимптотичних характеристик
O(n).
1. 3n 2. n2 3. n3 4. 2n
Скласти програму (C), яка ілюструє клас (поліноміальний чи експоненціальний)
складності алгоритму, асимптотична складність якого була визначена в п2, як найбільша. При складанні програми передбачити можливість зміни значень K та n.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #ifndef UINT
#define UINT unsigned long int #endif
#ifndef USHORT
#define USHORT unsigned short #endif
#ifndef UCHAR
#define UCHAR unsigned char #endif
#define QDBMP_VERSION_MAJOR 1
#define QDBMP_VERSION_MINOR 0
#define QDBMP_VERSION_PATCH 1
typedef enum{
BMP_OK = 0, BMP_ERROR, BMP_OUT_OF_MEMORY, BMP_IO_ERROR, BMP_FILE_NOT_FOUND,
BMP_FILE_NOT_SUPPORTED, BMP_FILE_INVALID, BMP_INVALID_ARGUMENT, BMP_TYPE_MISMATCH,
BMP_ERROR_NUM
} BMP_STATUS;
typedef struct _BMP BMP;
BMP* BMP_Create(UINT width, UINT height, USHORT depth);
void BMP_Free(BMP* bmp);
void BMP_WriteFile(BMP* bmp, const char* filename);
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val);
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b);
BMP_STATUS BMP_GetError();
const char* BMP_GetErrorDescription(); #define PALETTE_SIZE 256
#define OUTPUT_WIDTH 512
#define OUTPUT_HEIGHT 512
#define RECTANGLE_WIDTH ( OUTPUT_WIDTH / 16 ) #define RECTANGLE_HEIGHT ( OUTPUT_HEIGHT / 16 )
#define BMP_CHECK_ERROR( output_file, return_value ) \ if (BMP_GetError() != BMP_OK)
\
{
\
fprintf((output_file), "BMP error: %s\n", BMP_GetErrorDescription()); \ return(return_value);
\
}
void mark(BMP * bmpPtr, UINT o, UINT xSize, UINT ySize, UCHAR pt){ UINT o2 = 2 * o;
UINT xO, yO;
UINT fraction;
for (UINT x = 0; x < xSize; ++x){
for (UINT y = 0; !y || (!(x % 20) && y < 10); ++y){ for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y +
yO - o < ySize){
- o), pt);
}
}
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO
}
}
}
for (UINT y = 0; y < ySize; ++y){
for (UINT x = 0; !x || (!(y % 20) && x < 10); ++x){ for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y +
yO - o < ySize){
- o), pt);
}
}
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO
}
}
}
}
double functionForTabulate(double arg){ return arg * arg / 500.;
}
void tabulate(double(*functionPtr)(double arg), BMP * bmpPtr, UINT o, UINT xSize, UINT ySize, UCHAR pt){
UINT o2 = 2 * o;
UINT xO, yO;
UINT fraction;
for (UINT x = 0; x < xSize; ++x){
for (fraction = 0; fraction < 32; ++fraction){
double fX = (double)fraction / (double)32 + (double)x; UINT y = (UINT)functionPtr(fX);
for (xO = 0; xO <= o2; ++xO){
for (yO = 0; yO <= o2; ++yO){
if (x + xO >= o && x + xO - o < xSize && y + yO >= o && y +
yO - o < ySize){
- o), pt);
}
}
}
BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO
}
}
}
int main(int argc, char* argv[]){ BMP* output;
UCHAR r = 0xff, g = 0xff, b = 0xff;
output = BMP_Create(OUTPUT_WIDTH, OUTPUT_HEIGHT, 8); BMP_CHECK_ERROR(stderr, -3);
BMP_SetPaletteColor(output, 3, 0, 0, 255);
BMP_SetPaletteColor(output, 2, 0, 255, 0);
BMP_SetPaletteColor(output, 1, 255, 0, 0);
BMP_SetPaletteColor(output, 0, 0, 0, 0);
mark(output, 0, 512, 512, 1);
tabulate(functionForTabulate, output, 0, 512, 512, 2); BMP_WriteFile(output, "out.bmp"); BMP_CHECK_ERROR(stderr, -5);
BMP_Free(output);
printf("Result writed to \"out.bmp\".\r\n"); return 0;
}
/* Bitmap header */
typedef struct _BMP_Header{
USHORT
UINT
Magic;
FileSize;
/* Magic identifier: "BM" */
/* Size of the BMP file in bytes */
USHORT
Reserved1;
/* Reserved */
USHORT
Reserved2;
/* Reserved */
UINT
DataOffset;
/* Offset of image data relative to the file's start */
UINT
HeaderSize;
/* Size of the header in bytes */
UINT
Width;
/* Bitmap's width */
UINT
Height;
/* Bitmap's height */
USHORT
Planes;
/* Number of color planes in the bitmap */
USHORT
BitsPerPixel;
/* Number of bits per pixel */
UINT
CompressionType;
/* Compression type */
UINT
UINT UINT
ImageDataSize;
HPixelsPerMeter; VPixelsPerMeter;
/* Size of uncompressed image's data */
/* Horizontal resolution (pixels per meter) */
/* Vertical resolution (pixels per meter) */
UINT
ColorsUsed;
/
UINT
ColorsRequired;
/* Number of color indexes that are required for
displaying the bitmap */
} BMP_Header;
/* Private data structure */ struct _BMP{
BMP_Header Header; UCHAR* Palette;
UCHAR* Data;
};
/* Holds the last error code */
static BMP_STATUS BMP_LAST_ERROR_CODE = 0;
/* Error description strings */
static const char* BMP_ERROR_STRING[] ={ "",
"General error",
"Could not allocate enough memory to complete the operation", "File input/output error",
"File not found",
"File is not a supported BMP variant (must be uncompressed 8, 24 or 32 BPP)", "File is not a valid BMP image",
"An argument is invalid or out of range",
"The requested action is not compatible with the BMP's type"
};
/* Size of the palette data for 8 BPP bitmaps */ #define BMP_PALETTE_SIZE ( 256 * 4 )
int WriteHeader(BMP* bmp, FILE* f);
int WriteUINT(UINT x, FILE* f);
int WriteUSHORT(USHORT x, FILE* f);
BMP* BMP_Create(UINT width, UINT height, USHORT depth){ BMP* bmp;
int bytes_per_pixel = depth >> 3; UINT bytes_per_row;
if (height <= 0 || width <= 0){
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return NULL;
}
if (depth != 8 && depth != 24 && depth != 32){ BMP_LAST_ERROR_CODE = BMP_FILE_NOT_SUPPORTED;
return NULL;
}
/* Allocate the bitmap data structure */ bmp = calloc(1, sizeof(BMP));
if (bmp == NULL){
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
return NULL;
}
/* Set header' default values */ bmp->Header.Magic = 0x4D42; bmp->Header.Reserved1 = 0;
bmp->Header.Reserved2 = 0;
bmp->Header.HeaderSize = 40;
bmp->Header.Planes = 1;
bmp->Header.CompressionType = 0;
bmp->Header.HPixelsPerMeter = 0;
bmp->Header.VPixelsPerMeter = 0;
bmp->Header.ColorsUsed = 0;
bmp->Header.ColorsRequired = 0;
/* Calculate the number of bytes used to store a single image row. This is always rounded up to the next multiple of 4. */
bytes_per_row = width * bytes_per_pixel;
bytes_per_row += (bytes_per_row % 4 ? 4 - bytes_per_row % 4 : 0);
/* Set header's image specific values */ bmp->Header.Width = width;
bmp->Header.Height = height; bmp->Header.BitsPerPixel = depth;
bmp->Header.ImageDataSize = bytes_per_row * height;
bmp->Header.FileSize = bmp->Header.ImageDataSize + 54 + (depth == 8 ?
BMP_PALETTE_SIZE : 0);
bmp->Header.DataOffset = 54 + (depth == 8 ? BMP_PALETTE_SIZE : 0);
/* Allocate palette */
if (bmp->Header.BitsPerPixel == 8){
bmp->Palette = (UCHAR*)calloc(BMP_PALETTE_SIZE, sizeof(UCHAR)); if (bmp->Palette == NULL)
{
}
}
else
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
free(bmp); return NULL;
bmp->Palette = NULL;
/* Allocate pixels */
bmp->Data = (UCHAR*)calloc(bmp->Header.ImageDataSize, sizeof(UCHAR)); if (bmp->Data == NULL){
BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY;
free(bmp->Palette); free(bmp);
return NULL;
}
BMP_LAST_ERROR_CODE = BMP_OK;
return bmp;
}
void BMP_Free(BMP* bmp){ if (bmp == NULL)
return;
if (bmp->Palette != NULL) free(bmp->Palette);
if (bmp->Data != NULL)
free(bmp->Data); free(bmp);
BMP_LAST_ERROR_CODE = BMP_OK;
}
void BMP_WriteFile(BMP* bmp, const char* filename){ FILE* f;
if (filename == NULL){
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
return;
}
/* Open file */
f = fopen(filename, "wb"); if (f == NULL){
BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND;
return;
}
/* Write header */
if (WriteHeader(bmp, f) != BMP_OK){ BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f); return;
}
/* Write palette */ if (bmp->Palette){
if (fwrite(bmp->Palette, sizeof(UCHAR), BMP_PALETTE_SIZE, f) != BMP_PALETTE_SIZE)
{
BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f); return;
}
}
/* Write data */
if (fwrite(bmp->Data, sizeof(UCHAR), bmp->Header.ImageDataSize, f) != bmp-
>Header.ImageDataSize){
BMP_LAST_ERROR_CODE = BMP_IO_ERROR;
fclose(f); return;
}
BMP_LAST_ERROR_CODE = BMP_OK;
fclose(f);
}
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val){ UCHAR* pixel;
UINT bytes_per_row;
if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height) BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
else if (bmp->Header.BitsPerPixel != 8) BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
else{
}
}
BMP_LAST_ERROR_CODE = BMP_OK;
/* Row's size is rounded up to the next multiple of 4 bytes */ bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height;
/* Calculate the location of the relevant pixel */
pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x);
*pixel = val;
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b){ if (bmp == NULL)
BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT;
else if (bmp->Header.BitsPerPixel != 8)
else{
}
}
BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH;
*(bmp->Palette + index * 4 + 2) = r;
*(bmp->Palette + index * 4 + 1) = g;
*(bmp->Palette + index * 4 + 0) = b; BMP_LAST_ERROR_CODE = BMP_OK;
BMP_STATUS BMP_GetError(){
return BMP_LAST_ERROR_CODE;
}
const char* BMP_GetErrorDescription(){
if (BMP_LAST_ERROR_CODE > 0 && BMP_LAST_ERROR_CODE < BMP_ERROR_NUM)
return BMP_ERROR_STRING[BMP_LAST_ERROR_CODE];
else
}
return NULL;
int WriteHeader(BMP* bmp, FILE* f){ if (bmp == NULL || f == NULL)
return BMP_INVALID_ARGUMENT;
if (!WriteUSHORT(bmp->Header.Magic, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.FileSize, f))
return BMP_IO_ERROR;
if (!WriteUSHORT(bmp->Header.Reserved1, f))
return BMP_IO_ERROR;
if (!WriteUSHORT(bmp->Header.Reserved2, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.DataOffset, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.HeaderSize, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.Width, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.Height, f))
return BMP_IO_ERROR;
if (!WriteUSHORT(bmp->Header.Planes, f))
return BMP_IO_ERROR;
if (!WriteUSHORT(bmp->Header.BitsPerPixel, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.CompressionType, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.ImageDataSize, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.HPixelsPerMeter, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.VPixelsPerMeter, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.ColorsUsed, f))
return BMP_IO_ERROR;
if (!WriteUINT(bmp->Header.ColorsRequired, f))
return BMP_IO_ERROR;
return BMP_OK;}
int
WriteUINT(UINT x, FILE* f){
UCHAR little[4]; /* BMPs use 32 bit ints *
little[3] = (UCHAR)((x & 0xff000000) >> 24);
little[2] = (UCHAR)((x & 0x00ff0000) >> 16);
little[1] = (UCHAR)((x & 0x0000ff00) >> 8);
little[0] = (UCHAR)((x & 0x000000ff) >> 0);
return (f && fwrite(little, 4, 1, f) == 1);
}
int
WriteUSHORT(USHORT x, FILE* f){
UCHAR little[2]; /* BMPs use 16 bit shorts */
little[1] = (UCHAR)((x & 0xff00) >> 8);
little[0] = (UCHAR)((x & 0x00ff) >> 0);
return (f && fwrite(little, 2, 1, f) == 1);
}
Скріншот виконання програми:
Висновок:
Виконав лабораторну роботу;
Ознайомився з асимптотичними характеристиками складності та класами складності алгоритмів
14.10.2018 19:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора