Кафедра ЕОМ
Звіт
з лабораторної роботи № 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
...
