Лабораторна робота №2 АМО

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано

Інформація про роботу

Рік:
2018
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ЗВІТ З лабораторної роботи №2 з дисципліни “Алгоритми та методі обчислень” на тему: “Асимптотичні характеристики складності алгоритму” Варіант 8 1.Завдання: 1. Відповідно до варіанту завдання для заданих функцій часової складності L(n) визначити асимптотичні характеристики O(n). 2. Розташувати отримані функції в порядку зростання асимптотичних характеристик O(n). 3. Скласти програму (C), яка ілюструє клас (поліноміальний чи експоненціальний) складності алгоритму, асимптотична складність якого була визначена в п2, як найбільша. При складанні програми передбачити можливість зміни значень K та n. 2.Варіант завдання: Номер варіанту – 8 / 3.Результат виконання програми: Рис.1. Результат виконання програми 4.Висновок: На даній лабораторній роботі я дізнався про асимптотичну складність алгоритму, визначив клас складності, та склав відповідну програму. 5.Код програми: // don't forget to use compilation key for Linux: -lm #define _CRT_SECURE_NO_WARNINGS // for using fopen in VS #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); BMP* BMP_ReadFile(const char* filename); void BMP_WriteFile(BMP* bmp, const char* filename); UINT BMP_GetWidth(BMP* bmp); UINT BMP_GetHeight(BMP* bmp); USHORT BMP_GetDepth(BMP* bmp); void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b); void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b); void BMP_GetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR* val); void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val); void BMP_GetPaletteColor(BMP* bmp, UCHAR index, UCHAR* r, UCHAR* g, UCHAR* b); void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b); BMP_STATUS BMP_GetError(); const char* BMP_GetErrorDescription(); #define OUTPUT_SIZE 512 #define OUTPUT_WIDTH OUTPUT_SIZE #define OUTPUT_HEIGHT OUTPUT_SIZE #define NEIGHBOURHOOD 0 #define OUTPUT_SCALE 8 #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 neighbourhood, UINT xSize, UINT ySize, UCHAR pt) { UINT neighbourhood2 = 2 * neighbourhood; UINT xO, yO; for (UINT x = 0; x < xSize; ++x) { for (UINT y = 0; !y || (!(x % 20) && y < 10); ++y) { for (xO = 0; xO <= neighbourhood2; ++xO) { for (yO = 0; yO <= neighbourhood2; ++yO) { if (x + xO >= neighbourhood && x + xO - neighbourhood < xSize && y + yO >= neighbourhood && y + yO - neighbourhood < ySize) { BMP_SetPixelIndex(bmpPtr, x + xO - neighbourhood, ySize - (y + yO - neighbourhood), pt); } } } } } for (UINT y = 0; y < ySize; ++y) { for (UINT x = 0; !x || (!(y % 20) && x < 10); ++x) { for (xO = 0; xO <= neighbourhood2; ++xO) { for (yO = 0; yO <= neighbourhood2; ++yO) { if (x + xO >= neighbourhood && x + xO - neighbourhood < xSize && y + yO >= neighbourhood && y + yO - neighbourhood < ySize) { BMP_SetPixelIndex(bmpPtr, x + xO - neighbourhood, ySize - (y + yO - neighbourhood), pt); } } } } } } double functionForTabulate1(double arg) { return sqrt(arg); } void tabulate(double(*functionPtr)(double arg), BMP * bmpPtr, UINT neighbourhood, UINT xSize, UINT ySize, UCHAR pt, UINT scale) { UINT neighbourhood2 = 2 * neighbourhood; UINT xO, yO; UINT fraction; UINT scaledXSize = (UINT)((double)xSize / (double)scale); for (UINT x_ = 0; x_ < scaledXSize; x_++) { for (fraction = 0; fraction < scale; ++fraction) { double fX = (double)fraction / (double)scale + (double)x_; UINT x = (UINT)(fX * (double)scale); UINT y = (UINT)(functionPtr(fX) * (double)scale); for (xO = 0; xO <= neighbourhood2; xO++) { for (yO = 0; yO <= neighbourhood2; yO++) { if (x + xO >= neighbourhood && x + xO - neighbourhood < xSize && y + yO >= neighbourhood && y + yO - neighbourhood < ySize) { BMP_SetPixelIndex(bmpPtr, x + xO - neighbourhood, ySize - (y + yO - neighbourhood), pt); } } } } } } 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(functionForTabulate1, output, NEIGHBOURHOOD, OUTPUT_WIDTH, OUTPUT_HEIGHT, 2, OUTPUT_SIZE / OUTPUT_SCALE); BMP_WriteFile(output, "out.bmp"); BMP_CHECK_ERROR(stderr, -5); BMP_Free(output); printf("Result writed to \"out.bmp\".\r\n"); printf("An example file may be located:\r\n"); printf(" \"..\\Visual Studio 2013\\Projects\\amolab2\\amolab2\\out.bmp\"\r\n"); printf("After closing the program, open it manually.\r\n\r\n"); printf("Press any key to continue . . ."); getchar(); return 0; } /*********************************** BMP Implementation **********************************/ typedef struct _BMP_Header { USHORT Magic; UINT FileSize; USHORT Reserved1; USHORT Reserved2; UINT DataOffset; UINT HeaderSize; UINT Width; UINT Height; USHORT Planes; USHORT BitsPerPixel; UINT CompressionType; UINT ImageDataSize; UINT HPixelsPerMeter; UINT VPixelsPerMeter; UINT ColorsUsed; UINT ColorsRequired; } BMP_Header; /* Private data structure */ struct _BMP { BMP_Header Header; UCHAR* Palette; UCHAR* Data; }; static BMP_STATUS BMP_LAST_ERROR_CODE = (BMP_STATUS)0; 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" }; #define BMP_PALETTE_SIZE ( 256 * 4 ) int ReadHeader(BMP* bmp, FILE* f); int WriteHeader(BMP* bmp, FILE* f); int ReadUINT(UINT* x, FILE* f); int ReadUSHORT(USHORT *x, 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; } bmp = (BMP*)calloc(1, sizeof(BMP)); if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; return NULL; } 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; bytes_per_row = width * bytes_per_pixel; bytes_per_row += (bytes_per_row % 4 ? 4 - bytes_per_row % 4 : 0); 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); if (bmp->Header.BitsPerPixel == 8) { bmp->Palette = (UCHAR*)calloc(BMP_PALETTE_SIZE, sizeof(UCHAR)); if (bmp->Palette == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; free(bmp); return NULL; } } else { bmp->Palette = NULL; } 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; } BMP* BMP_ReadFile(const char* filename) { BMP* bmp; FILE* f; if (filename == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return NULL; } bmp = (BMP*)calloc(1, sizeof(BMP)); if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; return NULL; } f = fopen(filename, "rb"); if (f == NULL) { BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND; free(bmp); return NULL; } if (ReadHeader(bmp, f) != BMP_OK || bmp->Header.Magic != 0x4D42) { BMP_LAST_ERROR_CODE = BMP_FILE_INVALID; fclose(f); free(bmp); return NULL; } if ((bmp->Header.BitsPerPixel != 32 && bmp->Header.BitsPerPixel != 24 && bmp->Header.BitsPerPixel != 8) || bmp->Header.CompressionType != 0 || bmp->Header.HeaderSize != 40) { BMP_LAST_ERROR_CODE = BMP_FILE_NOT_SUPPORTED; fclose(f); free(bmp); return NULL; } if (bmp->Header.BitsPerPixel == 8) { bmp->Palette = (UCHAR*)malloc(BMP_PALETTE_SIZE * sizeof(UCHAR)); if (bmp->Palette == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; fclose(f); free(bmp); return NULL; } if (fread(bmp->Palette, sizeof(UCHAR), BMP_PALETTE_SIZE, f) != BMP_PALETTE_SIZE) { BMP_LAST_ERROR_CODE = BMP_FILE_INVALID; fclose(f); free(bmp->Palette); free(bmp); return NULL; } } else { bmp->Palette = NULL; } bmp->Data = (UCHAR*)malloc(bmp->Header.ImageDataSize); if (bmp->Data == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; fclose(f); free(bmp->Palette); free(bmp); return NULL; } if (fread(bmp->Data, sizeof(UCHAR), bmp->Header.ImageDataSize, f) != bmp->Header.ImageDataSize) { BMP_LAST_ERROR_CODE = BMP_FILE_INVALID; fclose(f); free(bmp->Data); free(bmp->Palette); free(bmp); return NULL; } fclose(f); BMP_LAST_ERROR_CODE = BMP_OK; return bmp; } void BMP_WriteFile(BMP* bmp, const char* filename) { FILE* f; if (filename == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return; } f = fopen(filename, "wb"); if (f == NULL) { BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND; return; } if (WriteHeader(bmp, f) != BMP_OK) { BMP_LAST_ERROR_CODE = BMP_IO_ERROR; fclose(f); return; } 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; } } 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); } UINT BMP_GetWidth(BMP* bmp) { if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return -1; } BMP_LAST_ERROR_CODE = BMP_OK; return (bmp->Header.Width); } UINT BMP_GetHeight(BMP* bmp) { if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return -1; } BMP_LAST_ERROR_CODE = BMP_OK; return (bmp->Header.Height); } USHORT BMP_GetDepth(BMP* bmp) { if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return -1; } BMP_LAST_ERROR_CODE = BMP_OK; return (bmp->Header.BitsPerPixel); } void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b) { UCHAR* pixel; UINT bytes_per_row; UCHAR bytes_per_pixel; if (bmp == NULL || x < 0 || x >= bmp->Header.Width || y < 0 || y >= bmp->Header.Height) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; } else { BMP_LAST_ERROR_CODE = BMP_OK; bytes_per_pixel = bmp->Header.BitsPerPixel >> 3; bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height; pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel); if (bmp->Header.BitsPerPixel == 8) { pixel = bmp->Palette + *pixel * 4; } if (r) *r = *(pixel + 2); if (g) *g = *(pixel + 1); if (b) *b = *(pixel + 0); } } void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b) { UCHAR* pixel; UINT bytes_per_row; UCHAR bytes_per_pixel; 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 != 24 && bmp->Header.BitsPerPixel != 32) { BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH; } else { BMP_LAST_ERROR_CODE = BMP_OK; bytes_per_pixel = bmp->Header.BitsPerPixel >> 3; bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height; pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel); *(pixel + 2) = r; *(pixel + 1) = g; *(pixel + 0) = b; } } void BMP_GetPixelIndex(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; bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height; pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x); if (val) *val = *pixel; } } 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; bytes_per_row = bmp->Header.ImageDataSize / bmp->Header.Height; pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x); *pixel = val; } } void BMP_GetPaletteColor(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) { BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH; } else { if (r) *r = *(bmp->Palette + index * 4 + 2); if (g) *g = *(bmp->Palette + index * 4 + 1); if (b) *b = *(bmp->Palette + index * 4 + 0); BMP_LAST_ERROR_CODE = BMP_OK; } } 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) { BMP_LAST_ERROR_CODE = BMP_TYPE_MISMATCH; } else { *(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 ReadHeader(BMP* bmp, FILE* f) { if (bmp == NULL || f == NULL) { return BMP_INVALID_ARGUMENT; } if (!ReadUSHORT(&(bmp->Header.Magic), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.FileSize), f)) return BMP_IO_ERROR; if (!ReadUSHORT(&(bmp->Header.Reserved1), f)) return BMP_IO_ERROR; if (!ReadUSHORT(&(bmp->Header.Reserved2), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.DataOffset), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.HeaderSize), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.Width), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.Height), f)) return BMP_IO_ERROR; if (!ReadUSHORT(&(bmp->Header.Planes), f)) return BMP_IO_ERROR; if (!ReadUSHORT(&(bmp->Header.BitsPerPixel), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.CompressionType), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.ImageDataSize), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.HPixelsPerMeter), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.VPixelsPerMeter), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.ColorsUsed), f)) return BMP_IO_ERROR; if (!ReadUINT(&(bmp->Header.ColorsRequired), f)) return BMP_IO_ERROR; return BMP_OK; } 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
Антиботан аватар за замовчуванням

28.05.2019 18:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!