[Править]Структурное программирование

Следующий шаг был сделан в 1954 году, когда был создан первый язык высокого уровня — Фортран (англ. FORTRAN - FORmula TRANslator). Языки высокого уровняимитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека, с помощью них, можно писать программы до нескольких тысяч строк длиной. Однако легко понимаемый в коротких программах, этот язык становился нечитаемым и трудно управляемым, когда дело касалось больших программ. Решение этой проблемы пришло после изобретения языков структурного программирования (англ. structured programming language), таких как Алгол(1958), Паскаль(1970), Си(1972).

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

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

Также создавались функциональные (аппликативные) языки (Пример: Lisp — англ. LISt Processing, 1958) и логические языки (пример: Prolog — англ. PROgramming in LOGic, 1972).

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

[Править]ооп

В итоге в конце 1970-х и начале 1980-х были разработаны принципы объектно-ориентированного программирования. ООП сочетает лучшие принципы структурного программирования с новыми мощными концепциями, базовые из которых называются инкапсуляцией, полиморфизмом и наследованием.

Примерами объектно-ориентированных языков являются Object Pascal, C++, Java и др.

.

Билет 20

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

• синтаксические, возникающие в результате нарушения правил написания предложений языка;

• семантические, связанные с недопустимыми значениями параметров, недопустимыми действиями над параметрами и т. д.; выявляются эти ошибки во время работы программы (обычно на этапе отладки);

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

Отладка предполагает выполнение следующих моментов:

• выявление факта наличия ошибки в программе;

• определение места нахождения ошибки (локализация);

• устранение ошибки.

Хз что еще

Билет 21

Итерационные циклы: уточнение корня алгебраического уравнения

Пусть в результате отделения корней стал известен отрезок [a, b], на котором функция f(x) имеет единственный корень. Требуется уточнить его значение с погрешностью . Выберем для решения данной задачи метод хорд. Задаем начальное приближение, например, x = a. Хордой соединяем точки кривой на границах отрезка ab:

Ввод (a, b, e) [y - f(x)]/[f(b) - f(a)] =

x:= a = (x - a)/(b - a).

Пока |f(x)| > e Отсюда точка пересечения

y:= f(a); z:= f(b); хорды с осью абсцисс:

x = a - f(a)(b - a)/[f(b) - f(a)]; w:=f(x) x = a - f(a)(b - a)/[f(b) - f(a)].

y*w < 0

ДА НЕТ Это очередное приближение.

b:= x a:= x Переопределяем отрезок ab.

Вывод (x, f(x))

Применим приведенный выше алгоритм для уточнения корня с погрешностью 0,0001 на отрезке [0, 2] уравнения .

program Horda;

const

e = 0.0001;

var

n: byte;

a, b, w, x, y, z: real;

begin

writeln(‘Введите границы отрезка’);

readln(a,b);

x:= a; n:= 0;

while abs(x*x-1) > e do begin

y:= a*a-1; z:= x*x-1;

x:=a - y*(b - a)/(z - y); w:= x*x -1;

if y*w < 0 then b:= x else a:= x;

n:= n + 1 end;

writeln(‘Корень уравнения = ’, x);

writeln(‘Значение функции в этой точке = ’, x*x-1)

writeln(‘Число итераций: ’,n) end.

Вложенная конструкция оператора условного перехода

Что же должно выполниться в случае "иначе"? На эту ветку оператора попадают все неположительные значения х. Если бы для этих чисел нужно было бы выполнить один и тот же оператор (или группу операторов), то проблемы бы не стояло. Но нам нужно этот промежуток разделить еще на две части (отрицательные и ноль) и для каждой части выполнить свой оператор. Поэтому ветка "иначе" будет содержать еще один условный оператор, и наш вложенный условный оператор будет иметь вид:

если х>0   то      у вычислить по формуле у=х-12   иначе      если х=0       то         у вычислить по формуле у=5       иначе         у вычислить по формуле у=sqr(x);

Тогда фрагмент программы для решения этой задачи будет выглядеть так:

if х>0   then      у := х-12   else      if х=0       then          у := 5       else          у := sqr(x);

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

Если часть else используется во вложенных if, то каждое else соответствует тому if, которое ему непосредственно предшествует. Таким образом, при определении последовательности выполнения фрагментов нет двусмысленности.

Билет 22

Напомним, что каждый модуль (процедура, функция, программа) состоит из заголовка (procedure…, function…, program…) и блока.

Если блок какой-либо процедуры p1 содержит внутри процедуру p2, то говорят, что p2 вложена в p1.

Пример.

procedure p1(x: real; var y: real);

var c: integer;

procedure p2(var z: real);

…………………….

end;

begin

…………………….

end;

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

Пример.

procedure t1;

var y1, y2: real;

procedure sq1;

var a, b, c, d: real;

begin

{ Переменные a, b, c, d являются локальными для sq1,

область их действия – процедура sq1 }

……………………………………

end;

begin

{ Переменные y1, y2 - нелокальные для sq1,

область их действия – t1 и sq1 }

end;

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

При написании программ, имеющих вложенные модули, необходимо придерживаться следующих правил:

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

2. Если один и тот же объект (переменная, тип, константа) используются в двух и более блоках, то описать этот объект надо в самом внешнем из них, содержащем все остальные блоки, использующие данный объект.

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

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

Пример.

var k: integer;

procedure a;

var x, z: real;

begin

{ через x, z обозначены две величины –

локальные переменные для a;

k – глобальная переменная для a }

…………………………………

end;

procedure b;

var x, y: integer;

begin

{ через x, y обозначены две другие величины –

локальные переменные для b;

k – глобальная переменная для b }

…………………………………

end;

begin

{ k – единственная переменная, которую

можно использовать в основной ветке программы }

…………………………………

end.

Если один и тот же идентификатор описан в блоке b и второй раз описан во вложенном в b блоке c, то надо помнить, что эти два одинаковых идентификатора соответствуют разным ячейкам памяти.

var

i: integer;

a: real;

 

procedure p(var d: real);

var i: integer;

begin

i := 3;

d := i + 10 * d;

end;

 

begin

a := 2.0;

i := 15;

p(a);

writeln(' i = ', i, ' a = ', a);

readln

end.

Глобальным переменным i и a отводятся две ячейки памяти. Первыми выполняются операторы a := 2.0 и i := 15. Затем вызывается процедураp(a). В процессе работы p отводится ячейка для локальной переменной iи туда засылается число 3. После окончания работы процедуры p эта ячейка i программой «забывается». После возврата на оператор writelnпрограмма знает только одну ячейку i – глобальную, т.е. ту, которая содержит число 15. Поэтому программа выдаст на печать i = 15, a = 23.0, т.к. a = 3 + 10 * 2.

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

Пример.

type ab = array[1..3] of real;

var a: ab;

procedure q;

var b: ab;

…………………………..

end;

В этом примере переменные a и b описаны через общий тип ab. Если же локальная и глобальная переменные описаны одинаково, но не через общий тип, то программа может «не понять», что эти переменные принадлежат одному типу.

Пример.

var a: array[1..3] of real;

procedure q;

var b: array[1..3] of real;

……………………….

end;

В этом примере переменные a и b – одинаковые массивы, т.е. типы этих переменных одинаковы, но программа, тем не менее, «не считает», что a и b принадлежат одному типу. Это происходит из-за того, что описание массивов дано в разных блоках.

Тип-множество. В отличие от математического понятия множества множество в Turbo Pascal представляет собой совокупность элементов базового типа. Максимальный размер множества - 256 элементов, которые имеют порядковые номера от 0 до 255. Следовательно, в качестве базовых могут выступать стандартные типы данных byte и char, перечисляемые типы и их диапазоны. Множество включает в себя все возможные наборы элементов базового типа, т.е. все подмножества данного множества, включая пустое. Если базовый тип состоит из n элементов, то число всех подмножеств равно .

Описание типа-множества имеет вид:

type <имя типа> = set of <базовый тип>;

Приведем примеры правильного и неправильного описания.

type bukva = ‘a’..’z’; {Тип ‘строчная буква латинского алфавита’}

mn_bukv = set of bukva;

mn_byte = set of byte;

godi_ucheniya = set of 2002..2007; {Неверное описание}

mn_nat_chisel = set of 1..256; {Неверное описание}

Элементы в множестве располагаются произвольно и не повторяются. Задается множество с помощью конструктора множеств - [ ]. В нем через запятую перечисляются допустимые элементы, в том числе и диапазоны, например:

type vremena_goda = set of (vesna, leto, osen, zima);

var q, s : vremena_goda; {Множество времен года}

mn : set of 1..100; {Множество целых чисел от 1 до 100}

begin s := [ ]; {Пустое множество}

q := [vesna, leto];

mn := [1, 5..13, 27..33] …

О перации над множествами:

1. объединение множеств A и B - A + B 

например s := [vesna] + [leto..zima]; (результат - [vesna..zima])

2. пересечение множеств A и B - A * B 

например q := [leto] * [vesna..osen]; ([leto])

3. р азность множеств A и B - A - B 

например q := [leto..zima] - [osen]; ([leto, zima])

4. операции отношения:

- тождественность множеств A = B;

- нетождественность множеств A <> B;

- A является подмножеством B A <= B;

- B является подмножеством B A >= B.

Установить принадлежность некоторого элемента e множеству mn можно с помощью операции in, e in mn, которая возвращает значение true, если элемент e присутствует в множестве mn, и false - в противном случае. Для включения элемента в множество можно использовать процедуру include(mn, e), а для исключения элемента из множества - процедуру exclude(mn, e).

Пример 2. Из строки символов s1 удалить повторно встречающиеся символы. Структурограмма алгоритма и программа приведены ниже.

program Symbol_Odin_Raz;

var i byte;

s1, s2 : string;

mn : set of char;

begin writeln(‘Введите строку символов’);

readln(s1); s2 := ‘’; mn := [ ];

for i := 1 to length(s1) do begin

if not s1[i] in mn then s2 := s2 + s1[i];

mn := mn + [s1[i]]

end;

writeln(‘Исходная строка: ‘, s1);

writeln(‘Результирующая строка: ‘, s2)

end.

Билет №23

Сам напишу

Запись, описание типа, пример действий

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

type <имя типа> = record

<имя поля1> : <тип1>;

. . .

<имя поляj> : <типj> end;

Ниже приведены примеры описаний. Однотипные поля можно описывать через запятую.

complex = record re, im : real end; {тип ‘комплексное число’}

book = record {тип-книга}

avtor : string[30]; {поле ‘автор книги’}

titul : string; {поле ‘название книги’}

god_izd : 1990..2003 {поле ‘год издания’} end;

Теперь можно описать и соответствующие переменные:

var z1, z2, z3 : complex; b : book;

Поле записи задается составным именем, например так: z1.re - вещественная часть комплексного числа z1; b.avtor - автор книги b. Из приведенных примеров видно, что составные имена полей могут быть достаточно громоздкими и затруднять описание действий с ними. Для упрощения обращения к полям записи служит оператор присоединения with, имеющий следующую конструкцию: with <имя записи> do <оператор>;

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

Д

X

ля примера рассмотрим вложенную конструкцию оператора присоединения для следующей структуры данных.

C

Y

p

A

rogram Vlogen_Zapisi;

v

B

ar x : record

c : string;

y : record a, b : byte end {y}

end;

begin with x, y do begin

writeln(‘Введите через пробел поля a и b записи y - целое от 0 до 255’);

readln(a, b); {Вместо x.y.a и x.y.b}

writeln(‘Введите поле c записи x - строку символов’);

readln(с); end; {Вывод сделаем без оператора присоединения}

writeln(‘Поля записи x: ’, x.c, ‘ и поля записи y: ’, x.y.a:4, x.y.b:4) end.

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

type <имя типа> = record

<поле1> : <тип1>; … Фиксированная

<полеj> : <типj>; часть записи

case <переменная> : <тип> of Вариантная

ci, ck : (<поле> : <тип>; … часть

<поле> : <тип>); … записи

cp, cq : (<поле> : <тип>; …

<поле> : <тип>) end;

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

type figura = (cvadrat, treug, krug);

param = record {параметры фигуры}

x, y : real; {Фиксированная часть - точка привязки фигуры}

case figura of

cvadrat : (storona : real);

treug : (storona1, storona2, ugol : real);

krug : (radius : real) end;

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

Билет №24

Операторы break и continue

Бывает, что цель выполнения цикла достигается раньше, чем он будет прекращен по условию выхода. Так, например, в программе для определения простоты числа цикл будет выполняться n div 2-1 раз, хотя то, что число не является простым, может быть обнаружено на первых шагах цикла. Чтобы уменьшить количество шагов цикла, можно воспользоваться оператором goto, либо сформировать сложное условие выполнения (прекращения) цикла.

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

Операторы break и continue выполняются в любом из видов циклов (repeat, while, for) и действительны только для внутреннего цикла. Например, если нужно обеспечить принудительный выход из двойного цикла, оператор break должен быть расположен как во внутреннем, так и во внешнем цикле. Операторы break и continue по сути являются видоизмененными операторами goto с известной точкой, в которую осуществляется переход.

В примере у пользователя пять раз запрашивается число только в том случае, если он не вводит ноль.

var

num: real;

i: integer;

begin

for i := 1 to 5 do begin

write ('Введите число: ');

readln (num);

if num = 0 then

break;

writeln (num)

end;

 

readln

end.

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

var

num, sum: real;

i: integer;

begin

sum := 0;

 

for i := 1 to 5 do begin

write ('Введите число: ');

readln (num);

if num < 0 then

continue;

sum := sum + num

end;

write (sum:10:2);

readln

end.

Запись с вариантами

type v = record

a: type1

b: type2

……

case n: typen of

c1:(t11: type11;

t12: type12; …);

c2:(t21: type21;

t22: type22; …)end;

var z: v;

Здесь z – переменная типа v; n – переменная, называемая переключателем; typen – тип переменной n.

Этому же типу должны принадлежать метки c1 и c2. Каждой метке соответствует набор полей t11, …. Эти поля являются компонентами варианта.

Если какой-либо метке c вообще не соответствуют поля, то пишут c…: ( );

Замечания:

1. Любая запись (record) может иметь только одну вариантную часть (case).

2. Вариантная часть должна помещаться после постоянной части.

3. Среди идентификаторов полей не должно быть одинаковых.

Обращение к компоненте z.tij записи z происходит так:

1. Присваивается соответствующее значение c… переключателю n. В зависимости от значения n переменная z, помимо полей a, b, …, содержит те поля, которые соответствуют той метке c…, с какой совпадает значение n.

2. Выполняется операция с компонентой z.tij.

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

Эта информация может быть описана, например, записью person.

Пусть переменная типа kind может иметь одно из значений («женат», «холост»).

kind = (married, single);

person = record

name: string;

datebirth: date;

case yesno: kind of

married: (name1: string; date1: date);

single: ()

end;

Здесь name – строка символов; datebirth – запись, содержащая дату рождения; yesno – переключатель типа kind, который может принимать одно из двух значений: married либо single; name1 – строка символов, содержащая фамилию супруга(и); date1 – запись, содержащая дату рождения; single – пустое поле.

Если персона в браке, то будет присутствовать поле married, если нет – поле single. Паскаль допускает вложение вариантов в типе record.

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

Пример.

type

kind = (married, single);

date = record

day: 1..31;

month: 1..12;

year: integer;

end;

person = record

name: string;

datebirth: date;

case yesno: kind of

married: (name1: string; date1: date);

single: ()

end;

var

p: person;

begin

with p do begin

yesno := married;

name := 'panin';

with datebirth do begin

day := 14;

month := 5;

year := 1962

end;

case yesno of

married: begin

name1 := 'panina';

with date1 do begin

day := 30;

month := 12;

year := 1968

end; end; end;end;

with p do

write(' ', name);

with p.datebirth do

writeln(' ', day, '/', month, '/', year);

with p do

write(' ', name1);

with p.date1 do

write(' ', day, '/', month, '/', year);

readln end.

Наряду с обычными константами Турбо Паскаль допускает использование типизированных констант. Название "типизированная константа" не совсем удачное (а точнее совсем не удачное), поскольку, по своим характеристикам, она (типизированная константа) скорее переменная нежели константа. Вот эти характеристики:

• при описании типизированных констант явно указывается их тип;

• типизированные константы могут менять свое значение по ходу выполнения программы также как обычные переменные;

• типизированные константы описываются в разделе CONST и также, как простые константы, получают при описании (начальное) значение;

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

Синтаксис описания типизированных констант:

CONST   ИмяКонстанты1 : ИмяТипа1 = Значение1;   ИмяКонстанты2 : ИмяТипа2 = Значение2;

Примеры описания типизированных констант:

CONST   R : Real = 19.875;   I : Integer = -10;   Title : String = 'Заголовок';   SpecChar : Char = '\';   { стартовое значение можно задать масиву }   Vector : array[1..5] of Byte = (1,3,5,7,9);   { а можно и множеству }   Indexes : set of Byte = [1..10,20,100..200];

Важно: Поскольку типизированные константы это, на самом деле, обычные переменные, их нельзя использовать в описаниях других констант и типов. Следующий фрагмент показывает пример НЕПРАВИЛЬНОГО использования типизированных констант:

CONST   Min : Byte = 0;   Max : Byte = 1;   e : Real = 2.7;   Interval = Max - Min + 1; { Ошибка }   e2 = e*e;                 { Ошибка } VAR   V : array[Min..Max] of Integer; { Ошибка }

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

  x := 0; y := 0; ch := 'n';   flag := FALSE;   a[1] := 1; a[2] := 0; a[3] := -1; a[4] := 0; Более элегантное решение этой проблемы - переменная со стартовым значением: вводим идентификатор переменной, указываем ее тип и тут же (!) определяем ее начальное значение.