Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

231882*1002;23.1882 + 0.0231834 = 23.2113834 = 23.2114 = 0.232114*1002;23.2114 + 0.00245383 = 23.21385383 = 23.2138*1002;23. 2138 + 0.000945722 = 23.214745722 = 23.2147 = 0.232147*1002;b) 0.645391*10-03 + 0.9457*10-03 + 0.245383*10-02 + 0.231834*10-01 +0.231876*1002 = 0.232157*1002;0.000645391 + 0.000945722 = 0.001591113 = 0.00159111 = 0. 159111*10-02;0.00159111 + 0.00245383 = 0.00494493 = 0. 494493*10-02;0.00494493 + 0.0231834 = 0.02812833 = 0.0281283 = 0. 281283*10-01;0.0281283 + 23.1876 = 23.2157283 = 23.2157 = 0.232157*1002;20Пример 2.

Вычисление разности плавающих чисел(мантисса – 6 десятичных цифр, порядок – 2 десятичных цифры):0.238617*1002 – 0.238616*1002 + 0.645391*1004 – 0.645392*1004 + 0.845791*1000 –0.835790*1000 =0.238617*1002 – 0.238616*1002 + 0.645391*1004 – 0.645392*1004 +a)0.845791*1000 – 0.835790*1000 = 0.100000*10-050.238617*1002 – 0.238616*1002 = 23.8617 – 23.8616 = 0.0001 = 0.100000*10030.100000*10-03 + 0.645391*1004 = 0.0001 + 6453.91 = 6453.9101 = 0.645391*10040.645391*1004 – 0.645392*1004 = – 0.000001*1004 = – 0.100000*10-01– 0.100000*10-01 + 0.845791*1000 = – 0.01 + 0.845791 = 0.835791 *10000.835791 *1000 – 0.835790*1000 = 0.000001*1000 = 0.100000*10-05b)0.238617*1002 + 0.645391*1004 + 0.845791*1000 – (0.238616*1002 + 0.645392*1004+ 0.835790*1000) = 0.100000*10000.238617*1002 + 0.645391*1004 = 23.8617 – 6453.91 = 6478.6 = 0.647777*10040.647777*1004 + 0.845791*1000 = 6477.77 + 0.845791 = 6478.615791 =0.647862*10040.238616*1002 + 0.645392*1004 = 23.8616 + 6453.92 = 6477.7816 = 6477.78*10046477.78*1004 + 0.835790*1000 = 6477.78 + 0.835790 = 6478.61579 = 0.647852*10040.647862*1004 – 0.647852*1004= 0.000010*1004 = 0.100000*10-0021Выводы(1)При вычислении суммы чисел с одинаковыми знакаминеобходимо упорядочить слагаемые по возрастанию искладывать, начиная с наименьших слагаемых.(2)При вычислении суммы чисел с разными знакаминеобходимо сначала сложить все положительные числа,потом – все отрицательные числа и в конце выполнитьодно вычитание.(3)Вычитание (сложение чисел с противоположными знаками)часто приводит к потере точности, которая у чиселс плавающей точкой определяется количеством значащих цифрв мантиссе (при вычитании двух близких чисел мантисса«исчезает», что ведет к резкой потере точности).Итак, чем меньше вычитаний, тем точнее результат.Значащими цифрами числа с плавающей точкой называются все цифры его мантиссыза исключением нулей, стоящих в ее конце.

Например, у числа 0.67000890000 * 103 всецифры, выделенные жирным шрифтом, значащие. При вычитании двух близких чиселпочти все значащие цифры пропадают. Например, 0.67000890 * 103 - 0.67000880 * 103 =0.00000010 * 103 = 0.10 * 10-4. Таким образом, у результата всего одна значащая цифра,22хотя у операндов было по 7 значащих цифр.Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 101Поразрядные операции& (поразрядное И)| (поразрядное включающее ИЛИ)^ (поразрядное исключающее ИЛИ)<< (сдвиг влево)>> (сдвиг вправо)Беззнаковое число – заполнение нулямиЗнаковое число – заполнение значениемзнакового разряда («арифметический сдвиг»)или нулями («логический сдвиг»)~ (дополнение до 1, или инверсия)2Тип «степень множества» (булеан)Пусть U − множество.

Множество всех подмножеств множестваU называется степенью множества U.Пусть B − степень конечного множества U. Тогда B = 2 U .Характеристической функцией χC подмножества C множества Uназывается функция, принимающая значение 1 на элементах U,входящих в состав C, и значение 0 на остальных элементах U.Множества удобно задавать через их характеристическиефункции. При этом в зависимости от количества элементовбазового множества U его характеристическая функция,кодированная битами целого типа, может иметь типunsigned char (если |U| ≤ 8)unsigned int (если |U| ≤ 32)unsigned long long (если |U| ≤ 64)3Тип «степень множества»Пример. Пусть U = {r, o, y, g, c, b, v, w}.

Тогда егоподмножества задаются переменными типаUB=2unsigned char:{} задается значением 00000000,{r, y, g} – значением 10110000{r, o, y, g, c, b, v, w}– значением 11111111буквы r, o, y, g, c, b, v, w являются первыми буквами семи цветовспектра и белого цвета:r – redc – cyano – orangeb – bluey – yellowv – violetg – greenw – white4Реализация операций над множествами с помощьюпоразрядных операций& (поразрядное И) соответствует пересечениюмножеств:B = {r, y, g, b, w}, C = {r, o, y, g, v}χB = 10110101, χC = 11110010χB & χC = 10110101 & 11110010 = 10110000B ∩ C = {r, y, g}5Реализация операций над множествами с помощьюпоразрядных операций| (поразрядное включающее ИЛИ) соответствуетобъединению множеств:B = {r, y, g, b, w}, C = {r, o, y, g, v}χB = 10110101, χC = 11110010χB | χC = 10110101 | 11110010 = 11110111B ∪ C = {r, o, y, g, b, v, w}6Реализация операций над множествами с помощьюпоразрядных операций~ (инверсия) соответствует дополнению домножества U:B = {r, y, g, b, w}χB = 10110101χ~B = 01001010~ B = {o, c, v}7СтруктурыСтруктура – это совокупность несколькихпеременных, часто разных типов, сгруппированныхпод одним именем для удобстваПеременные, перечисленные в объявленииструктуры, называются ее полями,элементами, или членами.Объявление структуры:struct метка структуры { поля структуры };struct point{int x;int y;} f, g;struct point h, center = {32, 32};8СтруктурыПоля структуры могут иметь любой тип, например,тип массива или тип другой структурыstruct rect{struct point pt1;struct point pt2;};Инициализация структуры:struct rect r = {.pt1 = {4, 4},.pt2 = {7, 6}};/* Остальные элементы – нулевые */struct rect r2 = {.pt2.x = 5};Размер структуры в общем случае не равен суммеразмеров ее элементов (выравнивание)9СтруктурыДоступ к полям структуры: операция точка "."f.x, g.y, r.pt1.xПрисваивание структур целиком: f = g;Массивы структур#define NRECT 15/* Первый прямоугольник вокруг 0, 0 */struct rect rectangles[NRECT]= {{-1, -1, 1, 1}};/* Последний прямоугольник – большой */#define BOUND 1024struct rect bounded_rectangles[NRECT]= {[NRECT-1] = {-BOUND, -BOUND,BOUND, BOUND}};10Указатели на структурыstruct rect r = {.pt1 = {4, 4},.pt2 = {7, 6}};struct rect *pr = &r;Доступ к полям структуры через указатель:pr->pt1 (= (*pr).pt1), pr->pt2.xАдресная арифметика:struct rect *pr = &bounded_rectangles[0];while (pr->pt1.x != -BOUND)pr++;11Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 111Составные инициализаторы структур (C99)struct rect r;r = (struct rect) { {4, 4},{7, 6}};Составной инициализатор генерирует lvalue!Т.е.

можно передавать и указатель:double area (struct rect *r) {return (r->pt1.x – r->pt2.x)* (r->pt1.y – r->pt2.y);}double da= area (& (struct rect) {{4, 4}, {7, 6}});2Приоритеты операцийОперацииАссоциативность( ) [ ] -> .Слева направо! ~ ++ -- + - sizeof (type) * &Справа налево* / %Слева направо+ -Слева направо<< >>Слева направо< <= > >=Слева направо== !=Слева направо&Слева направо^Слева направо|Слева направо&&Слева направо||Слева направо?:Справа налево= += -= *= /= %= &= ^= |= <<= >>=Справа налево,Слева направо3ОбъединенияОбъединение – это объект, который можетсодержать значения различных типов (но неодновременно – только одно в каждый момент)struct constant{int ctype;union{int i;float f;char *s;} u;} sc;switch (sc.ctype){case CI:printf("%d",sc.u.i);break;case CF:printf("%f",sc.u.f);break;case CS: puts(sc.u.s);}Размер объединения достаточно велик, чтобысодержать максимальный по размеру элементМожно выполнять те же операции, что и соструктурами4Анонимные объединения и структуры (С11)Для вложенных структур и объединений разрешеноопускать тег для повышения читаемостиstruct constant{int ctype;union{int i;float f;char *s;} /* нет имени! */;} sc;switch (sc.ctype){case CI:printf("%d",sc.i);break;case CF:printf("%f",sc.f);break;case CS: puts(sc.s);}Поля анонимной структуры считаютсяпринадлежащими родительской структуре(если родительская также анонимна – то следующейродительской структуре и т.п.)5Битовые поляДля экономии памяти можно точно задать размерполя в битах (например, набор флагов)struct tree_base {unsigned code : 16;unsigned side_effects_flag : 1;unsigned constant_flag : 1;<...>unsigned lang_flag_0 : 1;unsigned lang_flag_1 : 1;<...>unsigned spare : 12;}Адрес битового поля брать запрещеноМожно объявить анонимные поля (для выравнивания)Можно объявить битовое поле ширины 0 (для перехода6на следующий байт)ПеречисленияПеречисления – целочисленные типы данных,определяемые программистом.Определение перечисления:enum имя_типа { имена значений };enum colors {red, orange, yellow, green,azure, blue, violet};Значения перечисления нумеруются с 0, но можноприсваивать свои значенияenum {red, orange = 23, yellow = 23,green, cyan = 75, blue = 75, violet};Доступны операции над целочисленными типами иобъявление указателей на переменныеперечислимых типовПроверка корректности присваиваемых значений7не производитсяПрограмма: вычисление площадей фигурФигура определяется общей структурой, в которойобъединены различные конкретные структуры дляопределенных фигур и поле тега фигурыИспользуется перечисление для задания возможныхтипов фигурИспользуется адресная арифметика для обходамассива считанных фигурДля обработки фигуры используется операторвыбора по тегу фигуры8Программа: типы данныхenum figure_tag {CIRCLE,RECTANGLE,TRIANGLE,LAST_FIGURE};struct point {double x, y;};struct fcircle {struct point center;double radius;};struct frectangle {struct point ll, ur;};9Программа: типы данныхstruct ftriangle {struct point a, b, c;};struct figure {enum figure_tag tag;union {struct fcircle fc;struct frectangle fr;struct ftriangle ft;} u;};struct farea {double min, max;int initialized : 1;};10Программа: основная функцияint main (void) {enum { MAXFIG = 128 };struct figure figs[MAXFIG + 1];struct farea areas[LAST_FIGURE];int i = 0;while (i < MAXFIG)if (!read_figure (&figs[i]))break;elsei++;if (i == 0)return 1;<...

Обработка данных и вывод ...>}11Программа: основная функцияint main (void) {enum { MAXFIG = 128 };struct figure figs[MAXFIG + 1];struct farea areas[LAST_FIGURE];int i = 0;<... Считывание данных ...>figs[i].tag = LAST_FIGURE;for (i = CIRCLE; i < LAST_FIGURE; i++) {areas[i].initialized = 0;calculate_minmax_areas (i, figs, &areas[i]);output_minmax_areas (i, &areas[i]);}return 0;}12Программа: подсчет площадиstatic void calculate_minmax_areas (enum figure_tag tag,struct figure *f, struct farea *fa) {for (; f->tag != LAST_FIGURE; f++)if (f->tag == tag) {double a = calculate_area (f);if (!fa->initialized) {fa->min = fa->max = a;fa->initialized = 1;} else {if (a < fa->min)fa->min = a;if (a > fa->max)fa->max = a;}}}13Программа: подсчет площадиstatic double calculate_area (struct figure *f) {double a = 0.0;switch (f->tag) {case CIRCLE: a = f->u.fc.radius * f->u.fc.radius *M_PI; break;case RECTANGLE: a = fabs ((f->u.fr.ll.x –f->u.fr.ur.x) * (f->u.fr.ll.y - f->u.fr.ur.y));break;case TRIANGLE: <...>default: assert (0);}return a;}14Программа: подсчет площадиstatic double calculate_area (struct figure *f) {double a = 0.0;switch (f->tag) {<...>case TRIANGLE: {double x1, y1, x2, y2;x1 = f->u.ft.b.x - f->u.ft.a.x;y1 = f->u.ft.b.y - f->u.ft.a.y;x2 = f->u.ft.c.x - f->u.ft.a.x;y2 = f->u.ft.c.y - f->u.ft.a.y;a = fabs (x1 * y2 - x2 * y1) / 2;break;}<...>}return a;}15Программа: вводstatic int read_figure (struct figure *f) {char name;if (scanf (" %c", &name) != 1)return 0;switch (toupper (name)) {case 'C': f->tag = CIRCLE; break;case 'R': f->tag = RECTANGLE; break;case 'T': f->tag = TRIANGLE; break;default: return 0;}<...>return 1;}16Программа: вводstatic int read_figure (struct figure *f) {<...>switch (f->tag) {case CIRCLE: if (scanf ("%lf%lf%lf", &f->u.fc.center.x,&f->u.fc.center.y, &f->u.fc.radius) != 3)return 0;break;case RECTANGLE: if (scanf ("%lf%lf%lf%lf",&f->u.fr.ll.x, &f->u.fr.ll.y, &f->u.fr.ur.x,&f->u.fr.ur.y) != 4)return 0;break;case TRIANGLE: if (scanf ("%lf%lf%lf%lf%lf%lf",&f->u.ft.a.x, &f->u.ft.a.y, &f->u.ft.b.x,&f->u.ft.b.y, &f->u.ft.c.x, &f->u.ft.c.y) != 6)return 0;break;17}Программа: вывод и заголовочные файлы#include <stdio.h>#include <ctype.h>#include <math.h>#include <assert.h>static void output_minmax_areas (enum figure_tag ft,struct farea *fa) {static char *fnames[LAST_FIGURE] = {"CIRCLE","RECTANGLE", "TRIANGLE"};if (!fa->initialized)printf ("No figures of type %s were met\n",fnames[ft]);else {printf ("Minimal area of %s(s): %.5f\n", fnames[ft],fa->min);printf ("Maximal area of %s(s): %.5f\n", fnames[ft],fa->max);}18}Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 121Динамическое распределение памятиФункцияvoid *malloc (size_t size)выделяет область памяти размером size байтов и возвращаетуказатель на выделенную область памяти.Если память не выделена (например, в системе не осталосьсвободной памяти требуемого размера), возвращаемыйуказатель имеет значение NULL.Поскольку результат операции sizeof имеет тип size_tи равен длине операнда в байтах, в качестве size можноиспользовать результат операции sizeof.Тривиальные примеры:(1)Выделение непрерывного участка памяти объемом 1000 байтов:char *p;p = (char *) malloc (1000);(2)Выделение памяти для 50 целых:int *p;/* явное приведение типа необязательно */p = malloc (50 * sizeof (int));2Динамическое распределение памятиФункцияvoid free (void *p)возвращает системе выделенный ранее участок памяти суказателем p.Важное замечание: Аргументом функции free() обязательнодолжен быть указатель p на участок памяти, выделенной ранеефункцией malloc().Вызов функции free() с неправильным указателем неопределен и может привести к разрушению системыраспределения памяти.Вызов функции free() с указателем NULL не приводитни к каким действиям (С99).Функции malloc()и free()входят в состав библиотекиstdlib.h.3Динамическое распределение памятиПример.

Характеристики

Список файлов лекций