Министерство образования и науки РФ
Санкт-Петербургский государственный политехнический университет
Петра Великого
Институт компьютерных наук и технологий
Кафедра «Системный анализ и управление»
УТВЕРЖДАЮ
___________________________
___________________________
___________________________
«____» _____________ _____ г.
ОТЧЕТ
по дисциплине «Теория и технология программирования»
Выполнила:
студентка г
з13502/1
_________
О.А. Рупасова
подпись,
дата
Проверил:
доц. каф. САиУ
_____________
Болотин И.В.
подпись,
дата
Санкт-Петербург 2016 г.
Содержание
Введение........................................................................
............................................................................... 3
1. Состав проекта.........................................................................
................................................................ 4
1.1 Спецификация файлов..........................................................................
................................................ 4
1.2 Реализация main.cpp........................................................................
...................................................... 4
2. Аппроксимация...................................................................
.................................................................... 5
2.1 Анализ..........................................................................
.......................................................................... 5
2.2 Реализация......................................................................
........................................................................ 5
2.3 Примеры работы..........................................................................
.......................................................... 7
3. Сортировка и поиск...........................................................................
..................................................... 9
3.1 Реализация......................................................................
....................................................................... 9
3.2 Примеры работы..........................................................................
........................................................ 13
Вывод...........................................................................
............................................................................... 15
Список использованных
источников......................................................................
........................16
Введение
В стандарте языка Си отсутствуют средства ввода-вывода. Все операции ввода-вывода реализуются с помощью функций, находящихся в библиотеке языка Си, поставляемой в составе конкретной системы программирования Си.
Особенностью языка Си, который впервые был применён при разработке операционной системы UNIX, является отсутствие заранее спланированных структур файлов. Все файлы рассматриваются как неструктурированная последовательность байтов. При таком подходе к организации файлов удалось распространить понятие файла на различные устройства. В UNIX конкретному устройству сответствует так называемый «специальный файл», а одни и те же функции библиотеки языка Си используются как для обмена данными с файлами, так и для обмена с устройствами.
Библиотека языка Си поддерживает три уровня ввода-вывода: потоковый ввод-вывод, ввод-вывод нижнего уровня и ввод-вывод для консоли и портов. Последний уровень, обеспечивающий удобный специализированный обмен данными с дисплеем и портами ввода-вывода, мы рассматривать не будем.
1. Состав проекта
1.1. Спецификация файлов
|
Файл |
Описание |
|
Main.cpp |
Основной файл проекта, содержит реализацию функции main() |
|
Test1.h |
Заголовочный файл для теста 1 (аппроксимация), содержит заголовки функций, вызываемых из main() |
|
Test1.cpp |
Файл реализации теста 1 (аппроксимация), содержит реализацию функций |
|
Test2.h |
Заголовочный файл для теста 2 (сортировка и поиск), содержит заголовки функций, вызываемых из main() |
|
Test2.cpp |
Файл реализации теста 2 (сортировка и поиск), содержит реализацию функций |
|
In11.dat |
Файл ввода для теста 1.1 |
|
In12.dat |
Файл ввода для теста 1.2 |
|
In21.dat |
Файл ввода для теста 2.1 |
|
In22.dat |
Файл ввода для теста 2.2 |
|
In11.dat |
Файл вывода для теста 1.1 |
|
In12.dat |
Файл вывода для теста 1.2 |
|
In21.dat |
Файл вывода для теста 2.1 |
|
In22.dat |
Файл вывода для теста 2.2 |
1.2. Реализация main.cpp
Файл main.cpp
#include
#include "test1.h"
#include "test2.h"
int main()
{
FILE *fin, *fin2, *fout;
fin = fopen("in11.dat", "rеt");
fout = fopen("out11.dat", "wt");
test11(fin, fout);
fclose(fin);
fclose(fout);
fin = fopen("in12.dat", "rt");
fout = fopen("out12.dat", "wt");
test12(fin, fout);
fclose(fin);
fclose(fout);
fin = fopen("in21.dat", "wt");
test2gentable(fin);
fclose(fin);
fin = fopen("in21.dat", "rt");
fout = fopen("out21.dat", "wt");
test21(false, fin, fout);
fclose(fin);
fclose(fout);
fin = fopen("in21.dat", "rt");
fout = fopen("out21.dat", "a+t");
test21(true, fin, fout);
fclose(fin);
fclose(fout);
fin = fopen("out21.dat", "rt");
fin2 = fopen("in22.dat", "rt");
fout = fopen("out22.dat", "wt");
test22(fin, fin2, fout);
fclose(fin);
fclose(fin2);
fclose(fout);
return 0;
}
2. Аппроксимация
2.1. Анализ
В качестве исследуемой функции выбрана экспонента.
Разложение функции экспоненты в ряд Маклорена:
В качестве эталонной функции используется библитечная функция exp(), заголовок которой содержится в файле math.h
2.2. Реализация
Файл test1.h
#ifndef TEST1_H_INCLUDED
#define TEST1_H_INCLUDED
#include
void test11(FILE* fin, FILE* fout);
void test12(FILE* fin, FILE* fout);
#endif // TEST1_H_INCLUDED
Файл test1.cpp
#include
#include "test1.h"
double myExp(double x, double eps);
void test11(FILE* fin, FILE* fout)
{
double xmin, xmax, deltax, eps;
fscanf(fin, "%lf %lf %lf %lf", &xmin, &xmax, &deltax, &eps);
fprintf(fout, "Test 1.1 ");
for(double x = xmin; x < (xmax + deltax); x += deltax)
{
double y1 = myExp(x, eps);
double y2 = exp(x);
fprintf(fout, "%f %f %f %f ", x, y1, y2, fabs(y1 - y2));
}
fprintf(fout, " ");
}
void test12(FILE* fin, FILE* fout)
{
double x;
fscanf(fin, "%lf", &x);
fprintf(fout, "Test 1.2 ");
for(double eps = 0.1; eps >= 0.00001; eps /= 10)
{
double y1 = myExp(x, eps);
double y2 = exp(x);
fprintf(fout, "%f %f %f %f ", eps, y1, y2, fabs(y1 - y2));
}
fprintf(fout, " ");
}
double myExp(double x, double eps)
{
int i = 1;
double r = 1, y = 0;
while(r >= eps)
{
y += r;
r *= x / i++;
}
return y;
}
2.3. Пример работы
Файл in11.dat
Входной файл для теста 1.1.
На вход выдаются следующие параметры: xmin, xmax, deltax, eps
1.0 4.0 0.1 0.001
Файл out11.dat
Выходной файл для теста 1.1.
Каждая строка выходного файла включает в себя соответственно: x, y аппроксимированное, y эталонное, разность между аппроксимированным и эталонным.
Test 1.1
1.000000 2.718056 2.718282 0.000226
1.100000 3.003719 3.004166 0.000447
1.200000 3.319283 3.320117 0.000834
1.300000 3.669061 3.669297 0.000236
1.400000 4.054768 4.055200 0.000432
1.500000 4.480929 4.481689 0.000760
1.600000 4.952808 4.953032 0.000225
1.700000 5.473555 5.473947 0.000392
1.800000 6.048984 6.049647 0.000664
1.900000 6.684802 6.685894 0.001093
2.000000 7.388713 7.389056 0.000344
2.100000 8.165604 8.166170 0.000566
2.200000 9.024103 9.025013 0.000911
2.300000 9.973888 9.974182 0.000294
2.400000 11.022702 11.023176 0.000474
2.500000 12.181743 12.182494 0.000751
2.600000 13.462571 13.463738 0.001167
2.700000 14.879338 14.879732 0.000394
2.800000 16.444032 16.444647 0.000615
2.900000 18.173200 18.174145 0.000946
3.000000 20.085213 20.085537 0.000324
3.100000 22.197450 22.197951 0.000501
3.200000 24.531766 24.532530 0.000764
3.300000 27.111489 27.112639 0.001150
3.400000 29.963693 29.964100 0.000407
3.500000 33.114836 33.115452 0.000616
3.600000 36.597313 36.598234 0.000922
3.700000 40.446974 40.447304 0.000330
3.800000 44.700688 44.701184 0.000496
3.900000 49.401711 49.402449 0.000739
4.000000 54.597062 54.598150 0.001088
Файл in12.dat
Входной файл для теста 1.2.
На вход выдаются следующие параметры: x.
2.0
Файл out12.dat
Выходной файл для теста 1.2.
Каждая строка выходного файла включает в себя соответственно: eps, y аппроксимированное, y эталонное, разность между аппроксимированным и эталонным.
Test 1.2
0.100000 7.266667 7.389056 0.122389
0.010000 7.380952 7.389056 0.008104
0.001000 7.388713 7.389056 0.000344
0.000100 7.388995 7.389056 0.000061
0.000010 7.389046 7.389056 0.000010
3. Сортировка и поиск
3.1. Реализация
Файл test2.h
#ifndef TEST2_H_INCLUDED
#define TEST2_H_INCLUDED
void test2gentable(FILE* fin);
void test21(bool obr, FILE* fin, FILE* fout);
void test22(FILE* fin1, FILE* fin2, FILE* fout);
#endif // TEST2_H_INCLUDED
Файл test2.cpp
#include
#include
#include
#include
bool sravn(bool obr, int a, int b)
{
if(obr)
return (a < b);
else
return (a > b);
}
void bubbleSort(bool obr, int *a, int n, int* c1, int* c2)
{
for (int i = 0; i < n-1; i++)
{
bool swapped = false;
for (int j = 0; j < n-i-1; j++)
{
(*c1)++;
if (sravn(obr, a[j], a[j+1]))
{
(*c2)++;
int b = a[j];
a[j] = a[j+1];
a[j+1] = b;
swapped = true;
}
}
if(!swapped)
break;
}
}
void insertionSort(bool obr, int *a, int n, int* c1, int* c2)
{
int newElement, location;
for (int i = 1; i < n; i++)
{
newElement = a[i];
location = i - 1;
while(location >= 0 && sravn(obr, a[location], newElement))
{
(*c1)++;
(*c2)++;
a[location+1] = a[location];
location = location - 1;
}
a[location+1] = newElement;
}
}
void shellSort (bool obr, int *a, int n, int* c1, int* c2)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
(*c1)++;
for (j = i - gap; j >= 0 && sravn(obr, a[j], a[j + gap]); j -= gap)
{
(*c2)++;
temp = a[j];
a[j] = a[j + gap];
a[j + gap] = temp;
}
}
}
}
void quickSort(bool obr, int *a, int l, int r, int* c1, int* c2)
{
if(l >= r)
return;
int m = l + random() % (r - l + 1);
int pivot = a[m];
int i = l, j = r;
do
{
for(;sravn(obr, pivot, a[i]); i++)
(*c1)++;
for(;sravn(obr, a[j], pivot); j--)
(*c1)++;
if(i <= j)
{
(*c2)++;
int t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}while (i < j);
quickSort(obr, a, l, j, c1, c2);
quickSort(obr, a, i, r, c1, c2);
}
void test2gentable(FILE* fin)
{
int data[4][30];
srand(time(0));
for(int i=0; i<4; i++)
{
for(int j=0; j<30; j++)
{
data[i][j] = (rand() % 99) + 1;
fprintf(fin, "%d ", data[i][j]);
}
fprintf(fin, " ");
}
}
void test21(bool obr, FILE* fin, FILE* fout)
{
int data[4][30];
for(int i=0; i<4; i++)
{
for(int j=0; j<30; j++)
{
fscanf(fin, "%d ", &data[i][j]);
}
}
int c1[4], c2[4];
for(int i=0; i<4; i++)
{
c1[i] = 0;
c2[i] = 0;
}
bubbleSort(obr, data[0], 30, &c1[0], &c2[0]);
insertionSort(obr, data[1], 30, &c1[1], &c2[1]);
shellSort(obr, data[2], 30, &c1[2], &c2[2]);
quickSort(obr, data[3], 0, 29, &c1[3], &c2[3]);
for(int i=0; i<4; i++)
{
for(int j=0; j<30; j++)
{
fprintf(fout, "%d ", data[i][j]);
}
fprintf(fout, ": %d / %d ", c2[i], c1[i]);
}
}
int binSearch(int a[], int n, int x)
{
int l, r, m;
l = 0;
r = n - 1;
m = 0;
while((a[m = (l + r) / 2] != x) && (l <= r))
{
if(a[m] > x)
r = m - 1;
else
l = m + 1;
}
if(l > m)
return -1;
else
return m;;
}
void test22(FILE* fin1, FILE* fin2, FILE* fout)
{
int data[4][30];
for(int i=0; i<4; i++)
{
for(int j=0; j<30; j++)
{
fscanf(fin1, "%d ", &data[i][j]);
}
}
int x;
fscanf(fin2, "%d", &x);
int i, j;
for(i=0, j=-1; i<4 && (j<0); i++)
j = binSearch(data[i], 30, x);
if(j == -1)
fprintf(fout, "-1 ");
else
fprintf(fout, "%d %d ", i, j+1);
}
3.2. Пример работы
Файл in21.dat
Входной файл, представляет собой исходную таблицу, сгенерированную генератором псевдослучайных чисел
3 83 50 19 43 42 21 48 10 88 40 83 4 92 13 97 36 12 83 12 9 84 34 43 92 43 88 50 71 55
80 73 36 28 92 78 68 11 25 77 98 62 59 2 52 71 96 87 80 77 97 88 61 31 32 52 71 20 99 43
72 79 14 9 6 6 86 73 14 9 48 12 71 7 11 23 75 8 11 54 82 8 42 44 36 71 93 7 88 92
47 61 70 61 67 75 64 51 46 78 60 93 89 31 98 98 51 71 4 61 25 85 66 65 27 99 36 20 5 25
Файл out21.dat
Выходной файл, формируется следующим образом:
Строка 1 — строка 1 входного файла, отсортированная прямой пузырьковой сортировкой;
Строка 2 — строка 2 входного файла, отсортированная прямой сортировкой вставками;
Строка 3 — строка 3 входного файла, отсортированная прямой сортировкой Шелла;
Строка 4 — строка 4 входного файла, отсортированная прямой быстрой сортировкой;
Строка 5 — строка 5 входного файла, отсортированная обратной пузырьковой сортировкой;
Строка 6 — строка 6 входного файла, отсортированная обратной сортировкой вставками;
Строка 7 — строка 7 входного файла, отсортированная обратной сортировкой Шелла;
Строка 8 — строка 8 входного файла, отсортированная обратной быстрой сортировкой;
Каждая строка сопровождается двумя числами, разделенными символом «/»: соответственно количество сравнений и количество замен
3 4 9 10 12 12 13 19 21 34 36 40 42 43 43 43 48 50 50 55 71 83 83 83 84 88 88 92 92 97 : 177 / 380
2 11 20 25 28 31 32 36 43 52 52 59 61 62 68 71 71 73 77 77 78 80 80 87 88 92 96 97 98 99 : 220 / 220
6 6 7 7 8 8 9 9 11 11 12 14 14 23 36 42 44 48 54 71 71 72 73 75 79 82 86 88 92 93 : 63 / 94
4 5 20 25 25 27 31 36 46 47 51 51 60 61 61 61 64 65 66 67 70 71 75 78 85 89 93 98 98 99 : 50 / 123
97 92 92 88 88 84 83 83 83 71 55 50 50 48 43 43 43 42 40 36 34 21 19 13 12 12 10 9 4 3 : 248 / 414
99 98 97 96 92 88 87 80 80 78 77 77 73 71 71 68 62 61 59 52 52 43 36 32 31 28 25 20 11 2 : 211 / 211
93 92 88 86 82 79 75 73 72 71 71 54 48 44 42 36 23 14 14 12 11 11 9 9 8 8 7 7 6 6 : 65 / 94
99 98 98 93 89 85 78 75 71 70 67 66 65 64 61 61 61 60 51 51 47 46 36 31 27 25 25 20 5 4 : 45 / 91
Файл in22.dat
Входной файл, содержит искомое число.
Производится бинарный поиск в первых четырех строках отсортированной таблицы (файл out21.dat)
42
Файл out22.dat
Выходной файл.
Если искомое число найдено, то формируется номер строки и индекс числа в строке (начиная с 1).
Если число не найдено, то формируется «-1».
1 13
Вывод
В процессе выполнения данного задания я познакомилась с возможностями ввода-вывода программ и методами сортировки языка Си.
Список использованных источников
1. Подбельский В.В., Фомин С.С. Программирование на языке Си: Учебное пособие. - изд. 2-е, доп. - Москва: Финансы и статистика, 2000. - 600 с..: ил.
(zip - application/zip)
Статистика файлового архива
