10 (1106247)

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

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 101Операции над числами с плавающей точкойПо определению:x + FP y = Round ( x + y )x × FP y = Round ( x × y )где Round() означает округлениеВыполнение операцииСначала вычисляется точный результат(получается более длинная мантисса, чемзапоминаемая, иногда в два раза)Потом фиксируется исключение(например, переполнение)Потом результат округляется, чтобыпоместиться в поле frac2Умножение чисел с плавающей точкой(−1) s1 ⋅ M 1 ⋅ 2e1 × (−1) s 2 ⋅ M 2 ⋅ 2e 2Точный результат ( −1) s ⋅ MЗнак sЗначащие цифры MПорядок eПреобразованиеЕсли M ≥ 2, сдвиг M вправо с одновременнымувеличением еЕсли е не помещается в поле exp,переполнениеОкругление M, чтобы оно поместилосьв поле fracОсновные затраты на перемножение мантисс3⋅ 2es1 ∧ s2M1 × M2e1+ e2Сложение чисел с плавающей точкой(−1) s1 ⋅ M 1 ⋅ 2e1 + (−1) s 2 ⋅ M 2 ⋅ 2e 2Пусть e1 > e2Точный результат(−1) s ⋅ M ⋅ 2eЗнак s и значащиецифры M вычисляются как показанона рисункеПорядок суммы – e1ПреобразованиеЕсли M ≥ 2, сдвиг M вправо с одновременнымувеличением еЕсли M < 1, сдвиг M влево на k позицийс одновременным вычитанием k из еЕсли е не помещается в поле exp, переполнениеОкругление M, чтобы оно поместилось в поле frac4Плавающие типы языка Сиfloat, double, long doubleОперации над данными с плавающей точкой.Одноместные: изменение знака («одноместный минус»: –),одноместный плюс (+).Двухместные:сложение (+), вычитание (–), умножение (*),деление (/).Порядок выполнения арифметических операций ввыражениях (приоритет).самый низкий приоритет у двуместных + и –,более высокий приоритет у двуместных * и /,еще более высокий приоритет у одноместных + и –.В выражениях без скобок операции с более высокимприоритетом выполняются раньше.Скобки позволяют изменить порядок выполнения операций.5Пример 1.

Вычисление суммы 5 чисел типа float(мантисса – 6 десятичных цифр, порядок – 2 десятичных цифры):0.231876*1002 + 0.645391*10-03 + 0.231834*10-01 + 0.245383*10-02 +0.945722*10-03 =a) 0.231876*1002 + 0.645391*10-03 + 0.231834*10-01 + 0.245383*10-02 +0.945722*10-03 = 0.232147*1002;23.1876 + 0.000645391 = 23.188245391 = 23.1882 = 0. 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;6Пример 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-007Выводы(1)При вычислении суммы чисел с одинаковыми знакаминеобходимо упорядочить слагаемые по возрастанию искладывать, начиная с наименьших слагаемых.(2)При вычислении суммы чисел с разными знакаминеобходимо сначала сложить все положительные числа,потом – все отрицательные числа и в конце выполнитьодно вычитание.(3)Вычитание (сложение чисел с противоположными знаками)часто приводит к потере точности, которая у чиселс плавающей точкой определяется количеством значащих цифрв мантиссе (при вычитании двух близких чисел мантисса«исчезает», что ведет к резкой потере точности).Итак, чем меньше вычитаний, тем точнее результат.Значащими цифрами числа с плавающей точкой называются все цифры его мантиссыза исключением нулей, стоящих в ее конце.

Например, у числа 0.67000890000 * 103 всецифры, выделенные жирным шрифтом, значащие. При вычитании двух близких чиселпочти все значащие цифры пропадают. Например, 0.67000890 * 103 - 0.67000880 * 103 =0.00000010 * 103 = 0.10 * 10-4. Таким образом, у результата всего одна значащая цифра,8хотя у операндов было по 7 значащих цифр.Поразрядные операции& (поразрядное И)| (поразрядное включающее ИЛИ)^ (поразрядное исключающее ИЛИ))<< (сдвиг влево)>> (сдвиг вправо)Беззнаковое число – заполнение нулямиЗнаковое число – заполнение значениемзнакового разряда («арифметический сдвиг»)или нулями («логический сдвиг»)~ (дополнение до 1, или инверсия)9Тип «степень множества» (булеан)Пусть 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)10Тип «степень множества»Пример. Пусть 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 – white11Реализация операций над множествами с помощьюпоразрядных операций& (поразрядное И) соответствует пересечениюмножеств: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}12Реализация операций над множествами с помощьюпоразрядных операций| (поразрядное включающее ИЛИ) соответствуетобъединению множеств: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}13Реализация операций над множествами с помощьюпоразрядных операций~ (инверсия) соответствует дополнению домножества U:B = {r, y, g, b, w}χB = 10110101χ~B = 01001010~ B = {o, c, v}14СтруктурыСтруктура – это совокупность несколькихпеременных, часто разных типов, сгруппированныхпод одним именем для удобстваПеременные, перечисленные в объявленииструктуры, называются ее полями,элементами, или членами.Объявление структуры:struct метка структуры { поля структуры };struct point{int x;int y;} f, g;struct point h, center = {32, 32};15СтруктурыПоля структуры могут иметь любой тип, например,тип массива или тип другой структурыstruct rect{struct point pt1;struct point pt2;};Инициализация структуры:struct rect r = {.pt1 = {4, 4},.pt2 = {7, 6}};/* Остальные элементы – нулевые */struct rect r2 = {.pt2.x = 5};Размер структуры в общем случае не равен суммеразмеров ее элементов (выравнивание)16СтруктурыДоступ к полям структуры: операция точка "."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}};17Указатели на структуры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++;18Составные инициализаторы структур (C99)struct rect r;r = (struct rect) { {4, 4},{7, 6}};Можно передавать и указатель: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}});19.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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