Вопросы для абитуриентов, поступающих на специальность 0712 (150302) «Триботехника» после окончания техникума, или после окончания 3-го курса техникума
Скачать 1.34 Mb.
|
a+b = a при b 0 Более того, для сложения не выполняется закон ассоциативности: a+(b+c) (a+b)+c Действительно, пусть ε - максимальное плавающее число среди чисел, удовлетворяющих условию 1.0+ε = 1.0 (приведенные выше рассуждения показывают, что такие числа существуют). Тогда (1.0+ε)+ε 1.0+(ε+ε) поскольку левая часть неравенства равна единице, а правая строго больше единицы (это следует из максимальности числа ε). Число ε часто называют машинным эпсилоном или, чуть менее корректно, машинным нулем, поскольку при прибавлении к единице оно ведет себя как ноль. Величина машинного эпсилона характеризует точность операций компьютера. Она примерно одинакова для всех современных компьютеров: большинство процессоров работают с восьмибайтовыми плавающими числами (тип double в Си), а арифметика плавающих чисел подчиняется строгим международным стандартам. Оценим величину машинного эпсилона для типа double. Число 1.0 записывается в плавающей форме как 1.0 = +20*1.0. Порядок плавающего числа 1.0 равен нулю. При сложении 1.0 с числом ε производится выравнивание порядка путем многократного сдвига мантиссы числа ε вправо и увеличения его порядка на 1. Поскольку все разряды числа ε должны в результате выйти за пределы разрядной сетки, должно быть выполнено 53 сдвига. Порядок числа ε после этого должен стать равным порядку числа 1.0, т.е. нулю. Следовательно, изначально порядок числа ε должен быть равным -53: ε = 2-53*m где m - число в диапазоне от единицы до двух. Таким образом, величина машинного эпсилона составляет примерно 2-53 10-16 Приблизительно точность вычислений составляет 16 десятичных цифр. (Это также можно оценить следующим образом: 53 двоичных разряда составляют примерно 15.95 десятичных, поскольку 53/log210 53/3.321928 15.95.) В случае четырехбайтовых плавающих чисел (тип float языка Си) точность вычислений составляет примерно 7 десятичных цифр. Это очень мало, поэтому тип float чрезвычайно редко применяется на практике. К тому же процессор сконструирован для работы с восьмибайтовыми вещественными числами, а при работе с четырехбайтовыми он все равно сначала приводит их к восьмибайтовому типу. В программировании следует избегать типа float и всегда пользоваться типом double. Некоторые процессоры применяют внутреннее представление плавающих чисел с большим количеством разрядов мантиссы. Например, процессор Intel использует 80-битовое (десятибайтовое) представление. Поэтому точность вычислений, которые не записывают промежуточные результаты в память, может быть несколько выше указанных оценок. Кроме потери точности, при операциях с вещественными числами могут происходить и другие неприятности: переполнение - когда порядок результата больше максимально возможного значения. Эта ошибка часто возникает при умножении больших чисел; исчезновение порядка - когда порядок результата отрицательный и слишком большой по абсолютной величине, т.е. порядок меньше минимально допустимого значения. Эта ошибка может возникнуть при делении маленького числа на очень большое или при умножении двух очень маленьких по абсолютной величине чисел. Кроме того, некорректной операцией является деление на ноль. В отличие от операций с целыми числами, переполнение и исчезновение порядка считаются ошибочными ситуациями и приводят к аппаратному прерыванию работы процессора. Программист может задать реакцию на прерывание - либо аварийное завершение программы, либо, например, при переполнении присваивать результату специальное значение плюс или минус бесконечность, а при исчезновении порядка - ноль. Заметим, что среди двоичных кодов, представляющих плавающие числа, имеется несколько специальных значений. Перечислим некоторые из них: бесконечно большое число - это плавающее число с очень большим положительным порядком и, таким образом, очень большое по абсолютной величине. Оно может иметь знак плюс или минус; бесконечно малое, или денормализованное, число - это ненулевое плавающее число с очень большим отрицательным порядком (т.е. очень маленькое по абсолютной величине); Not a Number, или NaN - двоичный код, который не является корректным представлением какого-либо вещественного числа. Любые операции с константой NaN приводят к прерыванию, поэтому она удобна при отладке программы - ею перед началом работы программы инициализируются значения всех вещественных переменных. Если в результате ошибки программиста при вычислении выражения используется переменная, которой не было присвоено никакого значения, то происходит прерывание из-за операции со значением NaN и ошибка быстро отслеживается. К сожалению, в случае целых чисел такой константы нет: любой двоичный код представляет некоторое целое число. Запись вещественных констант Вещественные константы записываются в двух формах - с фиксированной десятичной точкой или в экспоненциальном виде. В первом случае точка используется для разделения целой и дробной частей константы. Как целая, так и дробная части могут отсутствовать. Примеры: 1.2, 0.725, 1., .35, 0. В трех последних случаях отсутствует либо дробная, либо целая часть. Десятичная точка должна обязательно присутствовать, иначе константа считается целой. Отметим, что в программировании именно точка, а не запятая, используется для отделении дробной части; запятая обычно служит для разделения элементов списка. Экспоненциальная форма записи вещественной константы содержит знак, мантиссу и десятичный порядок (экспоненту). Мантисса - это любая положительная вещественная константа в форме с фиксированной точкой или целая константа. Порядок указывает степень числа 10, на которую домножается мантисса. Порядок отделяется от мантиссы буквой "e" (от слова exponent), она может быть прописной или строчной. Порядок может иметь знак плюс или минус, в случае положительного порядка знак плюс можно опускать. Примеры: 1.5e+6 константа эквивалентна 1500000.0 1e-4 константа эквивалентна 0.0001 -.75E3 константа эквивалентна -750.0 Символьные переменные Значением символьной переменной является один символ из фиксированного набора. Такой набор обычно включает буквы, цифры, знаки препинания, знаки математических операций и различные специальные символы (процент, амперсенд, звездочка, косая черта и др.). Подчеркнем, что, в отличие от строковой переменной, символьная всегда содержит ровно один символ. (Строковая содержит строку из нескольких символов.) Конечно, в памяти компьютера никаких символов не содержится. Символы представляются их целочисленными кодами в некоторой фиксированной кодировке. Кодировка определяется тремя параметрами: диапазоном значений кодов. Например, самая распространенная в мире кодировка ASCII (от слов American Standard Code of Information Interchange - Американский стандартный код обмена информацией) имеет диапазон значений кодов от 0 до 127, т.е. требует семь бит на символ. Большинство современных кодировок имеют диапазон кодов от 0 до 255, т.е. один байт на символ. Наконец, сейчас во всем мире осуществляется переход на кодировку Unicode, которая использует коды в диапазоне от 0 до 65535, т.е. 2 байта на символ; множеством изображаемых символов. Например, кодировка ASCII содержит буквы латинского алфавита, в западноевропейской кодировке к символам ASCII добавлены буквы с умлаутами и акцентами, дополнительные знаки препинания, в частности, испанские перевернутые вопросительные и восклицательные знаки, и другие символы европейских языков, основанных на латинской графике. Любая из русских кодировок содержит кириллицу; отображением множества кодов на множество символов. Например, русские кодировки КОИ-8 (Код обмена информацией восьмибитовый) и "Windows CP-1251", традиционно используемые в операционных системах Unix и MS Windows, имеют один и тот же диапазон кодов и один и тот же набор символов, но отображения их различны (одни и те же символы имеют разные коды в кодировках КОИ-8 и Windows). К сожалению, российские программисты не сумели договориться о единой кодировке русских букв. В настоящее время в России широко используются четыре различные кодировки: кодировка КОИ-8 (это наиболее старый стандарт, принятый еще в конце 70-х годов XX века). КОИ-8 в основном используется в системе Unix и до недавнего времени была стандартом де-факто для русскоязычной электронной почты. Последнее время, однако, все чаще в электронной почте используют кодировку Windows; так называемая альтернативная кодировка CP-866, которая используется в системе MS DOS. Она не удовлетворяет некоторым требованиям международных стандартов - например, ряд русских букв совпадает с кодами символов, используемых для управления передачей по линии. Альтернативная кодировка постепенно уходит в прошлое вместе с системой DOS; кодировка Windows CP-1251, которая появилась значительно позже кодировки КОИ-8, но создатели русской версии Windows не захотели воспользоваться КОИ-8 (по-видимому, из-за того, что коды русских букв в КОИ-8 не упорядочены в соответствии с алфавитом; в CP-1251 коды русских букв упорядочены, за исключением буквы е). В связи с распространением операционной системы Windows, кодировка Windows получает все большее распространение; кодировка, используемая в компьютерах Apple Macintosh. Существование различных кодировок русских букв сильно осложняет жизнь как программистам, так и обыкновенным пользователям: файлы при переносе из одной системы в другую приходится перекодировать, периодически возникают трудности при чтении писем, просмотре гипертекстовых страниц и т.п. Отметим, что ничего подобного нет ни в одной европейской стране. С повсеместным переходом на кодировку Unicode все проблемы такого рода должны исчезнуть. Кодировка Unicode включает символы алфавитов всех европейских стран и кириллицу. К сожалению, большинство существующих компьютерных программ приспособлено к представлению одного символа в виде одного байта. Поэтому в настоящее время часто используется промежуточное решение: компьютерные программы работают с внутренним представлением символов в кодировке Unicode (такое решение принято в языках Java и C#). При записи в файл символы Unicode приводятся к однобайтовой кодировке в соответствии с текущей языковой установкой. При этом, конечно, часть символов теряется - например, в кодировке Windows невозможно одновременно записать русские буквы и немецкие умлауты, поскольку умлауты в западно-европейской кодировке имеют те же коды, что и русские буквы в русской кодировке. Логические переменные и выражения Логические переменные принимают два значения: истина и ложь. Логические, или условные, выражения используются в качестве условия в конструкциях ветвления "если ... то ... иначе ... конец если" и цикла "пока". В первом случае в зависимости от истинности условия выполняется либо ветвь программы после ключевого слова "то", либо после "иначе"; во втором случае цикл выполняется до тех пор, пока условие продолжает оставаться истинным. В качестве элементарных условных выражений используются операции сравнения: можно проверить равенство двух выражений или определить, какое из них больше. Любая операция сравнения имеет два аргумента и вырабатывает логическое значение "истина" или "ложь" (true и false в языке C++). Мы будем обозначать операции сравнения так, как это принято в языке Си: операция проверки равенства двух выражений обозначается двойным знаком равенства == (мы не используем обычный знак равенства во избежание путаницы, поскольку часто знак равенства применяется для обозначения операции присваивания); неравенство обозначается != (в Си восклицательный знак используется для отрицания); для сравнения величин выражений применяются четыре операции больше >, больше или равно `>=, меньше <, меньше или равно <=. Несколько примеров логических выражений: x == 0 - выражение истинно, если значение переменной x равно нулю, и ложно в противном случае; 0!= 0 - выражение ложно; 3>= 2 - выражение истинно. Из элементарных логических выражений и логических переменных можно составлять более сложные выражения, используя три логические операции "и", "или", "не": результат логической операции "и" истинен, когда истинны оба ее аргумента. Например, логическое выражение 0 <= x и x <= 1 истинно, когда значение переменной x принадлежит отрезку [0, 1]. Логическую операцию "и" называют также логическим умножением или конъюнкцией; в языке Си логическое умножение обозначается двойным амперсандом &&; результат логической операции "или" истинен, когда истинен хотя бы один из ее аргументов. Например, логическое выражение x != 0 или y != 0 ложно в том и только том случае, когда значения обеих переменных x и y равны нулю. Логическую операцию "или" называют также логическим сложением или дизъюнкцией; в Си логическое сложение обозначается двойной вертикальной чертой ||; в отличие от логических операций "и" и "или", логическая операция "не" имеет только один аргумент. Ее результат истинен, когда аргумент ложен, и, наоборот, ложен, когда аргумент истинен. Например, логическое выражение не x == 0 истинно, когда значение переменной x отлично от нуля. Логическая операция "не" называется логическим отрицанием (иногда негацией); в Си логическое отрицание обозначается восклицательным знаком "!". В сложных логических выражениях можно использовать круглые скобки для указания порядка операций. При отсутствии скобок считается, что наивысший приоритет имеет логическое отрицание; затем идет логическое умножение, а низший приоритет у логического сложения. Обратим внимание на чрезвычайно важную особенность операций реализации логического сложения и умножения - так называемое сокращенное вычисление результата. А именно, в случае логического умножения всегда сначала вычисляется значение первого аргумента. Если оно ложно, то значение выражения полагается ложным, а второй аргумент не вычисляется вообще! Благодаря этой особенности можно корректно использовать выражения вроде x != 0 и y/x > 1 При вычислении значения этого выражения сначала вычисляется первый аргумент конъюнкции "x != 0". Если значение переменной x равно нулю, то первый аргумент ложен и значение второго аргумента "y/x > 1" уже не вычисляется. Это очень хорошо, поскольку при попытке его вычислить произошло бы аппаратное прерывание из-за деления на ноль. То же самое относится и к логическому сложению. Сначала всегда вычисляется первый аргумент логической операции "или". Если он истинен, то значение выражения полагается истинным, а второй аргумент не вычисляется вообще. Таким образом, операции логического сложения и умножения, строго говоря, не коммутативны. Может так случиться, что выражение "a и b" корректно, а выражение "b и a" - нет. Программисты очень часто сознательно используют эту особенность реализации логических операций. Массивы Кроме базовых типов, в большинстве алгоритмических языков присутствует конструкция массив. Иногда массив называют также таблицей или вектором. Массив позволяет объединить множество элементов одного типа в единую переменную. Все элементы массива имеют один и тот же тип. Элементы массива обычно нумеруются индексами от 0 до n-1, где n - число элементов массива. В некоторых языках можно задавать границы изменения индексов, в других нижняя граница значения индекса равна единице, а не нулю. Мы, тем не менее, будем придерживаться языка Си (а также C++, Java, C#), в котором нижней границей индекса всегда является ноль. Это очень удобно, т.к. индекс элемента массива в этом случае равен его смещению относительно начала массива. Длина массива задается при его описании и не может быть изменена в процессе работы программы. При описании массива указывается тип и число его элементов. Тип записывается перед именем массива, размер массива указывается в квадратных скобках после его имени. Примеры: цел a[100]; описан массив целых чисел размера 100 (индекс меняется от 0 до 99) вещ r[1000]; описан вещ. массив из 1000 элементов. В языке Си соответствующие описания выглядят следующим образом: int a[100]; double r[1000]; Для доступа к элементу массива указывается его имя и в квадратных скобках - индекс нужного элемента. С элементом массива можно работать как с обычной переменной, т.е. можно прочитать его значение или записать в него новое значение. Примеры: a[3] := 0; элементу массива a с индексом 3 присваивается значение 0; a[10] := a[10]*2; элемент массива a с индексом 10 удваивается. Массив - это самая важная конструкция алгоритмического языка. Важность массива определяется тем, что память компьютера логически представляет собой массив (его можно рассматривать как массив байтов или как массив четырехбайтовых машинных слов). Индекс в этом массиве обычно называют адресом. Элементы массива читаются и записываются исключительно быстро, за одно действие, независимо от размера массива и величины индекса. Для программиста конструкция массива как бы дана свыше. Большинство других структур данных, используемых в программировании, моделируются на базе массива. Текстовые строки Текстовые строки представляются массивами символов. Строковая переменная содержит на самом деле адрес этого массива. В отличие от символа, который занимает либо один, либо два байта в зависимости от используемой кодировки, строка имеет переменную длину. Существуют два способа указания длины строки: строка заканчивается символом с нулевым кодом, т.е. либо нулевым байтом в случае однобайтового представления символов, либо двумя нулевыми байтами в случае двухбайтового представления. Такой способ принят в языке Си. Отметим, что нулевой байт - это вовсе не символ '0'! Символ '0' имеет код 48 в кодировках ASCII и UNICODE, а изображаемых символов с нулевым кодом не существует; строка в качестве первого элемента (байта или двух байтов) содержит общее число символов, не включая начального элемента. Затем идут сами символы в указанном количестве. Такой способ используется в языке Паскаль. Недостаток первого способа состоит в том, что для вычисления длины строки необходимо последовательно просмотреть все ее элементы, начиная с первого, пока не будет найден нулевой байт. Такая операция может быть долгой для длинной строки. Недостаток второго способа заключается в том, что длина строки ограничена. В случае однобайтовых символов максимальная длина строки равна 255, т.е. максимальному числу, которое можно записать в одном байте. Длина строки двухбайтовых символов ограничена числом 65535. Впрочем, существуют и другие способы представления строк, которые используются в объектно-ориентированных языках. Строка рассматривается как объект, внутреннее устройство которого скрыто от пользователя, хотя, как правило, он содержит массив или адрес массива символов и длину строки. Обычно в случае представления строк в виде объектов ограничения на длину строки отсутствуют. Вычисление функций на последовательностях Как правило, компьютеры прежде всего используются для обработки значительных объемов информации. В большинстве алгоритмов информация читается последовательно, от начала к концу. Поэтому в программах очень часто встречаются фрагменты кода, вычисляющие некоторую функцию на последовательности элементов. Предположим для простоты, что последовательность элементов находится в массиве. В реальных программах она также может читаться из файла или из более сложных структур данных - например, из списка. В любом случае можно встать в начало последовательности, прочесть ее очередной элемент, а также определить, есть ли еще непрочитанные элементы. Рассмотрим пример: дана последовательность вещественных чисел, требуется вычислить сумму ее элементов. Запишем алгоритм на неформальном языке в самом общем виде. вещ алгоритм сумма последовательности | дано: последовательность вещественных чисел | надо: вернуть сумму ее элементов начало алгоритма | вещ s, x; | s := 0.0; | встать в начало последовательности | цикл пока есть непрочитанные элементы | | прочесть очередной элемент последовательности в (вых:x) | | s := s + x; | конец цикла | ответ := s; конец алгоритма Здесь перед словом "алгоритм" записывается тип возвращаемого значения, т.е. "вещ" для вещественного числа. Это означает, что алгоритм можно использовать как функцию. Например, для функции "sin" можно записать выражение y = sin(x) При вычислении выражения сначала вызывается алгоритм (функция), вычисляющий sin, затем значение, которое возвращается этим алгоритмом, присваивается переменной y. В нашем случае можно использовать выражение y := сумма последовательности; для вызова алгоритма и записи возвращаемого значения в переменную y. В случае, когда последовательность чисел находится в массиве, алгоритм выглядит следующим образом: вещ алгоритм сумма последовательности(вх: цел n, вещ a[n]) | дано: n -- число элементов последовательности, | a[n] -- массив элементов последовательности | надо: вернуть сумму элементов последовательности начало алгоритма | вещ s; цел i; | s := 0.0; // Инициализация значения ф-ции | i := 0 | цикл пока i < n | | s := s + a[i]; // Вычисление нового значения по старому | | // значению и очередному элементу | | i := i + 1; // Переходим к следующему элементу | конец цикла | ответ := s; конец алгоритма Здесь целочисленная переменная i используется в качестве индекса элемента массива. Она последовательно принимает значения от 0 до n-1. Очередной элемент последовательности записывается как a[i]. Отметим следующие составные части алгоритма, вычисляющего функцию на последовательности элементов: инициализация значения функции для пустой последовательности - в данном случае s : = 0.0; вычисление нового значения функции по прочтении очередного элемента последовательности. Новое значение вычисляется по старому значению и очередному прочитанному элементу. В данном случае это суммирование s : = s+a[i]. Эти две части присутствуют в любом алгоритме, вычисляющем функцию на последовательности. Рассмотрим еще один важный пример: вычисление максимального элемента последовательности. В отличие от суммы элементов, здесь не вполне ясно, каким значением надо инициализировать максимум, то есть чему равен максимум пустой последовательности. Для того, чтобы максимум одноэлементной последовательности вычислялся правильно, надо, чтобы максимум пустой последовательности был меньше любого числа. Поэтому максимум пустой последовательности не может быть обычным числом. В математике и в программировании очень полезен следующий прием: к обычным элементам добавляется специальный воображаемый элемент с заданными свойствами. Так были изобретены ноль, отрицательные числа, иррациональные и комплексные числа и т.п. В данном случае, таким воображаемым элементом является "минус бесконечность". вещ алгоритм максимум последовательности(вх: цел n, вещ a[n]) | дано: n -- число элементов последовательности, | a[n] -- массив элементов последовательности | надо: вернуть максимум элементов последовательности начало алгоритма | вещ m; цел i; | m := минус бесконечность; // Инициализация значения ф-ции | i := 0; | цикл пока i < n | | если a[i] > m // Вычисление нового значения по | | | то m := a[i]; // старому значению и очередному эл-ту | | конец если | | i := i + 1; | конец цикла | ответ := m; конец алгоритма Здесь переменная m на любом шаге содержит максимальное значение для просмотренного начального отрезка последовательности, т.е. кандидата на максимум. Если очередной элемент больше, чем m, то он запоминается в переменной m и становится новым кандидатом на максимум. Значение "минус бесконечность" в случае операции взятия максимума двух чисел обладает следующим замечательным свойством: для всякого числа x выполняется равенство max(минус бесконечность,x) = x Можно сравнить с операцией сложения: 0+x = x Таким образом, значение "минус бесконечность" играет роль нуля для операции взятия максимума двух чисел. Ноль - это нейтральный элемент для операции сложения: будучи прибавленным слева к произвольному числу x, он не изменяет числа x. Точно так же значение "минус бесконечность" является нейтральным для операции взятия максимума. Для операции "минимум" нейтральным элементом является "плюс бесконечность". Таким образом, алгоритм нахождения минимума последовательности выглядит следующим образом: вещ алгоритм минимум последовательности(вх: цел n, вещ a[n]) | дано: n -- число элементов последовательности, | a[n] -- массив элементов последовательности | надо: вычислить минимум элементов последовательности начало алгоритма | вещ m; цел i; | m := плюс бесконечность; // Инициализация значения ф-ции | i := 0; | цикл пока i < n | | если a[i] < m // Вычисление нового знач. по старому | | | то m := a[i]; // значению и очередному элементу | | конец если | | i := i + 1; | конец цикла | ответ := m; конец алгоритма Значения "минус" и "плюс бесконечность" Как реализовать воображаемые элементы "минус бесконечность" и "плюс бесконечность" при программировании на конкретных алгоритмических языках, а не на псевдокоде? Вспомним, что компьютер может представлять не все возможные числа, а только их ограниченное подмножество. Поэтому для компьютера существует минимальное и максимальное целое и вещественное числа. В языке Си эти константы записаны в стандартных заголовочных файлах "limits.h" для целочисленных типов и "float.h" для вещественных типов. Для типа int эти константы называются INT_MIN и INT_MAX. INT_MIN = (-2147483647 - 1) INT_MAX = 2147483647 Для вещественных типов максимальное и минимальное числа равны по абсолютной величине и отличаются лишь знаками, поэтому специального названия для максимальной по абсолютной величине отрицательной константы не существует. Максимальное число типа float называется FLT_MAX, типа double - DBL_MAX. FLT_MAX = 3.402823466e+38 DBL_MAX = 1.7976931348623158e+308 Стоит отметить, что через FLT_MIN и DBL_MIN обозначены минимальные положительные числа, а вовсе не максимальные по абсолютной величине отрицательные! FLT_MIN = 1.175494351e-38 DBL_MIN = 2.2250738585072014e-308 Константа DBL_MAX является нормальным числом, она не равна специальному бесконечно большому значению, см. с. 1.4.2. Использовать бесконечно большое значение опасно, т.к. операции с ним могут приводить к ошибкам. Итак, в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать константы INT_MIN и INT_MAX для типа int. Для типа double в качестве значений "минус бесконечность" и "плюс бесконечность" можно использовать выражения (-DBL_MAX) и DBL_MAX. Не забудьте только при программировании на Си подключить стандартные заголовочные файлы: #include для целых типов и #include для вещественных. Впрочем, вовсе не обязательно помнить названия этих констант и имена стандартных заголовочных файлов. В качестве значения "минус бесконечность" всегда можно использовать произвольное значение, заведомо меньшее, чем любое конкретное число, которое может встретиться в программе. Например, если известно, что программа работает только с неотрицательными числами, то в качестве значения "минус бесконечность" можно использовать произвольное отрицательное число, например, минус единицу. Аналогично, в качестве значения "плюс бесконечность" можно применять любое достаточно большое число. Оно должно быть заведомо больше, чем все конкретные числа, которые могут встретиться в алгоритме. Пусть, например, известно, что в программе могут встретиться вещественные числа не больше миллиона. Тогда в качестве значения "плюс бесконечность" можно использовать константу 1.0e+30 т.е. десять в тридцатой степени. (Можно даже использовать 1.0e+7, т.е. десять миллионов, но не стоит мелочиться.) Схема Горнера Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней: p(x) = a0xn +a 1xn-1 + ... + an Нужно вычислить значение многочлена в точке x = t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени: p(x) = ax3+bx2+cx+d Его можно представить в виде p(x) = ((ax+b)x+c)x+d Для вычисления значения многочлена достаточно трех умножений и трех сложений. В общем случае, многочлен представляется в следующем виде: p(x) = (...((a0x+a1)x+a2)x+...+an-1)x+an. Обозначим через pk(x) многочлен k-ой степени, вычисленный по коэффициентам a0, a1, ..., ak: pk(x) = a0xk + a1xk-1 + ... + ak. Тогда pk+1(x) = pk(x)x + ak+1 т.е. при считывании нового коэффициента многочлена надо старое значение многочлена умножить на значение x, а затем прибавить к нему новый коэффициент. Выпишем алгоритм: вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t) | дано: n -- степень многочлена | a[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | i := 0; | цикл пока i <= n | | p := p * t + a[i]; // Вычисление нового значения по | | // старому значению и добавленному коэффициенту | | i := i + 1; | конец цикла | ответ := p; конец алгоритма Арифметический цикл В рассмотренных выше программах в цикле перебираются элементы массива с индексом i, где i пробегает значения от 0 до n-1 (в последней программе - от 0 до n, поскольку многочлен n-й степени имеет n+1 коэффициент). Для удобства записи таких циклов большинство языков программирования предоставляет конструкцию арифметического цикла. В нем используется так называемая переменная цикла, т.е. целочисленная переменная, которая последовательно принимает значения в указанных пределах. Для каждого значения переменной цикла выполняется тело цикла, в котором эта переменная может использоваться. цикл для i от a до b | . . . | тело цикла | . . . конец цикла Здесь переменная цикла i последовательно принимает значения от a до b с шагом 1, где a и b - некоторые целочисленные выражения. Таким образом, всего тело цикла выполняется b-a+1 раз. Если b меньше, чем a, то цикл не выполняется ни разу. Возможна также конструкция арифметического цикла с шагом s, отличным от единицы: цикл для i от a до b шаг s | . . . | тело цикла | . . . конец цикла Переменная цикла последовательно принимает значения a, a+s, a+2s, ... до тех пор, пока ее значение содержится в отрезке [a,b]. Для каждого значения переменной цикла выполняется тело цикла. Шаг может быть и отрицательным, в этом случае b должно быть не больше, чем a, иначе цикл не выполняется ни разу. В принципе, без конструкции арифметического цикла можно обойтись, поскольку ее можно смоделировать с помощью цикла "пока". А именно, конструкция цикл для i от a до b | . . . | тело цикла | . . . конец цикла эквивалентна конструкции i := a цикл пока i <= b | . . . | тело цикла | . . . | i := i + 1 конец цикла Однако традиционно арифметический цикл включается в большинство языков высокого уровня. С использованием арифметического цикла схема Горнера переписывается следующим образом: вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t) | дано: n -- степень многочлена | a[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | цикл для i от 0 до n | | p := p * t + a[i]; // Вычисление нового значения | | // при добавлении коэффициента | конец цикла | ответ := p; конец алгоритма Аналогично можно переписать и другие приведенные выше алгоритмы вычисления функций на последовательностях. Приведем также пример использования арифметического цикла с отрицательным шагом. Пусть коэффициенты многочлена заданы по возрастанию, а не по убыванию степеней. В схеме Горнера следует просматривать коэффициенты многочлена от старшего к младшему. Для этого удобно использовать арифметический цикл с отрицательным шагом: вещ алгоритм схема Горнера2(вх: цел n, вещ b[n+1], вещ t) | дано: n -- степень многочлена | b[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | цикл для i от n до 0 шаг -1 | | p := p * t + b[i]; // Вычисление нового значения | | // при добавлении коэффициента | конец цикла | ответ := p конец алгоритма Индуктивные функции на последовательностях и индуктивные расширения В рассмотренных выше примерах при добавлении к последовательности еще одного элемента новое значение функции на последовательности можно было вычислить, зная только старое значение функции и добавленный элемент. Обозначим через Sn последовательность Sn = {a0, a1, ..., an-1} длины n. С помощью знака & обозначим операцию приписывания нового элемента справа к последовательности (ее называют также конкатенацией): Sn+1 = Sn&an = {a0, a1, ..., an-1, an} Пусть f(S) - некоторая функция на множестве последовательностей, например, сумма элементов последовательности. Функция называется индуктивной, если при добавлении нового элемента к последовательности новое значение функции можно вычислить, зная только старое значение функции и добавленный элемент. На математическом языке функция f:W Y где W - множество всех последовательностей, составленных из элементов некоторого множества X, индуктивна, если существует функция G от двух аргументов G:Y*X Y такая, что для любой последовательности S из W и любого элемента a из X значение функции f на последовательности S, к которой добавлен элемент a, вычисляется с помощью функции G: f(S&a) = G(f(S), a). Функция G по паре (y, a), где y - старое значение функции f на последовательности S и a - элемент, добавленный к последовательности, вычисляет новое значение y, равное значению функции f на новой последовательности. В примере с суммой элементов последовательности функция G равна сумме элементов y и a: G(y, a) = y+a. В примере с максимальным элементом последовательности функция G равна максимуму: G(y, a) = max(y,a). В примере со схемой Горнера вычисления значения многочлена в точке t, где коэффициенты многочлена заданы в последовательности по убыванию степеней, функция G равна G(y, a) = yt+a. Во всех трех случаях рассматриваемая функция на последовательности индуктивна. Общая схема вычисления значения индуктивной функции на последовательности выглядит следующим образом:. алгоритм значение индуктивной функции( вх: последовательность S ) | дано: последовательность S | надо: вычислить функцию y = f(S) начало алгоритма | y := значение функции f на пустой последовательности; | встать в начало последовательности S; | цикл пока в последовательности S есть | | непрочитанные элементы | | прочесть очередной элемент | | последовательности S в (вых:x); | | y := G(y, x); | конец цикла | ответ := y; конец алгоритма Таким образом, для каждой конкретной индуктивной функции надо лишь правильно задать ее значение на пустой последовательности (инициализация) и определить, как новое значение функции вычисляется через старое при добавлении к последовательности очередного элемента, т.е. задать функцию G(y,x). Схема вычисления для всех индуктивных функций одна и та же. Однако не все функции на последовательностях являются индуктивными. Рассмотрим следующий пример. Пусть коэффициенты многочлена заданы в последовательности по убыванию степеней. Надо вычислить значение производной многочлена в точке x = 2. Обозначим через S = {a0, a1, ..., an} последовательность коэффициентов многочлена p(x) = a0xn+a1xn-1+...+an и через f(S) значение производной многочлена p'(x) в точке x =2: f(S) = p'(2) Покажем, что функция f не индуктивна. Достаточно указать две последовательности S1 и S2, такие, что значения функции f на них совпадают, но при добавлении к последовательностям S1 и S2 одного и того же элемента a новые значения функции уже не равны: f(S1) = f(S2), f(S1&a) f(S2&a) Возьмем последовательности S1 = {1}, S2 = {1, -4,1}. Им соответствуют многочлены p1(x) = 1, p2(x) = x2-4x+1 Производные многочленов равны p'(x) = 0, p'2(x)= 2x-4 Значения обеих производных в точке x=2 равны нулю, т.е. f(S1) = p'1(2) = 0, f(S2) = p'2(2) = 2*2-4 = 0 Припишем теперь к обеим последовательностям элемент a = 1: S1&1 = {1,1}, S2&1 = {1, -4,1,1}. Новым последовательностям соответствуют многочлены g1(x) = x+1, g2(x) = x3-4x2+x+1 Их производные равны g1(x) = 1, g2(x) = 3x2-8x+1 Значения производных в точке x=2 равны соответственно f(S1&1) = g'1(2) = 1 f(S2&1) = g'2(2) = 12-16+1 = -3 Мы видим, что значения f(S1) и f(S2) совпадают, но значения f(S1&1) и f(S2&1) не совпадают. Следовательно, функция f не индуктивна. Как поступать в случае, когда функция f не индуктивна? Общий рецепт следующий: надо придумать индуктивную функцию F, такую, что, зная значение F, легко можно вычислить исходную функцию f. Функция F называется индуктивным расширением функции f. Приведем формальные определения. Пусть исходная функция на множестве W всех последовательностей f:W Y не индуктивна. Индуктивная функция F:W Z называется индуктивным расширением функции f, если существует отображение P:Z Y такое, что для всякой последовательности S, принадлежащей W, выполняется равенство f(S) = P(F(S)) (т.е. функция f равна композиции отображений F и P, f = PºF.) Отображение P обычно называют проекцией множества Z на Y. Как построить индуктивное расширение функции f? Это творческий момент, готового рецепта на все случаи не существует. Неформальный рецепт следующий: надо понять, какой информации не хватает для того, чтобы уметь вычислять новое значение функции на последовательности при добавлении к последовательности нового элемента. Эту информацию надо хранить дополнительно к значению функции. Отсюда и появился термин расширение: вычисляется более сложная, расширенная, функция, чтобы по ней затем восстановить исходную. Как правило, значением индуктивного расширения F является пара (y, h), где y - значение исходной функции f, а h - некоторая дополнительная информация, позволяющая перевычислять значение y при добавлении нового элемента к последовательности. Таким образом, множество Z значений индуктивного расширения F:W Z чаще всего является множеством пар (y, h), т.е. декартовым произведением: Z = Y*H Отображение P на практике должно легко вычисляться. Так оно и есть в случае декартово произведения - это просто проекция на первый аргумент. P(y, h) = y Рассмотрим пример с вычислением производной многочлена в точке; коэффициенты многочлена заданы в последовательности по убыванию степеней. При добавлении к последовательности Sk = {a0, a1, ...,ak} нового коэффициента ak+1 получаем последовательность Sk+1 = S&ak+1 = {a0, a1, ...,ak, ak+1} Пусть этим двум последовательностям соответствуют многочлены pk(x) и pk+1(x). Тогда pk+1(x) = pk(x)*x + ak+1. Дифференцируя это равенство, получим: p'k+1(x) = p'k(x)*x + pk(x). Мы видим, что для вычисления нового значения производной нужно знать старое значение производной, а также старое значение многочлена. Следовательно, дополнительно к значению производной многочлена надо хранить еще значение самого многочлена. Таким образом, индуктивным расширением функции, равной производной многочлена в точке t, является пара (значение производной, значение многочлена): F:S (p'(t), p(t)) Новое значение производной вычисляется по приведенной выше формуле через старое значение производной и старое значение многочлена. После этого вычисляется новое значение многочлена по схеме Горнера. Выпишем алгоритм вычисления производной многочлена. вещ алг. значение производной(вх: цел n, вещ a[n+1], вещ t) | дано: n -- степень многочлена | a[n+1] -- массив коэффициентов многочлена по | возрастанию степеней | надо: найти значение производной многочлена в точке t начало алгоритма | вещ p, dp; цел i; | p := 0.0; // Инициализация значения многочлена | dp := 0.0; // Инициализация значения производной | цикл для i от 0 до n | | dp := dp * x + p; // Новое значение производной | | p := p * t + a[i]; // Новое значение многочлена | конец цикла | ответ := dp; конец алгоритма Другой пример неиндуктивной функции - это среднее арифметическое значение элементов последовательности. Индуктивным расширением является пара (сумма элементов последовательности, длина последовательности): F(S) = (сумма(S), длина(S)). Легко видеть, что функция F индуктивна. При известном значении функции F не составляет труда вычислить исходную функцию: среднее арифметическое(S) = сумма(S)/длина(S). В данном случае отображение P не является в чистом виде проекцией, т.к. в процессе вычислений удобнее хранить сумму элементов прочитанного отрезка последовательности, а не среднее арифметическое. Вычисления проще и, кроме того, сумма определена на пустой последовательности в отличие от среднего арифметического. Итак, в каждом конкретном случае при вычислении неиндуктивной функции f надо придумать ее индуктивное расширение F и в программе вычислять сначала индуктивное расширение F, а затем по значению F вычислять требуемое значение исходной функции f. Построение цикла с помощью инварианта Правильное использование конструкции цикла всегда представляет некоторую трудность. Применение элементарной теории помогает избежать ошибок и облегчает написание сложных программ. Основная идея состоит в следующем. В процессе выполнения цикла изменяются значения набора переменных. Надо найти соотношение между меняющимися переменными, которое остается постоянным. Это соотношение называется инвариантом цикла. Сознательное построение цикла "пока" всегда связано с явной формулировкой и использованием инварианта цикла. Явная формулировка инварианта помогает выписать инициализацию переменных, выполняемую до начала цикла, и тело цикла. Инициализация должна обеспечить выполнение инварианта до начала работы цикла. Тело цикла должно быть сконструировано таким образом, чтобы обеспечить сохранение инварианта. (Более точно, из того, что инвариант выполняется до начала исполнения тела цикла, должно следовать выполнение инварианта после окончания тела цикла. В процессе исполнения тела цикла инвариант может нарушаться.) Завершение цикла, как правило, связано с ограниченной величиной, которая монотонно возрастает или монотонно убывает при каждом выполнении тела цикла. Цикл "пока" завершается, когда условие после слова "пока" в заголовке цикла становится ложным. Следовательно, это условие должно прямо или косвенно зависеть от величины, монотонно убывающей или возрастающей в процессе выполнения цикла. По достижению ее определенного значения условие должно становиться ложным. Условием завершения цикла называют отрицание условия, стоящего после слова "пока" в заголовке цикла. Выполнение инварианта цикла и одновременно условия завершения должно обеспечивать решение требуемой задачи. Общая схема Обозначим через X множество всевозможных наборов значений всех переменных, меняющихся в ходе выполнения цикла. Множество X иногда называют фазовым, или конфигурационным, пространством задачи. Инвариант - это некоторое условие I(x), зависящее от точки x из множества X и принимающее значение "истина" или "ложь". (Математики называют такие условия предикатами.) В процессе инициализации точке x присваивается такое значение x0, что условие I(x0) истинно. Обозначим условие завершения цикла через Q(x). Условия I(x) и Q(x) должны быть подобраны таким образом, чтобы одновременная истинность I(x) и Q(x) обеспечивала решение требуемой задачи: нахождение точки x с требуемыми свойствами. Тело цикла можно трактовать как отображение точки x в новую точку T(x) из того же множества X: T:X X Условие I(x) является инвариантом для отображения T: если I(x), то I(T(x)) также истинно. Общая схема построения цикла с помощью инварианта выглядит следующим образом: x := x0; // x0 выбирается так, чтобы условие // I(x0) было истинным утверждение: I(x); цикл пока не Q(x) | инвариант: I(x); | x := T(x); // точка x преобразуется в T(x) конец цикла утверждение: Q(x) и I(x); ответ := x; Конечно, эта схема не имеет никакой ценности без умения применять ее на практике. Рассмотрим несколько важных примеров ее использования. Алгоритм Евклида вычисления наибольшего общего делителя Пусть даны два целых числа m и n, хотя бы одно из которых не равно нулю. Требуется найти их наибольший общий делитель. Напомним, что наибольшим общим делителем двух чисел m и n называется такой их общий делитель d, который делится на любые другие общие делители d'. Такое определение НОД подходит не только для чисел, но и для многочленов, поскольку в нем не используется сравнение по величине. Наибольший общий делитель определен с точностью до обратимого множителя; в частности, поскольку в кольце чисел обратимы только элементы ±1, НОД целых чисел определен с точностью до знака. В качестве пространства X рассматривается множество пар целых чисел X = {(a,b) | a, b Z, a 0 или b 0} Надо вычислить НОД для заданной пары чисел (m,n). В качестве инварианта используем утверждение, что НОД текущей пары чисел равен НОД исходной пары: I(a,b): НОД(a,b) = НОД(m,n). Следовательно, цикл надо строить таким образом, чтобы при изменении переменных a, b наибольший общий делитель пары (a,b) оставался неизменным. В качестве начальной точки x0 используется пара (m,n). Обозначим через r остаток от деления a на b: a = gb+r, где |r| < |b|. Тогда нетрудно доказать, что НОД(b,r) = НОД(a,b). Достаточно показать, что множества общих делителей пары (b,r) и пары (a,b) совпадают. Пусть d делит b и r. Тогда из равенства a = gb+r вытекает, что d делит a. Обратно, пусть d делит a и b. Из определения остатка имеем: r = a-gb. Так как правая часть равенства делится на d, то r тоже делится на d. Итак, при замене пары (a,b) на пару (b,r) НОД не меняется. Обозначим через T отображение T:(a,b) (b,r) Условие I(a,b) является инвариантным для отображения T. Осталось только определить условие завершения цикла Q(a,b). Выполнение этого условия должно обеспечивать решение задачи, т.е. нахождение HOД чисел a, b. Для какой пары чисел их НОД можно сразу вычислить? Проще всего, когда одно из чисел равно нулю. В этом случае НОД(a,0) = a Итак, в качестве условия завершения цикла используем условие, что вторая компонента пары (a, b) нулевая: Q(a,b): b = 0 Теперь можно выписать алгоритм нахождения наибольшего общего делителя: цел алгоритм НОД(вх: цел m, цел n) | дано: целые числа m, n, хотя бы одно отлично от нуля | надо: вычислить наибольший общий делитель пары (m, n) начало алгоритма | цел a, b, r; | // инициализация | a := m; b := n; | утверждение: НОД(a, b) == НОД(m, n); | | цикл пока b != 0 | | инвариант: НОД(a, b) == НОД(m, n) | | r := a % b; // находим остаток от деления a на b | | a := b; b := r; // заменяем пару (a, b) на (b, r) | конец цикла | | утверждение: b == 0 и НОД(a, b) == НОД(m, n); | ответ := a; конец алгоритма Алгоритм Евклида - один из самых замечательных алгоритмов теории чисел и программирования. Работает он исключительно быстро, за время, линейно зависящее от длины записи входных чисел. (Действительно, легко показать, что за два выполнения тела цикла число b уменьшается не менее, чем в четыре раза. Следовательно, число выполнений тела цикла в худшем случае равно длине двоичной записи максимального из чисел a, b.) Это позволяет применять алгоритм Евклида к очень большим целым числам - например, к двухсотзначным десятичным. Алгоритм Евклида (более точно, расширенный алгоритм Евклида, который будет рассмотрен ниже) применяется для таких больших чисел в схеме кодирования с открытым ключом RSA, которая в настоящее время широко используется на практике для защиты информации. Быстрое возведение в степень Второй важнейший алгоритм элементарной теории чисел - это алгоритм быстрого возведения в степень. Наряду с алгоритмом Евклида, он встречается буквально на каждом шагу, когда речь идет о применении теории чисел в программировании, - например, в теории кодирования. Пусть требуется возвести элемент a в целую неотрицательную степень n. В качестве a может фигурировать целое или вещественное число, квадратная матрица, элемент кольца вычетов по модулю m и т.п. - требуется только, чтобы элемент a принадлежал алгебраической структуре, в которой определена ассоциативная операция умножения (т.е. в общем случае, a - элемент полугруппы). Идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения. В качестве фазового пространства X этой задачи рассмотрим множество троек X = {(b,k,p)}. Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла: I(b,k,p): bk*p = an = const, т.е. величина bk*p постоянна и равна an. Легко подобрать начальные значения так, чтобы инвариант выполнялся: b0 = a; k0 = n; p0 = 1. I(b0,k0,p0) = I(a,n,1): an*1 = an Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление an. Действительно, если k = 0, то из инварианта следует, что b0*p = p = an, т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k: Q(b,k,p): k = 0 Осталось написать преобразование T точки x = (b,k,p), которое сохраняет инвариант и одновременно уменьшает k. Определим преобразование T следующим образом: T(b,k,p) = (b*b, k/2, p), если k четное T(b,k,p) = (b, k-1, p*b), если k нечетное Легко видеть, что инвариант сохраняется и k монотонно убывает. Итак, выпишем алгоритм быстрого возведения в степень для случая вещественного основания: вещ алг. быстрое возведение в степень(вх: вещ a, цел n) | дано: основание a и показатель степени n >= 0 | надо: вычислить a в степени n начало алгоритма | вещ b, p; цел k; | | // инициализация | b := a; p := 1.0; k := n; | утверждение: b^k * p == a^n; | | цикл пока k > 0 | | инвариант: b^k * p == a^n; | | если k четное | | | то | | | k := k / 2; | | | b := b * b; | | | иначе | | | k := k - 1; | | | p := p * b; | | конец если | конец цикла | | утверждение: k == 0 и b^k * p == a^n; | ответ := p; конец алгоритма Вычисление логарифма без использования разложения в ряд Схема построения цикла с помощью инварианта позволяет легко написать алгоритм вычисления логарифма заданного числа без использования разложения в ряд. Пусть задано вещественное число x. Требуется вычислить логарифм числа x по основанию a c точностью ε, где ε - некоторое положительное очень маленькое число. Для определенности, пусть a>1 (для a<1 можно воспользоваться тождеством log1/ax = -logax). Из определения логарифма следует, что надо найти число y такое, что ay = x. Нам достаточно, чтобы это равенство выполнялось приближенно. В качестве инварианта используем условие ayzt = x = const. Таким образом, в цикле будут меняться три переменные (y,z,t), и инвариант записывается в виде I(y,z,t): ayzt = x Начальные значения переменных y, z, t выбираются так, чтобы выполнялся инвариант: y0 = 0, z0 = x, t0 = 1. Определим условие завершения цикла Q(y,z,t). Необходимо, чтобы искомая величина по окончанию цикла содержалась в переменной y. Следовательно, величина zt должна быть близка к единице: тогда приблизительно выполняется равенство ay ayzt = x т.е. y приближенно равен искомому логарифму. Для того, чтобы величина zt была близка к единице, нужно, чтобы показатель степени t был близок к нулю, а основание z было не очень велико и не очень мало. Для этого достаточно выполнения трех неравенств |t| < ε, 1/a < z < a Можно доказать строго, что при выполнении этих неравенств, а также условия ayzt = x, величина y отличается от logax не больше чем на ε. Выполнение этих трех неравенств и являются условием завершения цикла: Q(y,z,t): |t| < ε и 1/a < z и z < a Наконец, тело цикла должно преобразовывать переменные (y,z,t) так, чтобы абсолютная величина t монотонно убывала, а переменная z рано или поздно попадала бы в интервал (1/a,a), и при этом сохранялся инвариант. Такое преобразование T легко выписывается по инварианту цикла: T(y,z,t) = (y+t, z/a, t), если z a T(y,z,t) = (y-t, z*a, t), если z 1/a T(y,z,t) = (y, z*z, t/2), если 1/a < z < a Заметим, что при применении преобразования T некоторая величина как бы перетекает из одних переменных в другие, при этом равенство ayzt = x остается неизменным. Теперь можно выписать алгоритм вычисления логарифма: вещ алгоритм логарифм(вх: вещ x, вещ a, вещ eps) | дано: x > 0, a > 1, eps > 0 | надо: вычислить log_a x с точностью eps начало алгоритма | вещ y, z, t; | | // инициализация | y := 0.0; z := x; t := 1.0; | утверждение: a^y * z^t == x; | | цикл пока |t| >= eps или z <= 1.0/a или z >= a | | инвариант: a^y * z^t == x; | | если z >= a | | | то | | | z := z/a; y := y + t; | | иначе если z <= 1.0/a | | | то | | | z := z*a; y := y - t; | | иначе | | | z := z*z; t := t/2.0; | | конец если | конец цикла | | утверждение: |t| < eps и | z > 1.0/a и z < a и | a^y * z^t == x; | ответ := y; конец алгоритма Расширенный алгоритм Евклида Один из важнейших результатов элементарной теории чисел утверждает, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть m и n - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(m,n) выражается в виде d = um+vn, где u и v - некоторые целые числа. Результат этот очень важен для практики, т.к. позволяет вычислить обратный элемент к n в кольце вычетов по модулю m. Действительно, пусть числа m и n взаимно просты, т.е. НОД(m,n) = 1. Тогда 1 = um+vn, откуда следует vn = 1-um vn 1(mod m) Нахождение обратного элемента в кольце вычетов Zm применяется во многих дискретных алгоритмах, например, в схеме кодирования с открытым ключом. Для вычисления наибольшего общего делителя d и одновременно чисел u и v используется так называемый расширенный алгоритм Евклида. В обычном алгоритме Евклида пара чисел (a,b) в цикле заменяется на пару (b,r), где r - остаток от деления a на b, при этом наибольший общий делитель у обеих пар одинаковый. Начальные значения переменных a и b равны m и n соответственно. Алгоритм заканчивается, когда b становится равным нулю, при этом a будет содержать наибольший общий делитель. Идея расширенного алгоритма Евклида заключается в том, что на любом шаге алгоритма хранятся коэффициенты, выражающие текущие числа a и b через исходные числа m и n. При замене пары (a,b) на пару (b,r) эти коэффициенты перевычисляются. Итак, в алгоритме участвуют переменные a, b, u1, v1, u2, v2, для которых выполняется следующий инвариант цикла: I(a, b, u1, v1, u2, v2): НОД(a,b) = НОД(m,n) a = u1m+v1n b = u2m+v2n Начальные значения этих переменных обеспечивают выполнение инварианта: a = m, b = n, u1 = 1, v1 = 0, u2 = 0, v2 = 1. Условием завершения цикла, как и в обычном алгоритме Евклида, является равенство нулю переменной b: Q(a, b, u1, v1, u2, v2): b = 0. Осталось написать тело цикла, сохраняющее инвариант и уменьшающее абсолютную величину переменной b. Это нетрудно сделать, исходя из инварианта цикла. В обычном алгоритме Евклида пара (a,b) заменяется на (b,r), где r - остаток от деления a на b. a = gb+r, |r| < |b|. Здесь g равняется целой части частного от деления a на b. Заметим, что в программировании, в отличие от школьной математики, операция взятия целой части перестановочна с операцией изменения знака: целая часть(-x) = - целая часть(x) Например, целая часть(-3.7) = -3. Это позволяет работать с отрицательными числами так же, как и с положительными, т.е. вообще не следить за знаком! Отметим также, что в большинстве языков программирования считается, что результат любой операции с целыми числами является целым числом, например, 8/3 = 2. Переменная g вычисляется как целая часть частного от деления a на b: g = целая часть (a/b) Выразим остаток r в виде линейной комбинации a и b: r = a-gb Используя инвариант цикла, можно выразить r через исходные числа m и n: r = a-gb = (u1m+v1n)-g(u2m+v2n) = = (u1-gu2)m+(v1-gv2)n. Через u'1, v'1, u'2, v'2 обозначаются новые значения переменных u1, v1, u2, v2. При замене (a,b) (b,r) они вычисляются следующим образом: u'1 = u2, v'1 = v2 u'2 = u1-gu2, v'2 = v1-gv2 По завершению цикла ответ будет находиться в переменных a (НОД исходных чисел m и n), u1, v1 (коэффициенты выражения НОД через m и n). Выпишем алгоритм: алгоритм Расширенный алгоритм Евклида( вх: цел m, цел n, вых: цел d, цел u, цел v ) | дано: целые числа m, n, хотя бы одно отлично от нуля; | надо: вычислить d = НОД(m, n) и найти u, v такие, что | d = u * m + v * n; начало алгоритма | цел a, b, q, r, u1, v1, u2, v2; | цел t; // вспомогательная переменная | // инициализация | a := m; b := n; | u1 := 1; v1 := 0; | u2 := 0; v2 := 1; | утверждение: НОД(a, b) == НОД(m, n) и | a == u1 * m + v1 * n и | b == u2 * m + v2 * n; | | цикл пока b != 0 | | инвариант: НОД(a, b) == НОД(m, n) и | | a == u1 * m + v1 * n и | | b == u2 * m + v2 * n; | | q := a / b; // целая часть частного от деления a на b | | r := a % b; // остаток от деления a на b | | a := b; b := r; // заменяем пару (a, b) на (b, r) | | | | // Вычисляем новые значения переменных u1, u2 | | t := u2; // запоминаем старое значение u2 | | u2 := u1 - q * u2; // вычисляем новое значение u2 | | u1 := t; // новое значение u1 := старое | | // значение u2 | | // Аналогично находим новые значения переменных v1, v2 | | t := v2; | | v2 := v1 - q * v2; | | v1 := t; | конец цикла | | утверждение: b == 0 и | НОД(a, b) == НОД(m, n) и | a == u1 * m + v1 * n; | // Выдаем ответ | d := a; | u := u1; v := v1; конец алгоритма Нахождение корня функции методом деления отрезка пополам Рассмотрим еще один пример использования схемы построения цикла с помощью инварианта, часто встречающийся в реальных программах. Пусть y = f(x) - непрерывная функция от вещественного аргумента, принимающая вещественные значения. Пусть известно, что на заданном отрезке [a,b] она принимает значения разных знаков. Из непрерывности функции f следует, что она имеет по крайней мере один корень на этом отрезке. Требуется вычислить корень функции f с заданной точностью ε. Идея алгоритма состоит в том, чтобы поделить отрезок пополам и выбрать ту половину отрезка, на которой функция принимает значения разных знаков. Эта операция повторяется до тех пор, пока длина отрезка не станет меньше, чем ε. Пусть концы текущего отрезка хранятся в переменных x0, x1. Инвариантом цикла является утверждение о том, что функция принимает значения разных знаков в точках x0, x1: I(x0, x1): f(x0)*f(x1) 0 Начальные значения: x0 = a, x1 = b Условием завершения цикла является утверждение о том, что длина отрезка меньше ε: Q(x0, x1): |x1-x0| < ε (знак модуля используется потому, что в условии задачи не требуется выполнения неравенства a < b). Выпишем алгоритм вычисления корня функции с заданной точностью: вещ корень функции на отрезке(вх: вещ a, вещ b, вещ eps) | дано: f(a) * f(b) <= 0, | eps > 0 - очень маленькое число; | надо: вычислить корень функции f на отрезке [a, b] с | точностью eps; начало алгоритма | вещ x0, x1, c; | | // инициализация | x0 := a; x1 := b; | утверждение: f(x0) * f (x1) <= 0; | | цикл пока |x1 - x0| >= eps | | инвариант: f(x0) * f (x1) <= 0; | | c := (x0 + x1) / 2; // Середина отрезка [x0, x1] | | если f(x0) * f(c) <= 0 | | | то | | | x1 := c | | | иначе | | | утверждение: f(c) * f(x1) <= 0 | | | x0 := c | | конец если | конец цикла | | утверждение: |x1 - x0| < eps и | f(x0) * f (x1) <= 0; | ответ := (x0 + x1) / 2; конец алгоритма Г. |
Похожие:
 | Загирова Румия Ахатовна Дата рождения: 10. 07. 1960 Образование: высшее Учебное заведение После окончания школы, мы остались работать в родном совхозе «Ямбухтинский». Затем, по велению райкома партии, я поступила на экономический... |  | Готов ответить на все Ваши вопросы… Заельцовском районе города Новосибирска. Вырос в неполной необеспеченной семье. После 8-го класса школы №159 поступил в Новосибирский... |
| Реферат Студент 2-го курса(гр. 28) Брюсселе, Вене и Будапеште. После поражения Германии он участвует в подписании капитуляции в качестве эксперта, принимает участие... | | Продукция оксида азота мононуклеарами крови у больных лекарственно-чувствительным... У больных лекарственно-устойчивым тл до и после проведения курса интенсивного лечения секреция no• моноцитами крови снижалась и увеличивалась... |
| Или, что такое эссе и как его написать? Все просто: получено задание от преподавателя как результат окончания очередного полугодия или семестра, как результат окончания... | | Конспект Конспект краткое изложение или краткая запись содержания В помощь подготовке старшеклассников к самообразовательной работе после окончания школы |
| Элективный курс «Устройство автомобиля» Многие учащиеся собираются после окончания 9-го класса получать среднее профессиональное или среднее специальное образование на базе... | | Программа элективного курса «Великие россияне» пояснительная записка ... |
| Весной после окончания учебного года педагоги, управляющий совет... Весной после окончания учебного года педагоги, управляющий совет Горячевской средней школы, возглавляемый Т. Г. Осиповой, представители... | | Конспект воспитательного мероприятия * В помощь подготовке старшеклассников к самообразовательной работе после окончания школы |
| Тематическое планирование по английскому языку для 11 класс Какими качествами надо обладать, чтобы найти достойную работу после окончания школы? | | Протокол №1 от 31. 08. 2012 г «Русский язык и литература» на филологических факультетах педагогических университетов проводится диалектологическая практика. Она... |
| Конспект непосредственно образовательной деятельности В помощь подготовке старшеклассников к самообразовательной работе после окончания школы | | Отчет по педагогической практике в трехдневный срок после окончания... ... |
| Хотеенкова Лариса Давыдовна «Русский язык и литература» на филологических факультетах педагогических университетов проводится диалектологическая практика. Она... | | «Утверждаю» Директор школы Индивидуальные беседы с учащимися 7-9 классов о продолжении обучения после окончания моу всош №1 |
