1 вопрос.

Этапы решения задач с помощью компьютера.

I.         Постановка задачи.

II.      Анализ условия задачи.

•       Входные/выходные данные/промежуточные переменные.

•       Условия (ограничения).

•       Математическая модель (решение задачи в общем виде).

III.   Составление алгоритма (в словесной форме или в форме блок-схемы).

IV.   Написание программы.

V.     Тестирование и отладка программы.

VI.   Анализ результатов. Если результат не соответствует ожидаемому, перейти ко второму этапу.

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

2 вопрос.

Структура программы на языке Паскаль. Пример простейшей программы.

Программа состоит из заголовка, раздела описания и раздела операторов. 

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

program n;

Здесь n – имя программы. Имя программы не должно начинаться с цифры и не должно содержать пробелы и специальные символы.

Заголовка может и не быть или он может быть без параметров.

2.       Раздел описания.

Блок программы состоит из шести разделов, следующих в строго определенном порядке:

•       раздел подключения модулей (uses);

•       раздел меток (label);

•       раздел констант (const);

•       раздел типов (type);

•       раздел переменных (var);

•       раздел процедур и функций;

3.       Раздел операторов. Begin

 Список операторов; End.

Раздел действий должен присутствовать всегда, остальные разделы могут отсутствовать.

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

Раздел меток (label)

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

Общий вид:

label l1, l2, l3…; здесь l1, l2, l3 – метки.

Пример. label 5, 10, 100;

Метка отделяется от оператора двоеточием.

Пример. Пусть оператор a:= b имеет метку 20. Тогда этот оператор выглядит так: 20: a:= b;

Раздел переменных (var)

Пусть в программе встречаются переменные v11, v12,…; все они должны быть описаны следующим образом:

var v11, v12,…: type1;       v21, v22,…: type2; … здесь v11, v12,… - имена переменных; type1 – тип переменных v11, v12,…; type2 – тип переменных v21, v22,….

Пример. var k, i, j: integer; a, b: real;

Каждая переменная должна быть описана до ее использования в программе и отнесена к одному и только одному типу. Названия разделов (const, type, var…) указываются только один раз.

Пример. 

var a: real;

      b: real;

Таким образом, в разделе var вводится имя каждой переменной и указывается, к какому типу эта переменная принадлежит. Тип переменной можно задать двумя способами: указать имя типа (например, real, color и т.д.), либо описать сам тип, например: array[1..16] of char.

3 вопрос.

Типы данных языка Паскаль.

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

Типы данных делятся на

I.        Простые типы: порядковые, вещественные.

1.        Порядковый тип в свою очередь делится на:

а) целые типы;

б) логический тип или булевский тип;

в) символьный тип;

г) перечисляемые типы;

д) ограниченные типы или тип-диапазон.

2.        Вещественные типы

II.     Составные типы:

1.        структурированные типы;

•       регулярные типы (массивы);

•       комбинированные типы (записи);

•       множественные типы;

•       файловые типы;

2.        указатели;

3.        строки;

4.        процедурные;

5.        объекты;

6.        классы; 7. варианты.

4 вопрос.

Переменные, константы в языке Паскаль.

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

Константа — это идентификатор, который обозначает некоторую не меняющуюся величину заданного программистом типа. Константы объявляются в соответствующем разделе — разделе const.

В среде Турбо Паскаль представлены следующие виды констант:

•     Целочисленные константы определяются числами, записанными либо в десятичной, либо в шестнадцатеричной системе счисления. Эти числа должны использоваться без десятичной точки. Пример: const a=5;

•     Вещественные константы могут быть определены числами, записанными в десятичной системе счисления с применением десятичной точки. Пример: сonst b=21.43;

•     Символьная константа - некоторый символ, заключенный в апострофы. Пример: const c='w';

•     Строковые константы — последовательность любых символов, которая заключена в апострофы. Пример: const d='stroka';

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

Примеры: god: integer = 2012; simvol: char = '!';

tip: real = 57.23;

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

program prost; const  m = 11;                   {константа m не меняет исходное значение} n: integer  = 4;       {типизированная константа n} var x,y,f:integer;          {переменные x и y имеют целый тип} begin writeln('Введите x'); readln(x); writeln('Введите y'); readln(y); f:=m*exp(n*ln(x+y));                               {меняется значение переменной x} writeln('Значение функции равно',f);   {выводим значение f на экран} end.

5 вопрос.

Операторы в языке Паскаль (понятие, классификация)

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

Все операторы можно разбить на две группы. Одну группу образуют операторы, которые в своем составе (т.е. в последовательности символов, образующей запись оператора) не содержат других операторов. Операторы этой группы назовем основными операторами. К ним относятся: оператор присваивания, оператор процедуры, оператор перехода, пустой операторы паскаль. Другую группу образуют операторы, в состав которых входят другие операторы. Операторы этой группы будем называть производными операторами. К этой группе относятся следующие типы операторов: составной оператор, выбирающий оператор, оператор цикла, оператор присоединения. В записи алгоритма могут использоваться последовательности из этих операторов, без ограничений на их количество. Все операторы в такой последовательности отделяются друг от друга разделителем ” ; ” (точка с запятой) — тем самым производится четкое разбиение всей записи на отдельные операторы. Таким образом, если обозначить через S любой допустимый оператор, то в общем случае такая последовательность будет иметь вид

S; S; .. . ; S

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

Классификация операторов

6 вопрос.

Ввод-вывод данных в языке Паскаль. Примеры.

В Паскале ввод осуществляется с помощью процедур read() и readln(), а вывод - благодаря write() и writeln(). Процедуры, которые имеют окончание ln, после своего выполнения переводят указатель на новую строку.

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

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

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

В процедуры ввода можно передавать не один фактический параметр, а множество.

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

Существуют особенности ввода данных с помощью операторов read() и readln(). Если используются подряд несколько операторов read(), то вводимые данные можно разделять всеми допустимыми способами. При использовании нескольких вызовов readln() каждый последующий срабатывает только после нажатия Enter. Программа ниже иллюстрирует это. Комментарии поясняют последовательность возможных действий при вводе данных.

var         a,b,c,d: integer; begin         read(a); // a -> <space> or <tab> or <enter> -> b         read(b);

        writeln(a,' ',b);

        readln(c); // c ->  only <enter> -> d         readln(d);

        writeln(c,' ',d);

        read(a,b); // a -> <space> or <tab> or <enter> -> b         writeln(a,' ',b);

        readln(c,d); // c -> <space> or <tab> or <enter> -> d         writeln(c,' ',d); end.

Форма представления значений в поле вывода соответствует типу переменных и выражений:   целочисленные величины выводятся как целые десятичные числа,

•      величины действительного типа представляются как действительные десятичные числа с десятичным порядком,

•      величины символьного типа и строки выводятся в виде символов, величины логического типа - в виде true и false (логические константы).

Оператор вывода создает возможность задать ширину поля вывода для каждого элемента списка вывода, которые будут иметь вид: А:К, где А - строка или выражение, К - выражение либо целочисленная константа. Возникают две ситуации при этом:

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

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

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

Пример, показывающий запись операторов вывода:

program vyvod; var rM, rN: real; iS, iT:integer; bZ, bL: boolean; chY, chD, chH, chX: char; begin

        . . . 

writeLn(rM, rN:10:2); writeLn(iS, iT:8); writeLn(bZ, bL:8); writeLn(chY, chD, chH, chX); end.

Вопрос 7.

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

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

Можно выделить два типа разветвляющихся алгоритмов:

                                                           Неполное ветвление                       Полное ветвление

В качестве примера приведём следующий:

Я лежу на диване. За окном идёт дождь.

а) Если дождь прекратиться, то я пойду гулять.

Здесь никаких действий в случае невыполнения условия не происходит!

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

На Паскале условный оператор записывается следующим образом:

Знак "точка с запятой" не ставится перед служебным словом Else, но операторы в группах, естественно, отделяются друг от друга этим знаком. Во всех случаях операторные скобки «Begin-End» нужны только в том случае, если внутри конструкции «If» содержится более одного оператора.

Пример из курса математики.

Необходимо вычислить значение выражения y=1/x. Известно, что данная функция не всегда имеет значение, то есть не для всех значений аргумента существует значение результата. Наша задача так составить алгоритм, чтобы исполнитель ни в коем случае не встал в тупик, даже при получении нуля в качестве аргумента. Сформулировать это на естественном языке не трудно:

1.  Получить значение x.

2.  Если x=0, то сообщить, что выражение значения не имеет, иначе — вычислить y как 1/x.

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

В простых условиях могут применяться знаки операций сравнения: >(больше), <(меньше), =(равно), <>(не равно), >=(больше или равно), <=(меньше или равно).

     Примеры простых условий:      A=5 {Значение переменной А равно 5}

      (C+D3)>=(D1*(45-2)) {Значение выражения в левой части больше либо равно значению выражения из правой части}

      S<>'ABC' {Значение переменной S не равно строковой константе 'ABC'}

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

Program Example;

Var A,B,C : Real; {A,B - для хранения аргументов, C - результат}

Begin

Writeln('Введите два числа');

Readln(A,B);                            {Вводим аргументы с клавиатуры}

If A>B Then C:=A Else C:=B; {Если A>B, то результат — A, иначе результат — B}

Writeln(C);                               {Выводим результат на экран} End.

8 вопрос.

Оператор цикла for в языке Паскаль. Пример использования.

Цикл с параметром

Цикл с параметром предназначен для повторения некоторого участка программы заданное (известное заранее) число раз. Для организации этого цикла используется оператор цикла с параметром, имеющий вид:

For <параметр цикла> := <начальное значение> To <конечное значение> Do Begin

<тело цикла>; End;

где for - для; to - до; do - выполнить;

Операторные скобки «Begin-End» нужны только в том случае, если тело цикла содержит более одного оператора.

<параметр цикла> — переменная целого типа;

<начальное значение> и <конечное значение> — арифметические выражения целого типа; <тело цикла> — один или несколько операторов языка Паскаль.

В отличие от других языков программирования, в Паскале шаг изменения параметра строго постоянен и равен 1. Такой цикл называют прямым. Единственное исключение из этого правила составляет цикл с шагом (-1), который имеет следующий вид:

For <параметр цикла> := <начальное значение> DownTo <конечное значение> Do Begin

<тело цикла>;

End;

Этот цикл называют обратным.

В прямом цикле начальное значение меньше конечного, в обратном — начальное значение больше конечного.

Например,

For i := 1 To 10 Do write(i); — выводит на экран строку 12345678910

For i := 10 DownTo 1 Do write(i); — выводит на экран строку 10987654321

9 вопрос.

Оператор цикла while в языке Паскаль. Пример использования.

Цикл while является циклом с предусловием. В заголовке цикла находится логическое выражение. Если оно возвращает true, то тело цикла выполняется, если false – то нет.

                                                                      Цикл с предусловием

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

var     i, n: integer;

 begin     write ('Количество знаков: ');

    readln (n);

     i := 1;

    while i <= n do begin         write ('(*) ');         i := i + 1     end; end.

Задача: вычислить сумму ряда 1+1.5+2+2.5+3+3.5+ .. + 30 program example-while;

var    sum:real;    n:real;

BEGIN

   sum:=0;    n:=1;    while n < =30 do         begin            sum:=sum+n;            n:=n+0.5;

        end;

   writeln('Сумма равна: ',sum); END.

10 вопрос.

Оператор цикла repeat в языке Паскаль. Пример использования.

Цикл с постусловием

В цикле repeat логическое выражение стоит после тела цикла. Причем, в отличие от цикла while, здесь всё наоборот: в случае true происходит выход из цикла, в случае false – его повторение.

var     i, n: integer; begin     write ('Количество знаков: ');

    readln (n);     i := 1;     repeat         write ('(*) ');         i := i + 1     until i > n; end.

В примере, даже если n будет равно 0, одна звездочка все равно будет напечатана.

Program test2;

Var b:Real; Begin b:=100;

Repeat b:=b/2;

Until b<10; Writeln(b,' '); End.

11 вопрос.

Массивы. Понятие, разновидности, способы описания. Доступ к элементам массива. 

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

Общая форма описания одномерного массива на Паскале такая:

var <имя массива>: array [<нижняя граница индекса .. верхняя граница индекса>] of <тип массива> Слово "array" буквально переводится как "массив". Границы индекса могут быть любыми целыми числами. Важно, чтобы нижняя граница была меньше верхней границы. Например: var T: array [1..12] of real;

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

Type

Mass=array[1..n] of Integer;

Var

A,B:Mass;

Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента.

Простой массив является одномерным. Он представляет собой линейную структуру.

Пример программы, задающей массив из десяти случайных целых чисел от 0 до 100. Var

M:array[1..10] of Integer;

i:Byte;

Begin

Randomize;

For i:=1 to 10 do

Begin

M[i]:=random(100);

Write(M[i],’ ‘); End; End.

12 вопрос.

Основные способы сортировки массивов.

Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов.

Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:

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

•       количество сравнений элементов;

•       количество перестановок, выполняемых при сортировке.

Существует три основных способа сортировки массивов:

1.      Метод пузырька.

2.      Метод вставки.

3.      Метод сортировки посредством выбора.

Метод пузырька

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

При этом:

•       если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;

•       при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним.

В результате наибольший элемент оказывается в самом верху массива.

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.

Теперь можно привести текст программы упорядочения массива M[1..N]:

 begin

   for j:=1 to N-1 do      for i:=1 to N-j do

        if M[i] > M[i+1] then swap(M[i],M[i+1]) end;

procedure swap(var x,y: ...);  var t: ...;  begin     t := x;     x := y;     y := t  end;

Сортировка вставками

Второй метод называется метод вставок, т.к. на j-ом этапе мы "вставляем" j-ый элемент M[j] в нужную позицию среди элементов M[1], M[2],. . ., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.

Сказанное можно записать следующим образом:

нц для j от 2 до N переместить M[j] на позицию i <= j такую, что

M[j] < M[k] для i<= k < j и

либо M[j] >= M[i-1], либо i=1 кц

Чтобы сделать процесс перемещения элемента M[j], более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0], чье значение будет заведомо меньше значения любого из "реальных" элементов массива (как это можно сделать?). Мы обозначим это значение через -оо.

Если барьер не использовать, то перед вставкой M[j], в позицию i-1 надо проверить, не будет ли i=1. Если нет, тогда сравнить M[j] (который в этот момент будет находиться в позиции i) с элементом M[i-1].

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

begin

   M[0] := -oo;    for j:=2 to N do     begin        i := j; 

        while M[i] < M[i-1] do           begin 

              swap(M[i],M[i-1]);               i := i-1           end     end  end;

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j-ом этапе выбирается элемент наименьший среди M[j], M[j+1],. . ., M[N] (см. процедуру FindMin) и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j], M[j+1],. . ., M[N]будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1

    выбрать среди M[j],. . ., M[N] наименьший элемент и     поменять его местами с M[j] кц

Более точно:

begin

   for j:=1 to N-1 do     begin 

        FindMin(j, i);         swap(M[j],M[i])     end  end;

В программе, как уже было сказано, используется процедура FindMin, вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex:

procedure FindMin(startindex: integer; var lowindex: integer); var lowelem: ...; u: integer;  begin

   lowindex := startindex;    lowelem := M[startindex];    for u:=startindex+1 to N do      if M[u] < lowelem then         begin

          lowelem := M[u];           lowindex := u         end

 end;