Лабораторна робота №2 АМО. Лабораторна робота з Алгоритми та методи обчислень. Робота № 530959

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

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

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра ЕОМ

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

Рік:

2019

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми та методи обчислень

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 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

Лабораторна робота Алгоритми та методи обчислень

159753

28.05.2019 18:26

Коментарі

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

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

поділитись