4787

Простые типы данных. Линейные программы

Лекция

Информатика, кибернетика и программирование

Простые типы данных. Линейные программы Заголовок программы. Константы и их использование. Раздел констант. Переменные программы. Раздел переменных. Стандартные простые типы данных: Тип данных Integer Тип данных Real...

Русский

2012-11-27

99.5 KB

37 чел.

Простые типы данных. Линейные программы

1.Заголовок программы.

2.Константы и их использование. Раздел констант.

3.Переменные программы. Раздел переменных.

4.Стандартные простые типы данных:

  Тип данных Integer;

  Тип данных Real;

  Тип данных Char.

5.Понятие выражения. Значение выражения. Тип выражения.

6.Раздел операторов. Оператор присваивания.

7.Операторы ввода-вывода.

8.Пример линейной программы.

9.Понятие сложности выражения. Оптимизация вычислений.

10.Оптимизация линейных программ.

11.Задачи и упражнения

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

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

1.Заголовок  программы.

Синтаксическая диаграмма заголовка программа имеет вид:

Заголовок

программы

 

В стандарте языка используются стандартные файлы с именами:

Input - входной стандартный файл (имя стандартного устройства ввода).

Output - выходной стандартный файл (имя стандартного устройства вывода).

Примеры заголовка :

program LinearUnequation (Input, Output);

program GrafTrans;

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

2.Константы и их использование. Раздел констант.

Раздел констант определяется следующей диаграммой:

 

раздел

констант

В разделе констант определяются имена как синонимы констант. Под константой понимается либо некоторое число, либо имя константы, возможно со знаком, либо строка.

Пример раздела констант:

const Pi = 3.1415926; alfa = 7.1219;

MinInt = -MaxInt;

Line = ‘____________________________’;

FirstLine = ‘______ Список группы________’;

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

3.Переменные программы. Раздел переменных.

Раздел переменных определен диаграммой :

Раздел

переменных

   

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

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

1.Распределения памяти. Распределение (резервирование) памяти для переменных, описанных в разделе переменных, производит компилятор на этапе генерации кода. Для каждой переменной в ОЗУ отводится определенное место. Размер этой части памяти определяется типом переменной.

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

3.Контроля правильности применения переменных. Ошибка, допущенная при написании переменной в разделе операторов, приведет к сообщению об синтаксической ошибке, так как эта переменная не описана в разделе переменных.

Пример раздела параменных:

var Root1, Root2, Discriminant : Real;

Index, Counter : Integer;

A,B,C : Real;

Letter : Char;

IsSolution : Boolean;

4.Стандартные простые типы данных

В языке Паскаль определены 4 стандартных простых типа данных:

Integer (целый);

Real (вещественный);

Char (символьный).

Boolean (логический);

Для полного описания каждого типа данных, используемых в языке программирования, необходимо знать:

множество допустимых значений для данных этого типа;

допустимые операции над данными этого типа;

функции, определенные на данных этого типа или принимающие значения в этом типе;

допустимые отношения на данных этого типа.

Тип данных Integer .

Значениями целого типа являются элементы зависящего от реализации подмножества (отрезка) целых чисел. Это означает, что существует стандартная константа с именем MaxInt, такая что для любого данного X типа Integer

MaxInt < X < MaxInt

Наиболее распространенное для 16 разрядных ПЭВМ значение  MaxInt = 215 - 1 = 32767.

Операции:

* -    умножение; div -  целочисленное деление; mod - остаток от целочисленного деления;

+ -      сложение;   -    -  вычитание;

Функции:

Abs(x) -  х ;

Sqr(x) - х 2;

Trunc(x) - отбрасывание дробной  части от вещественного х;

Round(x) - округление вещественного x;

Succ(x) - х + 1;

Pred(x) - х - 1;

С некоторыми другими функциями мы познакомимся позже - при определении других типов данных.

Отношения:

 < - меньше     <= - меньше или равно

 > - больше      >= - больше или равно

 = - равно       <> - неравно

Тип данных Real.

Значениями вещественного типа являются элементы зависящего от реализации подмножества вещественных чисел. В TP-6 диапазон типа Real [ 2.9*10 -39 ... 1.7*10 38 ]

Операции:

*  - умножение;      /   - деление;

+  - сложение;        -   - вычитание;

Функции:

Abs(x) - модуль х;

Sqr(x) - х в квадрате; 

Sqrt(x) - корень из х.

Sin(x) - sin х;

Cos(x)- cos х;

Arctan(x)- arctg х;

Ln(x)  - ln х;

Exp(x) - e х;

Отношения: такие же, как и для типа Integer.

Числовые типы Integer и Real совместимы. Это означает, что данные типа Integer могут обрабатываться как вещественные числа и результат будет иметь тип Real.

Тип данных Сhar.

Значениями символьного типа являются элементы конечного и упорядоченного множества символов. Символы этого множества определяются реализацией. Они должны быть и на вводных, и на выводных устройствах. Большинство ПЭВМ поддерживает ASCII - код, поэтому в реализациях языка множество значений типа Char совпадает с некоторымм расширением ASCII - символов. ASCII код каждому символу, определенному в нем, ставит в соответствие один байт.

Вне зависимости от реализации множество символов включает:

A,  B, C, ... , Z, _  (знак подчеркивания)

 1, ... , 9 - (десятичные цифры)

 Символ пробела.

Функции:

 Ord(x) - порядковый номер x.     Chr(n)- символ с порядковым номером N.

 Pred(x)- символ, предшедствующий x.    Succ(x) - символ, следующий за x.

Отношения.

Как уже сообщалось, тип данных Сhar упорядочен. Это означает, что данные типа Сhar можно сравнивать, как и данные числовых типов, с помощью отношений:

= , <> , > , < , >= , <= .

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

Логический тип данных Boolean будет описан ниже - когда мы будем изучать понятие условия.

5.Понятие выражения. Значение выражения. Тип выражения.

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

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

Таблица приоритетов.

Функции, not.

Мультипликативные операции: * , /  ,div , mod ,  and

Аддитивные операции:   + ,  - , or

Отношения: = , <> , > , < , >= , <= , in

Операции одного приоритета вычисляются слева направо. Это соответствует группировке скобок в бесскобочном выражении влево.

a + b + c = (a + b) + c,               a * b * c = (a * b) * c

Выражения, заключенные в скобки, вычисляются независимо.

Важно понимать, что в ходе вычисления значения выражения каждый промежуточный результат - данное некоторого типа, точно определенного знаком операции или функции и типами операндов. Любое несоответствие типа значения операнда приведет к ошибке, выявляемой компилятором при синтаксическом анализе.   Наглядное представление о структуре выражения дает так называемое дерево выражения. Например, выражение sin(x+pi/2) - cos(2*y-pi) может быть представлено в виде дерева:

 

 

 

Вычисление значения выражения осуществляется в соответствии с движением по ветвям от листьев к корню - снизу вверх..

6.Раздел операторов. Оператор присваивания.

Действия, производимые над данными, описываются в разделе операторов. Синтаксическая диаграмма раздела операторов имеет вид:

раздел

операторов

Самым основным, фундаментальным оператором языка является оператор присваивания. С помощью оператора присваивания осуществляется преобразование информации.

Он имеет вид:  < имя > := < выражение >

оператор

присваивания

Имя слева от символа присваивания := является именем переменной, которой присваивается значение выражения, стоящего справа. Поэтому наряду со значением выражения важным атрибутом является его тип. Тип выражения в правой части оператора присваивания должен совпадать или быть совместимым с типом переменной из левой части. Компилятор на этапе синтаксического анализа программы осуществляет эту проверку - так называемый контроль типов. Допустимо присваивание переменным любых типов, за исключением типа File.

Root1 := Pi*(x - y)

Solution := Discriminant >=0

Discriminant := Sqrt(b*b-4*a*c)/2/A

Index := Index + 1

Letter := Succ(Succ(Letter))

7.Операторы ввода - вывода.

Для организации ввода - вывода данных в языке Pascal используются операторы - процедуры Write, Read, Writeln, Readln. С помощью этих операторов организуется ввод-вывод данных в/из файлы Input ,Ouтput.

Текстовые файлы Input, Output представляются пользователю как текст, разбитый на строки и снабженный признаком конца текста и признаками концов строк. Каждая строка может содержать числа или символьные данные (т.е. строка состоит из нескольких данных типов Integer, Real, Сhar). Чтение /  запись осуществляется через т.н. буфер файла. В момент обращения к файлу его буфер установлен на некоторое данное - элемент файла. Буфер файла может быть перемещен либо к следующему данному, либо к первому данному следующей строки.

Оператор Read(x) читает данное из Input в переменную х и перемещает буфер к следующему данному.

Оператор Wriте(x) перемещает буфер в следующую позицию и пишет данное в Output из переменной х.

Оператор Readln(x) читает данное с новой строки из файла Input в переменную х.

Оператор Wriтеln(x) пишет данное с новой строки в Output из переменной х.

Операторы ввода/вывода могут использоваться в более общей форме:

Read( <список переменных> ),                Readln( <список переменных> )

Write( <список выражений или строк> )     Writeln( <список выражений или строк> )

Эта форма определяется синтаксическими диаграммами:

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

8.Пример линейной программы.

Пример 1. Программа вычисления площади круга, вписанного в треугольник и площади круга, описанного около треугольника.

Program Triangle; {программа вычисляет площади, вписанного в треугольник и описанного        около треугольника кругов}

Const  Pi = 3.1415926;

          Line = ‘_______________________________’;

Var a, b, c : Real;

      Sint, Sout : Real;

      S, p : Real;

Begin

 { ввод данных }

 Write(‘введите стороны треугольника a b c ‘);

 Readln(a, b, c);

 { вычисления }

 p := (a + b + c)/2;

 S := Sqrt(p*(p - a)*(p - b)*(p - c));

 Sout := Pi*sqrt(a*b*c/4/S);

 Sint := Pi*sqrt(2*S/p);

 { печать ответа }

 Writeln; Writeln (Line);

 Writeln(‘Sвпис = ‘, Sout); Writeln(Line);

 Writeln(‘Sопис = ‘, Sint); Writeln(Line)

End .

Операторы Readln и Writeln могут применяться без параметров (т.е. без текста в скобках вместе со скобками), для перехода к вводу/выводу со следующей строки или для пропуска строки.

Для оформления вывода в операторах Write, Writeln можно использовать строку. Например: writeln(‘***’, ‘площадь вписанной окружности = ‘, sint, ‘***’). Текст программы может содержать комментарии. Комментарий - это некоторый текст, заключенный в фигурные скобки. Комментарии используют для пояснений, необходимых для лучшего понимания программы. Хорошо прокомментированная программа - признак квалификации и добросовестности программиста.

Особое  внимание следует обращать на проектирование ввода-вывода. В профессиональных программах это - одна из наиболее важных проблем. Здесь следует выделить следующие аспекты:

Защита программы от ошибок пользователя при вводе данных;

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

Обсуждение этих аспектов, однако, выходит за рамки этой книги.

9.Понятие сложности выражения. Оптимизация вычислений.

Основной критерий качества программы - ее правильность.  Строгое математическое понятие правильности программы пока выходит за рамки нашего рассмотрения. Будем предполагать, что наши программы выполняют именно те действия, которые мы от них ожидаем.

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

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

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

U := X*Cos(Alfa) + Y*Sin(Alfa)       (1)

V := -X*Sin(Alfa) + Y*Cos(Alfa)       (2)

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

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

Пусть Tf, Tm и Ta - времена вычисления соответственно функций, умножений и сложений, а T(U) - время вычисления значения U. Тогда

T(U) = 2Tf + 2Tm + Ta,   T(V) = T(U)    (3)

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

а)Тождественные пребразования, уменьшающие сложность;

б) Предварительные вычисления общих подвыражений;

Примеры:

U := 4*Sin(X)*Cos(X) + 3       <==>   U := 2*Sin(2*X) + 3

U := Sin(X)^2 - 3*Sin(X) + 2   <==>   U := (Sin(X) - 2)*(Sin(X) - 1)   <==> 

Y := Sin(X);   U := (Y - 2)*(Y - 1)

Между величинами Tf, Tm и Ta существуют соотношения

   Tf  >> Tm > Ta       (4)

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

Следующий пример по существу определяет оптимальную форму записи многочлена для задачи вычисления его значения.

Пример 2 ( Схема Горнера)

Вычислить значение Y = a0x3 + a1x2 + a2x + a3;

Поскольку операции возведения в степень в языке нет, можно заменить его умножениями:

Y = a0*x*x*x + a1*x*x + a2*x + a3;

В этом варианте T(Y) = 6Tm + 3Tа;

Вынося x за скобки там, где это возможно, получим:

Y = ((a0x + a1)x + a2)x + a3; {Схема Горнера}. T(Y) = 3Tm + 3Tа.

Можно показать, что схема Горнера вычисления многочлена является оптимальной.

10.Оптимизация линейных программ.

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

Пример 3. Программа вычисления координат вектора, повернутого на угол Alfa.

Program Vector;

Var X, Y : Real;

Alfa : Real;

U, V : Real;

Begin

{ Ввод X, Y, Alfa }

U := X*Cos(Alfa) + Y*Sin(Alfa);

V := -X*Sin(Alfa) + Y*Cos(Alfa);

{ Вывод U, V }

End.

В этом варианте сложность программы T(U, V) есть  T(U, V) = 4Tf + 4Tm + 2Ta 

Осуществим предварительное вычисление функций Sin, Cos:

{ Описать вспомогательные переменные Fsin, Fcos }

Begin

{ Ввод X, Y, Alfa }

Fsin := Sin(Alfa); Fcos := Cos(Alfa);

U := X*Fcos + Y*Fsin;

V := -X*FSin + Y*Fcos;

{ Вывод U, V }

End.

Получим: T(U, V) = 2Tf + 4Tm + 2Ta

В результате преобразования сложность уменьшилась примерно вдвое. Можно еще уменьшить мультипликативную сложность, если вычислить U и V следующим образом:

A := (Fcos + Fsin)*(X + Y);

B := X*Fsin; C := Y*Fcos;

U := A - B - C;

V := C - B;

Тогда   T(U, V) = 2Tf + 3Tm + 5Ta

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

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

Пример 4  Известно, что уравнение  x2 - px + q  имеет два решения. Найти их.

Вариант 1:

Discriminant := Sqrt(p*p - 4*q);

Root1 := ( p + Discriminant )/2;

Root2 := ( p - Discriminant )/2;

Вариант 2:

Discriminant := Sqrt(p*p - 4*q);

Root1 := (p + Discriminant)/2;

Root2 := p - Root1;

Вычисления во втором варианте содержат на одно деление меньше.  Здесь оптимизация достигнута благодаря наличию соотношения между Root1 и Root2: Root1 + Root2 = p.

Отметим в заключение, что рассмотренные оптимизационные приемы имеет смысл применять тогда, когда вычисления повторяются в программе достаточно часто и время выполнения программы - критический параметр.

11.Задачи и упражнения.

Составить программу решения задачи:

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

2.Смешано V1 литров воды температурой t1 с V2 литрами воды температуры t2. Найти объем V и температуру t образовавшейся смеси.

3.Найти радиус круга с центром в (X0,Y0), касающегося прямой y = kx + b.

4.Вычислить центр тяжести системы из трех материальных точек на плоскости с массами M1, M2, M3 и координатами (X1,Y1), (X2,Y2), (X3,Y3).

5.Решить систему линейных уравнений методом Крамера.

а11х1 + а12х2 = в1

а21х1 + а22х2 = в2

{Считать, что ее определитель не равен нулю }

6.Вычислить координаты точки А(X,Y) при повороте системы координат на угол Alfa и параллельном переносе на вектор a = (u, v).

7.Найти корень степени n и n-тую степень положительного действительного числа a.

8.Вычислить целые коэффициенты А, В, С квадратного уравнения по его рациональным корням х 1 = n 1 / m 1,   x 2 = n 2 / m 2.

9.Вычислить внутренние углы треугольника, заданного длинами сторон.

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

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

12.Расчитать координаты материальной точки, пущенной с начальной скоростью V0 под углом Alfa к горизонту в направлении вектора а = (X0,Y0) в момент времени t.

13.Вычислить сумму, произведение и частное двух комплексных чисел z1 = a+bi, z2 = c+di.

14.Многочлены F(x) = ax + b и G(x) = cx + d заданы своими коэффициентами. Найти коэффициенты многочлена H(x) = F(x)*G(x).

15.Многочлены F(x) = ax + b и G(x) = cx + d заданы своими коэффициентами. Найти коэффициенты многочленов H1(x) = F(G(x))  и  H2(x) = G(F(x))

Задачи

1.Найти решение упражнения 13, использующее 3 умножения.

2.Найти решение упражнения 14, использующее 3 умножения.

3.Найти решение примера 3, использующее 1 операцию вычисления тригонометрической функции.

4.Используя решение задачи 2, найти схему умножения двух квадратных трехчленов, использующую 6 умножений.


 

А также другие работы, которые могут Вас заинтересовать

1622. Плацентарный барьер 19.59 KB
  Плацентарный барьер - совокупность морфологических и функциональных особенностей плаценты, обусловливающих ее способность избирательно пропускать вещества из крови матери к плоду и в обратном направлении.
1623. Подготовка к оказанию акушерской помощи 19.88 KB
  Акушерскую помощь оказывают чаще во время родов и реже при беременности и в послеродовом периоде. Обычно она бывает неотложной, подлежащей быстрому и точному исполнению.
1624. Половой акт (половые рефлексы самцов) 20.76 KB
  Половой акт — это комплекс условных и безусловных половых рефлексов, обеспечивающих выделение спермы из половых органов самца и внедрение ее в половые пути самки.
1625. Половой цикл у разных видов животных, его стадии 20.82 KB
  Половой цикл - сложный нейрогуморальный рефлекторный процесс, сопровождающийся комплексом физиологических и морфологических изменений в пол органах и во всем организме самки от одной стадии возбуждения до других.
1626. Положение, предлежание, позиция и членорасположение плода во время родов 18.8 KB
  Положение плода — расположение продольной оси тела плода по отношению к продольной оси тела матери. Продольное расположение правильное, вертикальное и поперечное — патологические.
1627. Понятие о ветеринарной гинекологии и андрологии. Их задачи в профилактике и ликвидации бесплодия с/х животных 20.83 KB
  Ветеринарная гинекология как отрасль клинической ветеринарии изучает патологические процессы в половых и других органах вне беременности, родов и послеродового периода и процессы, приводящие к бесплодию самок.
1628. Понятие о естественном осеменении животных 20.15 KB
  Естественное осеменение в половые - комплекс условных и безусловных рефлексов обеспечения, выделения спермы из органа самца в половые органы самки.
1629. Понятие о родовом акте. Факторы, обуславливающие роды 20.16 KB
  Родовой акт - физиологический процесс, заключающийся в выделении их организма матери зрелого живого плода с изгнанием плодных оболочек и плодных вод.
1630. Послеродовой парез: причины, формы, признаки, диагностика, лечение и профилактика 20.75 KB
  Послеродовом парез - острое тяжело протекающее заболевание у высокопродуктивных, хорошо упитанных животных, получающих большое количество концентрированных кормов.