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

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

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

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

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

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 2 Асимптотичні характеристики складності алгоритму; алгоритми з поліноміальною та експоненціальною складністю. з дисципліни " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" 1. МЕТА РОБОТИ Ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів. ТЕОРЕТИЧНІ ВІДОМОСТІ 1.1. Часова складність. В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній:  бути простим для розуміння, переводу в програмний код, відлагодження.  ефективно використовувати комп'ютерні ресурси і виконуватись швидко. Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання, а не виконання програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма. На час виконання програми впливають наступні чинники:  ввід інформації в програму;  якість скомпільованого коду;  машинні інструкції, які використовуються для виконання програми;  часова складність алгоритму(ЧС). Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування). Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму. Використовується також ЧС в середньому випадку (в статистичному сенсі), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому випадку важче визначити ніж ЧС для найгіршого випадку, через те що це математично важка для розв'язання задача. Крім того, іноді важко визначити, що означає "середні" вхідні дані. Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції. Код програми // 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 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){ BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), pt); } } } } } 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){ BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), pt); } } } } } } 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){ BMP_SetPixelIndex(bmpPtr, x + xO - o, ySize - (y + yO - o), 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(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"); 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 **********************************/ /* Bitmap header */ typedef struct _BMP_Header { USHORT Magic; /* Magic identifier: "BM" */ UINT FileSize; /* 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 ImageDataSize; /* Size of uncompressed image's data */ UINT HPixelsPerMeter; /* Horizontal resolution (pixels per meter) */ UINT VPixelsPerMeter; /* Vertical resolution (pixels per meter) */ UINT ColorsUsed; /* Number of color indexes in the color table that are actually used by the bitmap */ 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 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; } /* 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) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; free(bmp); return NULL; } } else { 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; } BMP* BMP_ReadFile(const char* filename) { BMP* bmp; FILE* f; if (filename == NULL) { BMP_LAST_ERROR_CODE = BMP_INVALID_ARGUMENT; return NULL; } /* Allocate */ bmp = calloc(1, sizeof(BMP)); if (bmp == NULL) { BMP_LAST_ERROR_CODE = BMP_OUT_OF_MEMORY; return NULL; } /* Open file */ f = fopen(filename, "rb"); if (f == NULL) { BMP_LAST_ERROR_CODE = BMP_FILE_NOT_FOUND; free(bmp); return NULL; } /* Read header */ if (ReadHeader(bmp, f) != BMP_OK || bmp->Header.Magic != 0x4D42) { BMP_LAST_ERROR_CODE = BMP_FILE_INVALID; fclose(f); free(bmp); return NULL; } /* Verify that the bitmap variant is supported */ 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; } /* Allocate and read palette */ 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 /* Not an indexed image */ { bmp->Palette = NULL; } /* Allocate memory for image data */ 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; } /* Read image data */ 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; } /* 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); } 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; /* 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 (rows are flipped) */ pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel); /* In indexed color mode the pixel's value is an index within the palette */ if (bmp->Header.BitsPerPixel == 8) { pixel = bmp->Palette + *pixel * 4; } /* Note: colors are stored in BGR order */ 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; /* 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 (rows are flipped) */ pixel = bmp->Data + ((bmp->Header.Height - y - 1) * bytes_per_row + x * bytes_per_pixel); /* Note: colors are stored in BGR order */ *(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; /* 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); 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; /* 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_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
Антиботан аватар за замовчуванням

28.05.2019 18:05-

Коментарі

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

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

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

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

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

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

Admin

26.02.2023 12:38

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