Сочинения

(Еще не оценили)

Загрузка...

Программирование линейных алгоритмов языком Turbo Pascal 7.0 в операторах присваивания можно записывать имена сменных, которым присвоено значения за предыдущими операторами программы. Значением выражения, что является именем сменной, есть ее значения, присвоенное ей раньше. Например, если в программе сменной z присвоено значения 2, то выражение z+1 задает добавление 2 и 1 и имеет значение 3. При другом значении z выражение z+1 имел бы другое значение. Если это выражение написать, например, в операторе z : =z+l, то оператор задает увеличение значения z на 1, которым бы оно не было (конечно, какое-то значение сменной z надо присвоить перед выполнением этого оператора). Совокупность сменных, имена которых объявлено в программе, называется пам ‘яттю программы а соответствие между именами сменных и их залогами — залогом пам ‘яти программы. Присваивание значения сменной означает изменение залога пам ‘яти программы.

Имя сменной в выражении задает ее значение на момент вычисления выражения. Итак, выражение исчисляется при текущих значениях указанных в нем сменных, т.е. на текущем залоге пам ‘яти.

[smszamok]

Дальше мы рассмотрим другие виды операторов, но все операторы задают изменение залогов пам ‘яти программы. Это изменение и является их семантикой.

Для пересчитываемых типов существует специфическая разновидность оператора присваивания. Он записывается как inc (z) или dec (z), где z — имя сменной пересчитываемого типа. В действительности эти операторы являются вызовами встроенных процедур (о процедурах речь идет в разделе 6). Вызов іпс (z) тождественный оператору z : =succ (z), dec (z) — оператору z: =pred (z).

В первой строке записан заголовок программы; он содержит имя программы и не является обязательным. Тем не менее лучше взять себе за правило всегда его записывать.

Раздел подключения модулей (он тоже не является обязательным) начинается служебным словом uses и содержит перечень имен модулей. Подробнее о модулях речь идет в статье 10, а сейчас дадим сильное краткое объяснение. Программы часто создаются в виде нескольких программных единиц — собственно программы и целого набора модулей, которые в ней используются. Модули сохраняются и транслируются отдельно, а их «машинные» варианты подключаются к программе при компоновании. Чтобы обеспечить подключение нужных модулей, в начале программы указывают их имена.

Объявление имени — это описание того, что обозначает имя в программе. Имя может обозначать некоторое значение или участок памяти, в которой сохраняются значение, атакож другие, более сложные объекты. Конкретные виды объявлений имен будут рассматриваться вместе с уточнением соответствующих понятий (сменных, констант, типов и подпрограмм). Каждое из объявлений заканчивается разделителем «;».

Подпрограмма — это специальным чином оформленная часть программы. Если программа описывает действию из решение некоторой задачи, то подпрограмма описывает действию из решение некоторой части этой задачи.

Каждое имя, которое используется в программе, должны быть объявленным. Некоторые имена объявляются в системе программирования или в других программных единицах.

Описание выполняемых действий вместе с «дужками» begin-end называется телом программы. После тела обязательной есть точка — символ конца программной единицы. Текст программы между ее заголовком и точкой, т.е. объявление и тело, называется блоком. Действия в программе задаются последовательно записанными командами, или операторами. В литературе операторы еще называют указаниями и инструкциями.

Примеры. Кратчайшая программа, которая не задает никаких действий, имеет такой вид:

begin  end.

Как видим, операторы присваивания и другие операторы записываются один за одним и отделяются разделителем «;». Операторы, записанные один за одним, образовывают последовательность операторов. Выполнение операторов программы можно проімітувати, указав последовательность операторов и станів памяти программы, после выполнения операторов. Если в процессе выполнения программы сменная еще не получила значения, будем считать его неопределенным и обозначать как «?». Имитацию программы можно провести с помощью ее пошагового выполнения. Вместо неопределенности начальными значениями сменных будут нули. Тем не менее на это свойство системы программирования полагаться не следует.

Языки программирования, как правило, не имеют специальных операторов для вывода значений из оперативной памяти на внешние носители и введение их из носителей к оперативной памяти. Эти операции осуществляются за специальными подпрограммами {процедурами) введени-вывод. Рассмотрим подпрограммы вывода.       Вывод, или запись, значение выражения на экран задается в виде вызова процедуры writeln (выражение) ,5 Вызов процедуры, в отличие от вызова функции, записывается не в выражении, а как отдельный оператор. При выполнении подпрограммы writeln исчисляется значение выражения и за ним создается соответствующая константа, т.е. последовательность символов. Константа передается устройства, частью которого является экран, и выводится на него. Типом выражения может быть лишь базовый тип.

На экране почти всегда имеющаяся световая пометка, которая мелькает, — курсор. При выполнении подпрограммы вывода константа печатается, начиная из того места на экране, где находится курсор. После вывода с помощью процедуры writeln курсор переходит к следующей строке экрана.

Внутри дужек writeln можно написать несколько выражений через запятую. Они исчисляются один за одним, и соответствующие им константы печатаются подряд в одном строке; курсор передвигается в следующую строку после вывода последней константы.

Например, в результате выполнения операторов За выражением можно написать двоеточие и целую константу, например, х+в: 10. Константа задает так называемую ширину поля вывода, к которому выводятся символы, которые представляют значение выражения. Напомним: имя writeln является сокращением английского write line— записать строку.

Введение данных из внешних носителей к сменным программы задается процедурами введения, или чтение. Вызов одной из них в простейшем случае имеет вид readln (їм’я-змінної). Имя readln является сокращением английского read line — прочитать строку. При выполнении такого вызова компьютер останавливается и ждет, что на клавиатуре будет набрана константа того же типа, что и тип указанной сменной. В ответ следует набрать какую-то константу на клавиатуре (ее будет показано на экране) и нажать на клавишу Enter. Набранная константа после нажатия на Enter передается процедуре, которая за константой создает соответствующее значение и присваивает указанной сменной. Типом сменной может быть лишь базовый тип. Если нажать Enter, не набрав ничего, кроме пропусков, то компьютер и в дальнейшем будет ждать. Перед числовой константой можно набрать произвольное число пропусков (система их игнорирует).

Если вместо нужной константы набрать другие символы (например, недопустимую константу или вместо числовой константы символьную), то выиздыхание программы на этом будет завершено (аварийно) и на экране появится сообщение о том, что входные символы были неправильными. Пусть, например, имя z обозначает сменную типа integer. Если при выполнении readln (z) набрать 1024, то после нажатия на Enter значением z станет 1024. Если же набрать 50.9 или z=1024, программу будет аварийно завершено, поскольку число 50.9 не подается в типе integer и целая константа не может начинаться символами «z=». Если же набрать целое число, которое выходит за пределы типа, например, 50000000, результат зависит от установленных директив компиляции и может быть целиком неожидаемым.

[/smszamok]

В вызове процедуры чтения можно написать несколько имен сменных, отделив их запятыми. При выполнении этого вызова надо набрать соответствующее количество констант, отделив их пропусками или нажатиями на Enter в произвольном количестве. Пока все константы не будет набрано, выполнение вызова не заканчивается. Пусть, например, х: integer, в: real. При выполнении readln (х, у) ; следует набрать целую константу, прибавить хотя бы один пропуск или нажатия на Enter, а потом набрать любую целую или действительную константу (между целой и дробовой частью набрать десятичную точку) и нажать на Enter.

Практически перед каждым вызовом процедуры чтения из клавиатуры следует записать вызов процедуры вывода с приглашением к введению значений и указанием, сколько и каких типов. Например, указать вывод приглашения writeln(‘Температура (целое число)>’), а потом вызов readln (tCel s) ;. Процедура readln задает чтение не только из клавиатуры, но и из других внешних носителей, например, с диску.

(Еще не оценили)

Загрузка...

Для представления действительных чисел используют четыре типа: single, real, double, extended.  Тип real есть стандартным (доступным для использования независимо от установленного режима компиляции). Чтобы использовать другие действительные типы, надо установить специальный режим компиляции с помощью меню системы программирования или директивы компилятора.

Действительные числа обозначаются действительными константами. Рассмотрим пример. Число 1,2345 можно обозначить несколькими способами, например, -2

123,45 • 10 .В этой записи оно имеет целую часть «123», дробовую часть «,45» и десятичный порядок «-2». Записи отвечает константа языка Паскаль 123.45Э-2, в которой 123 — целая часть, .45 — дробовая, а Е-2 — порядок. Это самое число можно представить также константами 0 .12345Э1, 0 . 012345Э+2,1. 2345,12345е-04 и другими.

[smszamok]

Действительные константы имеют обязательную целую часть, за которой записана дробовая часть и порядок (возможно, одно из них). Целая часть — это непустая последовательность цифр, дробовая — последовательность цифр, возможно, пустая, с точкой в начале, а порядок — латинская буква Е или есть с одной или несколькими цифрами, возможно, со знаком + или -. Перед константой может стоять знак -, и тогда она задает отрицательное число: -12.345Э-1.

Представление действительного числа константой, в которой целая часть содержит одну цифру от 1 до 9, называется нормализованным, например, 9.81 или 1.0Е2 (для числа 0 таким есть 0.0).

Множество чисел, которые можно представить в действительных типах, уточняется за представленной выше таблицей. За любого действительного типа она есть скінченною ограниченным подмножеством множества рациональных чисел и содержит все целые числа, которые представлено в типе longint (тип single содержит не все, но содержит носитель типа integer). Разность между двумя «соседними» действительными числами изменяется в их диапазоне, для больших чисел достигая порядка 104.

Операции. К действительным значениям применяют те же арифметические операции, что и к целым, за исключением odd, div, mod, а также succ, pred, ord. Результатом этих операций всегда есть действительное число. Сравнение действительных чисел, как и целых, имеет соответствующий булів результат: результатом 1.0<=2.5 есть значения true, 1.0=0.99 — значение false.

Действительные типы є «машинными представителями» множества действительных чисел, которая есть всюду плотной (между произвольными двумя действительными числами существует множество других действительных). Пронумеровать эти числа невозможно, поэтому действительные типы не являются пересчитываемыми.

Для действительные типы обозначены так называемые встроенные математические функции. Действительное значение | х \, arctg х, cos х, ех, In х, sin х, х2, -Jx возвращает из вызова функции, имя которой, соответственно,

abs,   arctan,   cos,   exp,   In,   sin,   sqr,   sqrt.

Все эти функции применяются и к числам целых типов (но лишь abs и sqr в этом случае порождают значение целого типа). Значение аргумента в вызовах функций cos и sin выражает количество радиан, а не градусов. Обозначено также нульмісну функцию Рі (ее значение являются приближением к числу 71 = 3,14159265358979 ).Например, cos (Pi/2) =0.0,sin(Pi/2) =1.0.

Понятие сменной числовой величины впервые появилось в роботах Карта-где-карта в XVII ст. Позднее оказалось, что переменная величина может быть не только числовой. В широчайшем понимании переменная величина — это обобщение, абстракция какого-то реального или мысленного объекта (или его отдельной характеристики), который может находиться в разных залогах. Переменные величины задают именами, например, в записи второго закона Ньютона а = F/m имена т, a, F обозначают переменные величины — массу тела, ускорение его движения и силу, которая действует на него.

В программировании сменная также является представителем объекта или йогол*»-деллю в программе. Она представляет его в памяти компьютера, поэтому сменная в программировании — это участок памяти, которая своими залогами представляет залоги объекта.

В языках высокого уровня сменные обозначаются именами, или идентификаторами.’ Имена можно выбирать любые, кроме служебных слов. Например, ABRACADABRA, temperature, number, f 123qqToiu.o. Напомним: большие и малые буквы в именах рассматриваются как одинаковые.

Например, var even : boolean;. Ключевое слово var является сокращением английского variable — сменная. Несколько однотипных сменных можно объявить вместе, указав их имена через запятую.

var tCels, tKelv : integer;

Тип сменной задает множество ее возможных значений (что зависит от длины участка памяти, которую занимает сменная) и операций, которые можно применить к ней.

Каждый участок памяти компьютера имеет адрес, которым участок обозначается в машинной программе. Имя сменной в Паскаль-програмі в результате трансляции превращается в адресу некоторого участка памяти. При выполнении программы этот участок и есть сменной, имя которой записано в программе. Имя сменной указывает или ссылается на участок памяти во время выполнения программы (рис. 1). Как видим, сменная (участок памяти) и ее обозначение (имя) — это разные понятия.

Способы, которыми сменным предоставляются значение, будет описано ниже, а в следующем параграфе будем использовать имена сменных в выражениях, считая, что они имеют значение (неважно, которые именно).Применение операций к числовым и другим значениям, в результате которого образовывается новое значение, в языках программирования высокого уровня задается с помощью выражения.

Простейшие выражения — это константы и имена сменных базовых типов.

Более сложное выражение образовывается с более простых как:

•          выражение в дужках;

•          два выражений и знак двухместной операции между ними;

•          выражение со знаком одноместной операции перед ним;

•          вызов функции с выражением в дужках.

Примеры: ((1)), true and false, 1-(2+3) , (1-2)+3, (l+2)<>3,   -(5+3),   odd(2),   ord(odd(15)).

Программирование линейных алгоритмов языком Turbo Pascal 7.0

Значение, к которому применяется бперація, называется ее операн-дом. Операнди обозначаются выражениями. Последовательность применения операций к операндів образовывает процесс вычисления выражения, результатом которого являются значения выражения. Тип значения выражения называется типом выражения.

Как видим, выражение имеет двойное содержание {семантику): задает процесс вычисления и имеет значение определенного типа.

Примеры. Выражение 2*2 = 5 задает процесс, в котором:

1)         исчисляется произведение 2*2 и возникает целое значение 4;

2)         сравниваются целые значения 4 и 5 и возникает значение false, которое является значением этого выражения; его тип —boolean.

Пусть a, b, с — имена числовых сменных, которые представляют коэффициенты квадратного уравнения ах +bx + c = 0. При вычислении выражения b *b-4*а*с>0 сначала исчисляется квадрат значения змінноїЬ, потом произведение числа 4 и значений сменных а и с, потом разность двух полученных произведений. Эта разность сравнивается с нулем, и булів результат этого сравнения (значение true или false) является значением всего выражения. Итак, это выражение задает вычисление признака того, что указанное уравнение имеет именно два корня.

Предположим, что с — имя символьной сменной, значением которой может быть один из символов ‘0’, ‘ 1’,…, ‘9’, т.е. десятичная цифра. Выражение ord (с) -ord (‘ 0 ‘) задает вычисление порядковых номеров значения сменной с и символа ‘ 0 ‘. Потом исчисляется разность этих номеров — целое число от 0 до 9, т.е. числовое значение цифры. В

Язык Turbo Pascal, в основном, отвечает соглашениям математики о порядке применения операций в выражениях. Это разрешает не записывать лишние дужки, например, 1-2*3 означает то самое, что и 1- (2*3). На порядок применения операций при отсутствии дужек влияет их старшинство, или приоритет.

Если рядом с обозначением операнда записаны знаки двух операций, то сначала выполняется старшая из них (с высшим приоритетом).

В таблице, представленной ниже, все операции разбиты на четыре группы, расположенные в порядке спадания приоритета (некоторые операции обозначены в дальнейших главах). Операции внутри каждой группы имеют одинаковые приоритеты. Например, выражение 1+ (3+2) *2 задает, что после вычисления 3+2, т.е. значение 5, оно множится на 2, а не прибавляется до 1.

[/smszamok]

Кроме приоритетов, операции имеют свойства право- или левостороннего связывания. В языке Turbo Pascal все двухместные операции имеют свойство левостороннего связывания: связывается с операцией, указанной по левую сторону (эта операция применяется сначала). Например, 1-2*4+3 задаете именно, что и (1-2*4) +3, но не то, что 1-(2*4+3).

В системе программирования Turbo Pascal применяется так называемое ленивое, или сокращенное, вычисление булевих операций and и or. Сначала исчисляется их первый операнд. Если для операции and это false, то второй операнд не исчисляется, поскольку результатом все одно будет false. Аналогично, если первый операнд операции or есть true, то второй операнд не нужный. Например, выражение (2*2 = 5) and 323345 div 17 = 0) задает вычисление лишь 2*2=5, а (2*2=4) or (323345 div 17 = 0) — лишь 2*2=4. Полностью булеві выражения исчисляются в специальном режиме компиляции (см. дополнения А і В).

(1голосов, средний: 5,00 out of 5)

Загрузка...

Изучение любого языка начинается из изучение алфавита — конечного множества символов, разрешенных для использования. Алфавит языка Turbo Pascal содержит:

•          буквы {буквы) — большие и малые латинские А, В, … ,Z,a,b,…, z, а также символ подчеркивания _;

•          десятичные цифры 0,1,2,…,9;

•          специальные символы + -*/=><.,;:'()[]{} * @  $ #.

Из символов алфавита образовываются «слова» языка -лексемы (единицы). Это последовательности символов, которые рассматриваются как неделимые и сами по себе имеют некоторое содержание.

В языке Turbo Pascal есть четыре вида лексем:

•          константы;

•          имена;

•          знаки операций;

•          разделители.

Кроме них, в программах записывают еще комментарии и директивы компилятора.

Константа — это обозначение значения (числового или другого типа). Числовые константы имеют обычный для нас вид, например, 273,3.1415926, 2.71828, лишь обособление целой части от дробовой задается точкой, а не запятой. Булеві константы false и true обозначают то, о чем мы привыкли говорить, соответственно, «ошибочность» и «истина».

[smszamok]

Существуют также текстовые константы — последовательности любых ASCII-символов, ограниченных апострофами, например, ‘ Лицей’, ‘ 3.1415926’, ‘ -273’.

им ‘я — это последовательность букв алфавита и цифр, которые начинаются из буквы, например, A, xl, _1_2, jklmn. Большие и малые буквы в именах не различаются: Nam, nAM, nam — это одно и то самое имя. Имена могут иметь произвольную длину, но к вниманию берутся лишь первые 63 символа.

Имя всегда именует какой-либо объект; оно выделяет его из других, т.е. идентифицирует, поэтому имя еще называют идентификатором.

Некоторые имена (это английские слова или их сокращение) обозначают определенные составные части программы, например, program, const, var, begin, end. Они называются зарезервированными, ключевыми или служебными словами. Существуют также стандартные слова, например, integer, write, readln, sin, Pi и т.п., которые имеют определенное содержание, но его по желанию программиста можно изменить.

Автор программы также сам создает и использует користувацькі имена, обозначая за их помощью определенные объекты программы.

Знак операции — это обозначение операции, выполнение которой над числами и другими значениями порождает новое значение. Значение, к которым применяется операция, называются ее операндами, а порождаемое значение -результатом. Знаки операций записывают как отдельными символами, например + или -, так и именами или последовательностями других символов, например div или <=. Множество знаков уточняется в параграфах 5-9.

Разделителями являются дужки ( ) [ ], разделительные знаки , ; . : и пропуск. Ими отделяются лексемы и прочие, более сложные, элементы программы.

Комментарий — это вспомогательное объяснение, которое имеет целью помогать человеку понять программу, не задает никаких действий и при трансляции пропускается. Комментарий — это «почти» произвольная последовательность символов, которая начинается символом {и заканчивается ближайшим }, т.е. не содержит } внутри. «Почти» означает, что сразу за дужкой { не может быть символа $ (тогда это не комментарий, а так называемая директива компилятору). Вместо дужек { и } можно записывать пары символов (* и *). Например,

{ это комментарий }  (* это тоже *)  (и это }

а это уже не комментарий, а непонятно что}

Комментарии можно записывать между любыми в двух словах, тем не менее лучше располагать их по правую сторону от текста программы или в отдельных строках.

Директивы компилятора — это записи, которые задают те или другие режимы

компиляции программы и могут существенно влиять на содержание машинной программы. Как и комментарии, директивы записываются в дужках {}, однако сразу за дужкой { должны идти символ $. Конкретный вид и содержание некоторых директив будет рассмотрено ниже.

Сопредельные имена и константы отделяются так называемыми пустыми символами — символами, которые не имеют изображения и появляются в тексте программы, если при его создании нажимать клавиши Space (пропуск), Enter («конец строки») и Tab (символ табуляцїі). Пустые символы называются пропусками. Пропуск между соседними лексемами не обязательный, если хотя бы одна из них является разделителем, комментарием или знаком операции (но не именем). Например, знаки + или <= не являются именами, a div — есть. Поэтому 1+2, 1 div-2 или 1<=2 написать можно, a ldiv2 — ни (надо 1 div 2).

Программы обрабатывают данные в виде чисел, символов и других значений. Значения имеют определенное представление в компьютере и к значениям применяют некоторые операции. За способом представления и допустимыми операциями значения (данные) делятся на типы. Понятие типа данных есть одним из фундаментальных в программировании.

Тип данных — это множество значений (данных) вместе с множеством операций, примененных к этим данным. Множество значений называется носителем типа, а множество операций — сигнатурой.

В языках программирования используются числовые, символьные и бу-леві значения. Они рассматриваются как целостные элементы, которые не имеют отдельных составных частей, поэтому называются скалярными в отличие от структурных, составленных из отдельных компонентов. Типы скалярных данных называются скалярными.

Практически каждый язык программирования обеспечивает целое семейство скалярных типов. Они называются базовыми типами языка. Имена базовых типов можно употреблять, не объявляя в программе (они являются стандартными). Кроме того, языки имеют специальные конструкции для объявления собственных скалярных и структурных типов.

В базовых скалярных типах языка Turbo Pascal есть целые и действительные числа, булеві значение «истина» и «ошибочность», атакож символы.

Любой тип, базовый или созданный программистом, имеет свое имя и характеризуется множеством значений и набором возможных операций. Для представления целых чисел язык Turbo Pascal предоставляет пять типов:

Имя типа        Длина, байт   Диапазон значений

byte     1          0..255

word    2          0..65535

shortint 1          -128..127

integer  2          -32768..32767

longint  4          -2147483648..2147483647

Чему у целых типов такие диапазоны значений, висвітлено в разделе 1. Целая константа — это, как и в математике, последовательность десятичных цифр, возможно, со знаком «+» или «-» впереди: 0, +1024, -273 и т.п.. Диапазоны возможных констант разных целые типы приведены в таблице. Для наибольшего целого числа типа integer выделено имя maxint (типа longint — именем maxlongint). Более всего за модулем отрицательное число типа integer можно задать выражением -maxint-1.

Все целые типы имеют одинаковые наборы операций. Рассмотрим сигнатуру операций на примере типа integer.

Основные арифметические операции с целыми числами (добавление, отнимание, умножение, вычисление частицы и остатка от деления націло, а также деление) обозначают знаками. Большинство операций являются двухместными. Знак «-» задает применение как двухместной операции отнимания, так и одноместной операции «минус»: -32768, -(2+3). Знак <<+» также может задавать как двухместную, так и одноместную операцию.

Арифметические операции с целыми числами

Знак    Примеры применения и результаты

+          1+2  =  3

—          1-2  =  -1

—   (одноместный)     -(1)   =  -1

*          2*2   =  4

div       7  div 3  =  2,   -7  div 3   =  -2, 7  div -3  *  -2,   -7  div  -3=2

mod     7  mod 3   =  1,   -7 mod 3   m  -1, 7 mod -3  =  1,   -7 mod -3  = -1

/           7/3 = 2.3333333    (действительное), 6/3 =2.0   (действительное)

Булив тип имеет два логических (булевих) значение «ошибочность» и «истина», которые задано константами false (ошибочность) и true (истина). Этот тип имеет имя boolean в честь выдающегося англичанина Джорджа Буля, основателя математической логики.

К булевих значений применяют логические операции «и», «или», «не», которые называют, соответственно, булевим умножением (кон ‘юнкцією), булевим добавлением (диз ‘юнкцією) и возражением и обозначают как and, or и not. Еще одна операция называется «исключительное или» или «добавление за модулем 2» и обозначается знаком хог. Результаты применения этих операций к булевих значения приведены в таблице:

А         В         A and В           A or В А хог В           not A

false     false     false     false     false     true

false     true      false     true      true      true

true      false     false     true      true      false

true      true      true      true      false     false

Кроме булевих, есть еще операция «порядковый номер» ord: ord (false) = 0, ord (true) = 1. Порядковым номерам булевих значений отвечает результат их сравнения: false < true. Очевидным путем обозначено все другие сравнения =, ОБ, >, <=, >=.

Булеве значения представляется его номером в одном байте, т.е. Sizeof(boolean)=1.

Тип символов {буквенный тип) имеет имя char. В нем 256 значений, которые представляются в одном байте. Заметим, что в относительно новых языках программирования, например Java, символы занимают два байта, поэтому их количество — 65536.

Символ обозначается символьной константой, т.е. символом в апострофах: ‘А’, Ч’, ‘ . ‘ и т.п.. Сам символ «апостроф» задается символьной константой ‘ ‘ ‘ ‘ .Подчеркнем: символьная константа — это не символ, а его обозначение в языке программирования.

Символам взаимно однозначно отвечают номера от 0 до 25 5. Любое символьное значение можно задать выражением chr (и), где и имеет значение от 0 до 255, т.е. номер. Например, chr (48) обозначает то же, что и константа ‘ 0’, chr (48+1) — то же, что ‘ 1’, chr (65) является синонимом константы ‘ А’, chr (97) — ‘а’. Запись вида #і обозначает то же, что и chr (и); например, #48 = chr (48).

Соответствие символов и номеров от 0 до 127 зафиксировано в Американском стандартном коде для обмена информацией (ASCII), а номерам от 128 до 256 могут отвечать разные наборы символов.

Рассмотрим операции с символами. Целый номер символа порождается вызовом функции «порядковый номер», т.е. выражением ord (с), где значением с есть символ. Например, ord(‘ 0’) = 48, ord(‘ А1) = 65, ord (‘а’) =97.

За определением, функции chr и ord взаимно обратные, т.е. chr (ord (с)) = с за любого символа с, a ord (chr (n)) = п за любого п от 0 до 255.

Для символы обозначены все сравнения, причем символы упорядочены так же, как и соответствующие им номера. В частности, исполняются такие неровности. ‘ ‘ < ‘_’ < ‘0’ < Ч’ < … < ‘9’ < ‘А’ < ‘В’ < … <   ‘Z’   <   ‘а’   <   ‘Ь’   < … <   ‘z’

[/smszamok]

Результатом операции конкатенации (дописывание) со знаком «+» есть последовательность с двух символов, или строка. Например, ‘ 1′ +’ 2′ — это последовательность символов, которую можно задать также выражением 42 и.

Каждый элемент типа boolean, char или целое число, кроме наибольшего в своем типе, имеет элемент, следующий за ним, и каждый, кроме наименьшего, — предыдущий перед ним. Например, следующим за false есть true, за chr (0) —chr (1), за chr (254) —chr (255), а предыдущим перед true есть false. Кроме того, элементы этих типов можно пронумеровать последовательными целыми числами.

В языке Паскаль пересчитываемым называется тип, в котором обозначена операции succ (следующий), pred (предыдущий) и ord (порядковый номер). Пересчитываемые типы также называются дискретными.

Операции succ, pred, ord задают в виде вызовов встроенных функций: выражения pred (1), succ (‘ а’) и ord (true) имеют значение, соответственно, 0,’ b’ и 1. Для знаковых числовых типов операцию ord обозначено так, что ord (и) = и, т.е. ord (0) =0,ord(-l) = -1. Во всех пересчитываемых типах обозначено также сравнение =, ОБ, <, >, <=, >=.

Результат применения succ к наибольшему элементу типа и pred к наименьшему зависит от налаживания компилятора.

(Еще не оценили)

Загрузка...

Как уже отмечалось, восемь последовательных бит образовывают байт, который может иметь 256 разных залогов (комбинаций с 0 и 1). им можно поставить во взаимно однозначное соответствие целые числа от 0 до 255, целые числа от-128 до 127, 16-пары цифр или элементы какой-то 256-другого элементного множества.

Целые числа подаются в компьютере преимущественно в двух формах — без-знаковой и знаковой. Эти формы называются кодами. Дальше числа отождествляются с их представлением, хотя с точки зрения математики это есть ошибочным.

Беззнаковые коды занимают несколько байтов (чаще всего, 1,2,4 или 8). Байты нумеруются, начиная с 0. Биты внутри байтов нумеруются от 0 до 7. N байтов содержат 8N бит, поэтому используют также сквозную нумерацию бит — от 0 до 8N-1 (от младших до старших). Все возможные последовательности бит представляют числа от 0 до 2^8лм . Соответствие между кодами и числами при разных значениях представлено в такой таблице 3.

Знаковые коды также занимают 1,2,4 или 8 байт. Старший бит представляет знак числа: 0 — «+», 1 — «-».числа представляются так же, как и беззнаку, лишь за счет знакового бита их диапазон — от 0 до 2^8ЛМ -1. Такое представление называется прямым кодом. Например, число 2^8ЛМ -1 имеет прямой код 011… 1.

Отрицательные числа представлены так называемым дополнительным кодом. Код отрицательного числа А обозначается D (А) и образовывается так.

1.  За прямым кодом числа |А| заменой всех 0 на 1 и всех 1 на 0 строим обратный код R{A) .

2.  За К(А) как беззнаковым целым числом вычисляем код Г>(А) = Я(А)+1.

Пример. Построим двобайтовий дополнительный код числа -144.

«Восстановить» за дополнительным кодом от’ емкое число можно в возвратном порядке.

1.     D(A)   рассматриваем  как беззнаковое целое и обчис­
 люємо R (А)   = D (А) -1.

2.    Код,  обратный к R(A) ,  является прямым кодом числа  |А|.
Тем не менее можно обойтись без отнимания. Очевидно, что D(A) = ЩА\ -1),

т.е., например, дополнительный код числа-144 вместе с тем является обратным кодом числа -143. Тогда код R(_D{A)) является прямым кодом числа \А \ — 1. Тогда прямой код \А\ можно получить так.:

1. 1.       Строим код K(D(A)) ,   обратный к  D(A) .
2. 2.       К R(D(A))   как беззнахового целого прибавляем  1. 

Таблица 4

Как видим, отрицательных чисел на одно больше, чем додатних.

Некоторые особенности представления действительных числа здесь опущены, чтобы не загромаджувати изложения.

Для действительных чисел чаще всего используют 4,6,8 или 10 байт, разделенных на поля (последовательности бит) <знак><порядокХмантиса>. Эти поля означают такое.

Поле <знак> имеет длину 1 бит, его значение 0 представляет знак «+», 1 — знак «-». Поле <порядок> в некоторый специальный способ задает показатель степени числа 2 (он может быть как додатним, так и отрицательным). Поле <ман-тиса> означает дробовую часть — неотъемлемое число строго меньше 1.

Поля представляют число в такой способ. Мантисса прибавляется до 1, сумма множится на степень числа 2, заданный порядком, и учитывается знак. Итак, число является значением выражения вида:

±(\+дробовая часть)*!»»™³‘»»‘.

Сумма в этом выражении не меньше 1 и строго меньше 2\ поэтому говорят, что это представление числа есть нормализованным.

Действительные числа в описанном представлении образовывают ограниченное подмножество множества рациональных чисел; в частности, среди них есть число, меньше всего за модулем и отличное от 0, а также число, более всего за модулем.

ЗАДАЧИ

1. Запишите число как сумму степеней основы системы исчисления с:

а) 5768;           Ь) 842,413;            с) 12,223;       d)A09,7F16.

1. Переведите десятичное число в римскую систему записи: а) 55;         Ь)995;    с) 1547.
2. Переведите римскую запись чисел в арабский (позиционный десятичный): a)LX;   b)CXI;   c)MDCCCXH;    d)MCMLXI.

4.  Запишите число как сумму степеней основы системы исчисления с и определите десятичную запись числа:

а) 2,336;           Ь) 291,40615;      с) 245,5678;    сии)Л09,С3513;

(Еще не оценили)

Загрузка...

Добавление одноцифровых чисел ученики изучают с помощью таблиц, в которых представлены результаты добавления чисел от 1 до 9, например, 7 + 8 = 15, 9+1 = 10,9+9 =18. Аналогичные таблицы добавления нетрудно составить для любой системы исчисления.

Пример. Для  системы с цифрами 0,1,2,3,4,5 и 6 таблица 1 добавление имеет такой вид.

Таблица 1

Таблица демонстрирует переставной закон добавления — заполнив строку таблицы, можно сразу получить соответствующий столбик.

Если сумма чисел не менее чем 7, образовывается двоцифрова сумма, т.е. появляется перенос 1 к старшему разряду. Так же в десятичной системе перенос появляется, если сумма не меньше чем 10.

В системах с основой больше 10 нужны цифры А, В, Стощо. Например, два последние строки таблицы добавления одноразрядных чисел с основой 16 имеют такой вид:

При добавлении одноцифровых чисел А и В у любой  системе значением цифры является остаток от деления (А+В) нар, переносом к старшему разряду — частица от деления (А+В) на Р. Если А+В < Р, перенос равняется 0 («переноса нет»),  А+В £ Р, он равняется 1.

Приведенное правило дает основу для алгоритма добавления чисел в столбик в произвольной  системе.

Начиная от младшего разряда, цифры и перенос от предыдущего разряда прибавляются, в разряде остается остаток от деления суммы на Р, а частица является переносом к следующему разряду. Перенос в младший разряд равняется 0.

УМНОЖЕНИЕ

Умножение в недесятичных системах исчисления выполняется также с помощью соответствующих таблиц. Рассмотрим, например, таблицу умножения одноразрядных чисел с основами 2,3 и 4.

Таблицы демонстрируют переставной закон умножения — заполнив строку таблицы, можно сразу получить соответствующую колонку.

Приведем также восемь последних строк таблицы 2 умножение с основой 16.

При умножении одноцифровых чисел А и В у любой системе значением цифры является остаток от деления АхВнаР, переносом к старшему разряду — частица от деления А х В на Р. За А х В < Р перенос равняется 0.

Приведенное правило дает основу для алгоритма умножения кількарозряд-ного числа на одноразрядное число Ху столбик.

Начиная из младшего разряда, исчисляется произведение Y значение цифры числа и X. К Y прибавляется перенос от предыдущего разряда и получается сумма 5. Остаток от деления S на Р у Р-ковому представлении записывается в результат, а частица является переносом к следующему разряду.

Пример. Помножим числа соответственно в системах; в дужках вверху запишем переносы.

(ПО)                             (1220)                               (8/Л0)

_х212                                _х123                                ₊ 8£2

2                                  З                                     F

1201                               1101                                853£

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

• Во всех приведенных примерах мы никогда не смешивали записи чисел в системах с разными основами. Если число записано в разных системах исчисления, то выполнять действия с ними или сравнивать их нельзя.

(Еще не оценили)

Загрузка...

Разумеется, в этой статье мы не будем использовать сложный математический инструментарий. Те немногие понятия математики, к которым мы прибегнем, можно будет рассматривать просто как занимательные картинки. Одно из таких понятий — функция. Для читателей, не использующих в своей работе математический аппарат, этот термин мгновенно ассоциируется с картинкой, на которой начертаны две оси координат и какая-то линия — график некоторой функции. В общем, это представление верно. Однако здесь нелишне его уточнить. Математики называют еловом «функция» любой закон соответствия между переменными величинами, когда одной мз них (ее называют независимой переменной, или аргументом функции, и обозначают х) ставится в соответствие другая (ее называют зависимой переменной, или значением функции, и обозначают у).

Возьмем какое-либо значение аргумента и отложим его на горизонтальной оси координат. Возьмем затем значение функции, соответствующее этому аргументу, и отложим на вертикальной оси. Отметим на координатной плоскости точку с такими координатами. Беря все новые значения аргумента и нанося на координатную плоскость все новые точки, мы получим некоторый график — наглядный образ функции, закона соответствия между независимой   и  зависимой  переменными. График функции может содержать особые точки. Бывает, что кривая сначала опускается, а затем поднимается. Участки спада и нарастания стыкуются в точке минимума. Бывает и наоборот: кривая сначала поднимается, а затем опускается. Точка стыка восходящего и нисходящего участков называется точкой максимума. Бывает, что кривая изгибается сначала в одну сторону, а потом в Другую; там, где она сменяет направление поворота, находится точка перегиба.

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

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

Но в математике рассматриваются и такие функции, у которых не один аргумент, а несколько, скажем, два, Здесь уже две оси координат нужны для того, чтобы откладывать на них аргументы. Каждой паре аргументов в этом случае ставится в соответствие определенное значение функции.

Ради наглядности две эти оси координат дополняют третьей и на ней откладывают значение функции. Три координаты (два аргумента да еще значение функции) определяют точку в пространстве. Перебирая все возможные сочетания аргументов и расставляя точки в пространстве, мы получим некоторую поверхность — наглядный образ функции  двух  переменных. На таких поверхностях тоже могут встретиться особые точки — точки минимума, максимума, бесконечного разрыва. Приведенные иллюстрации поясняют эти термины.

(Еще не оценили)

Загрузка...

Параметр-значение сообщает подпрограмме «собственную» сменную. В начале выполнения вызова подпрограммы этой сменной присваивается значение аргумента. Соответствующим аргументом может быть произвольное выражение того же типа, что и тип параметра (или типа, совместного за присваиванием с типом параметра).

Примеры аргументов, которые є выражениями, нам знакомые из вызовов стандартных подпрограмм: sqrt(b*b-4*a*c) , chr (ord ( ‘ 0 ‘ ) +1) , writeln (x*x) и т.п..

В вызовах нашей процедуры min первые два аргументы тоже могут быть произвольными выражениями типа integer, например min (10+х,3*х,v), где х, v — имена целых сменных.

Этот способ передачи данных в подпрограмму называется подстановкой аргумента на место параметра по значению.

ПОДСТАНОВКА ЗА ССЫЛКОЙ

Параметр-сменная во время выполнения подпрограммы обозначает одну и ту же сменную, которую обозначает соответствующий ему аргумент, указанный в вызове. Чтобы обеспечить это, к памяти подпрограммы передается ссылка на эту сменную. Соответствующим аргументом может быть ім ‘я ЗМІННОЇТОГО же типа, что и у параметра.

Примеры аргументов, которые отвечают параметрам параметр-сменным: readln(a,b,c) или іпс(х), а также третий аргумент в вызовах нашей процедуры min.

Этот способ передач данных в подпрограмму называется подстановкой аргумента на место параметра за ссылкой.

ЧТО ВЫБИРАТЬ?

Если после вызова подпрограммы используется старое значение аргумента или аргументом может быть произвольное выражение, ему имеет відпо-;»;Яати параметр-значение.

Вспомогательные алгоритмы, или подпрограммы

Если после вызова подпрограммы должны использоваться новое значение аргумента, полученное при выполнении вызова, то параметр надо объявить как параметр-тінну.

Первое правило имеет исключения, связанные с массивами (см. раздел 7). Параметры х и у процедуры min (см. выше) иллюстрируют первое правило, параметр z — второе.

ПАРАМЕТРА-КОНСТАНТЫ

В языке Turbo Pascal есть еще один разновидность параметров — параметра-константы; они объявляются со словом const в начале. Аргументом для них может быть произвольное выражение того же типа, что и параметр.

Подстановка происходит так. Значение аргумента исчисляется и запоминается в участке памяти подпрограммы, которая вызывает (аналогично к параметров, а в подпрограмму, которая вызвана, передается ссылка на этот участок (как для параметр-сменных). Итак, этот механизм разрешает использовать аргументы-выражения и не требует копирования их значений к памяти вызова подпрограммы. Присваивание параметрам-константам запрещено; их обнаруживает транслятор.

(Еще не оценили)

Загрузка...

Функция является второй разновидностью подпрограммы. Вызов функции является выражением (числовым, булевим и т.п.). Значением этого выражения становится значение, которое исчисляется при выполнении вызова функции и в некоторый специальный способ возвращает в программу.

Пример 1. Вспомним вычисление минимального с двух целых значений. Результатом этого вычисления есть одно скалярное значение (число), которое удобно использовать как выражение, например, указать его как аргумент в вызове процедуры writeln.

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

program MinOfTwoNumbers; var a, b : integer;

{ функция вычисления минимума }

function min(x,y : integer) : integer;

begin

if x<y then min:=x else min:=y

end;

Begin

wrіteln(‘Задайте два целых числа:’)

readln(arb);

{вызов функция-аргумент в вызове процедуры}

writeln(‘Минимальное Из них: ‘, min(a,b));

End.H

Подпрограмма, что является функцией, начинается служебным словом function. После дужек с параметрами записывается двоеточие и тип значения, которое возвращает из вызова функции.

Возвращение значения происходит по помощи специальной сменной, которую обозначает имя функции (в приведенном примере это min). В теле функции обязательно должны быть операторы присваивания с именем функции в левой части, причем при выполнении вызова должны выполняться хотя бы один из них. Окончательное значение этой сменной возвращает из вызова функции.

Проиллюстрируем выполнение приведенной программы, считая, что сменные а таЬ во время введения получают значение 1 и 2. Сменная, одноименная с функцией, имеет «собственную» участок пам ‘яти и в таблице обозначенная min. min. Когда заканчивается вызов min, п значения присваивается дополнительной сменной, которая есть в «машинной» программе и обозначенная «Аргумент writeln» (см. табл. на с. 106).

Вызов функции является выражением и может быть частью более сложного выражения (мы видели это раньше, используя стандартные функции).

Примеры использования вызовов min

1.         Если с какой-то целью нам надо вычислить квадрат значения, которое возвращает из вызова min, или прибавить к нему 1, можно написать выражение sqr (тел (a,b)) или, соответственно,min (a,b) +1.

2.         Для вычисления минимального с трех целых значений a, b, с можно записать такие вызовы функции min.

m:=min(a,b);  m:=min(m,c)

Вместе с тем, минимальное с трех целых значений a, b, с является значением выражения min (min (а,b) , с). При его вычислении, когда начинает выполняться «внешний» вызов min, надо вычислить значения первого аргумента, а им есть «внутренний» вызов min (a,b). Поэтому выполняется этот «внутренний» вызов. Лишь потом значения, которые возвращает из него, присваивается первому параметру в выполнении «внешнего» вызова.

Аналогично минимальное с четырех значений задает выражение min (min (a,b) ,min (c,d)).

Пример 2. Прочитать длины четырех отрезков (гарантированиный, что это попарно разные додатні целые числа) и вычислить количество треугольников, которые из них можно образовать.

Чтобы вычислить количество треугольников, надо для каждой с четырех возможных троек отрезков проверить, можно ли образовать из них треугольник. Итак, нам надо одни и те самые вычисления провести четыре раза, только с разными числами.

Напишем функцию, которая вычисляет признак,  можно ли с трех отрезков образовать треугольник. Но возвращать из нее будем не булеве значение этого признака, а целое (0 отвечает false, 1 — true). Это разрешит просто напечатать сумму этих признаков:

program NumberOfTriangles;

var a, b, c, d : integer; function triangle(x, y, z : integer) : integer; begin

triangle:=ord{(x+y>z) and (x+z>y) and (y+z>x)) end; Begin

wrіteln(‘Задайте четыре додатних целых числа:’) readln(a,b,crd);

wrіteIn(‘Количество треугольников: ‘, triangle(a,b,c)+triangle(a,b,d)+ triangle(a,c,d)+triangle(b,c,d)) End.

Имя функции, записанное на месте выражения (по правую сторону в операторе присваивания, в условии разветвления или цикла, как аргумент в вызове и т.п.), обозначает вызов этой функции. Если эта функция имеет параметры, а в выражении записано лишь ее имя, это является синтаксической ошибкой.

Записывать имя функции в вызовах процедур введение запрещено (в отличие от записи в левых частях операторов присваивания).

(Еще не оценили)

Загрузка...

Описанное здесь сортировка в среднем медленнее, чем быстрое, хотя и имеет сложность в наиболее плохом случае B(n\ogn) . Тем не менее этот алгоритм применяется для сортировки файлов и решение некоторых других задач. Пирамидальная сортировка (или сортировка с помощью груды) использует бинарное дерево (пирамиду). Рассмотрим цс понятие. Расположим элементы массива с индексами 1..к строками, удваивая количество элементов в строках: в первой строке — первый элемент (с индексом 1), во второму — с индексами 2 и 3, в третьему — с индексами 4-7, дальше— 8-15 и т.п.. Последняя строка может остаться неполным, Например, при п = 10 будет образована пирамида индексов, как на рисунке.

Рассмотрим пирамиду как бинарное дерево с корнем наверху и листвой внизу. Дерево образовано узлами, которые відловідають индексам, и связями между ними — дугами. Корнем дерева является узел 1. Узлы 2 и С назовем сыновьями узла І (их отца), узлы 4 и 5 — сыновьями 2 и т.п.. Узлы, которые не имеют сынов, называются листками (на рисунке это узлы 6-10. Итак, если узел и имеет сынов, то ими есть узлы с индексами 11 и 2/ + 1, а его отцом является узел с индексом / div 2.

Дальше будем рассматривать узлы дерева, которые содержат значение элементов массива с соответствующими индексами, Для сортировки важным есть упорядочения значений в массиве, за который при каждому возможному и исполняется неровность А\\ div 2] >/4[j], т.е. «сын не больше отца». Это свойство не касается лишь корня дерева, поскольку он не имеет отца. Дерево с этим свойством называют правильным, или правильной грудой. Рассмотрим пример правильного дерева, которое отвечает последовательности значений

Сортировка с помощью груды использует то, что корень правильной груды содержит ее максимальное значение. Сначала в массиве образуем правильную груду, дальше поменяем местами значения первого элемента массива (корня дерева) и последнего. Наибольшее значение займет «свое» последнее место в массиве, и дальше о нем можно забыть. Среди сдачи элементов массива восстановим основное свойство груды и обменяем местами значения первого элемента и теперь уже предпоследнего, и так будем действовать дальше, пока дерево не сократится до одного элемента. procedure   heapSort(var   A:alnt;   n:word);

var   j:word;    {индекс   последнего} begin

build(A,n);    {начальное   построение   хупи} for   j:=n   downto   2   do   begin swap(A[l],A[j]);

rebuild(A,1,j-1)    {восстановление  правильности} end end;

Сначала уточним процедуру rebuild восстановление правильности груды. Если значение в корневом узле изменилось, основное свойство в нем может не выполняться, поэтому по потребности больший из сынов обменивается с отцом, после чего основное свойство проверяется и восстанавливается для сына. Действия из восстановление правильности груды в части массива А]/], …, A[d] нетрудно уточнить рекурсивной процедурой.

• procedure   rebuild(var  A:alnt;   f,d:word); var   maxSon:word;    {индекс   максимального   сына} begin
• maxSon:=f;
• if    (2*f<=d)and(A[f]<A[2*f])
• then  maxSon   :=   2*f;
• if    (2*f+K=d) and(A[maxSon]<A[2*f+1])
• then maxSon:=2*f+1; if   maxSonOf   then   begin swap(A[f] r[maxSon]) ; rebuild<A,maxSon,d); end; end;
• Приведенная процедура является примером так называемой «хвостовой ре-курсії», когда после рекурсивного вызова нет никаких действий. В подобных ситуациях рекурсию можно заменить циклом, условие завершения которого отвечает условию «дна рекурсн». Очевидно также, что перестройку дерева можно закончить, если значение максимального сына и отца местами не обменивались. В этой ситуации, чтобы прекратить выполнение цикла, присвоим индекса «отца» f значение за пределами части массива, который перестраивается. Итак, приведем нерекурсивный вариант процедуры rebuild, procedure   rebuild(var   A.alnt;    f,d:word); var  maxSon:word;    {индекс   максимального   сына} begin
• while (2*f<=d)do begin
• maxSon:=f;
• if   <M?]<A[2*ff]) then maxSon:=2*f;
• if    (2*f+K=d)andCA[raaxSon]<   A[2*f+1]) then maxSon:=2*f+l; if   maxSonOf   then  begin swap(A[f],A[maxSon]);
• f :=maxSon  -{дальше  перестройка пирамиды сына} end
• else   f:=d+l; end;
• {2*f   >  d   или   A[f]    >= A[maxSon]} end;

В конце концов уточним начальное построение груды за процедурой build. Заметим, что в массиве с п элементами максимальным ‘индексом узла-отца есть п div 2. Итак, последовательно образуем правильные груды в піддеревах, корнями которых являются узлы п div 2, п div 2 — и,…, 1. Это разрешит утверждать, что построенный массив представляет собой правильную груду.

• procedure build(var A:alnt; n:word); var и:word;
• begin
• for i:=n div 2 downto 1 do
• rebuild(A,i,n); {перестройка чаотини массива}
• end;

Оценим сложность алгоритма. Очевидно, что она прямо пропорциональная общему количеству вызовов rebuild. При выполнении build процедура rebuild вызывается п div 2 раза, а при выполнении цикла for процедуры treeSort — еще л — 2 раза, т.е. общее количество вызовов процедуры rebuild из других процедур есть ®(п).

Оценим сложность выполнения одного вызова процедуры rebuild. Заметим, что в цикле значения сменной f не менее чем удваивается, а цикл не будет продлеваться, если это значение станет больше d, которое не больше г. Итак, таких удвоений не может быть больше чем |_log2 п\ . Количество действий в теле цикла является константой, поэтому общая сложность имеет оценку 0{n\ogn). Высотой узла дерева называют количество ребер в наиболее длинном пути из этой вершины вниз к листкам; высоту корня называют высотой дерева. Дерево, которое образовано как пирамида с п узлов, имеет высоту log2 п .

(Еще не оценили)

Загрузка...

Первый алгоритм быстрой сортировки 1960 года разработал Ч.А.Р. Хоар (CA.R.Hoare). Этот алгоритм есть одним из найпопу-лярніших, поскольку сравнительно нескладный в реализации, хорошо работает на разнообразных видах входных данных и не требует огромных объемов дополнительной памяти (кроме относительно небольшого стека).

Идея быстрой сортировки такая. В некоторый способ выбирается эталонное значение есть. Значение элементов массива А обмениваются так, что массив разбивается на две участка — левую и правую. Элементы в левом участке имеют значение не больше есть, а в правой — не меньше. После этого достаточно отдельно отсортировать эти две участка.

Существует простой, но довольно эффективный способ выбора есть в участке массива A[L],…, A[R]: есть = A[(L+R) div 2]. Для разбивки используются два индекса — «левый курсор» и и «правый курсор» j. Сначала i=L, j=R; дальше они двигаются навстречу друг другу в такой способ. Значение меньше есть («хорошие») в левой части пропускаются, а на «плохому» движение останавливается. Аналогично после этого в правой части пропускаются значение, которые большие есть. Если и еще не стал больше j, то это означает, что оба они указывают на «плохие» значение. Эти значения обмениваются местами, а курсоры сдвигают навстречу друг другу. Движение курсоров продлевается, пока и не станет больше j. Тогда все элементы от A[L] к А[ j] имеют значение не больше есть, а все от А [и] к A[R] — не меньше. Эти две участка, если их длина больше 1, делятся и сортируются рекурсивно. Если же участок имеет длину 1, то ее уже отсортировано.

Оформим сортировка части массива A [L], …, A[R] такой процедурой:

• procedure   quicksort(var  A:alnt;   L,R:word); var   e:integer;    {эталонное   значение} и,j:word;    {левый   и   правый   курсоры) begin
• и:=L;   j:=R; e:=A[(i + j)    div   2] ; while   i<=j   do begin
• while  A[i]<e   do   inc(i); while   A[j]>e   do   dec(j); if   i<=j   then  begin swap(A[i],A[j]); inc(i);   dec(j); end; end;
• {i  >  j};
• if L<j {сортировать левый участок) then quicksort(A,L,j); if i<R {сортировать правый участок) then quicksort(А,и,R); end;

Оценим сложность приведенной реализации быстрой сортировки. Пусть массив А имеет п элементов. В наиболее плохом случае в каждом вызове процедуры quicksort эталонным значением есть меньше всего в участке от A. [L] AO[R] , и разбивка участка массива длиной т дает участка длиной 1 и т — 1, Поскольку т = п, п—1, …, 2, глубина рекурсии достигает 0(и), и при каждом значении т разбивка участка длиной т имеет сложность ОБ(т). Тогда суммарная сложность имеет оценку 0 (w) + 9 (« -1)+…+Є>(2) = 0(л2) .

Тем не менее описанный наиболее плохой случай в реальных данных практически никогда не случается. Для подавляющего большинства данных разбивки участка массива дает две участка с приблизительно равными длинами. Поэтому размеры массивов, которые сортируются, при переходе на следующий уровень рекурсии уменьшаются приблизительно вдвое. Итак, в среднем количество уровней рекурсии оценивается как 0(log п). Очевидно, что на каждом равные рекурсии суммарная сложность есть 0(п), поэтому общая сложность в среднем имеет оценку 0(nlogn).

Многочисленные практические исследования свидетельствуют, что приведенный алгоритм в среднем работает быстрее, чем другие алгоритмы сортировки, которые имеют сложность наиболее плохого случая O(n)ogri) . Быстрая сортировка не сохраняет взаимного порядка одинаковых значений, т.е. есть неустойчивым.

Для выбора эталонного значения существует много способов, а не только выбор A[(L + R)/2). Если эталонным есть одно со значений в сортированной части массива, ведь это разрешает не беспокоиться о предотвращении выхода за границы сортированной часть и не проверять дополнительных условий.

Выбор «золотой середины» (значение, которое должных быть посредине, или медиана) требует немалых дополнительных усилий и может вообще ухудшить оценку сложности. Тем не менее довольно эффективным есть выбор среднего с трех значений — первого (с индексом L), последнего {R) и срединного ((І + R)/2). Для этого перед выбором эталону их можно обменять местами таким образом.

• if  A[L]   >  A[(L+R)    div   2]
• then   swap (A[L] ,A[ (L+R)   div   2] ) ;
• if   A[(L+R)    div   2]    >  A[R]
• then   swap   (A[(L+R)   div   2],A[R]>;
• if  A[L]    >  A[(L+R)    div   2]
• then   swap(A[L],A[(L+R)    div  2]);
• e   := A[(L+R)   div   2];

Еще два способа выбора эталонное значение приведено в задачах к этой главе.

Итеративная версия алгоритма. Запишем итеративную процедуру, в которой явным образом реализуем обработку стека, необходимую для выполнения рекурсивной процедуры. Смоделируем программный стек с помощью массива Stack, в котором будем сохранять левые и правые границы сортированных підмасивів. Сначала присвоим элементам массива Stack значение 0 с помощью стандартной подпрограммы f illchar.

• procedure   Quicksort(var  A:alnt;   nrword); var   i,   j,   L,   R,   top   :   word; e   :   integer;
• Stack   :   array[1..N_max,1..2]   of   word; Begin
• FillChar(Stack,SizeOf (Stack) ,0) ;
• top:=l;    {индекс   верхушки   стека}
• Stack[top,1]    :=  1;   Stack[top,2]    := N;
• while   top>0   do
• begin
• L:«Stack[top,1]; R:=Stack[top,2];
• dec(top);
• e:=A[(L+R) div 2];
• и:»L; j:=R;
• repeat
• while (A[i]<e) do inc(i); while (A[j]>e) do dec(j); if i<=j then begin Swap(A[i],A[j]); inc(i); dec(j); end; until i>=j; if L<j then begin inc(top);
• Stack[top,1]:=L; Stack[top,2]:=j; end;
• if i<R then begin inc(top); Stack[top,1]:=i; Stack[top,2]:=R;
• end; End; End;