Главная страница
Навигация по странице:

  • На сколько отрезков разбивать исходный интервал [a, b], a = 0,4, b = 1,6

  • Чем объясняется хорошее совпадение результатов при замене криволиней- ной фигуры лишь одним прямоугольником

  • Лекциям по курсу Информатика


    Скачать 3.84 Mb.
    НазваниеЛекциям по курсу Информатика
    Анкорlekcii_shiryaevoy.pdf
    Дата11.07.2018
    Размер3.84 Mb.
    Формат файлаpdf
    Имя файлаlekcii_shiryaevoy.pdf
    ТипЛекция
    #19640
    страница7 из 9
    1   2   3   4   5   6   7   8   9
    Пример 6.1. Что будет выведено на экран в результате работы следующей программы?
    Использование подпрограмм
    1
    program ProcVar4;
    2
    procedure Proc1(x, y : Integer);
    3
    begin
    4
    x := x * y;
    5
    end;
    6
    procedure Proc2(var x : Integer; y : Integer);
    7
    begin
    8
    x := x * y;
    9
    end;
    10
    var c, d : Integer;
    11
    begin
    12
    c := 1;
    d := 4;
    Proc1(c, c + d);
    WriteLn(c, d:3);
    13
    c := 1;
    d := 4;
    Proc2(c, c + d);
    WriteLn(c, d:3);
    14
    end.
    Для каждого параметра задаются его имя, тип и способ передачи.
    В Pascal существует 4 вида параметров:
    — значения;
    — переменные;
    — константы;
    — нетипизированные параметры.
    185

    10.6.1
    Параметры-значения
    Параметр-значение получает свое значение из главной программы при вызове подпрограммы.
    
    
    ¨
    ©
    В подпрограмму передается копия значения аргумента.
    Механизм передачи:
    Сегмент стека
    Область параметров копируется переменная, передаваемая
    Ячейка памяти,
    в которой хранится
    Сегмент стека
    Область параметров в подпрограмму значение переменной
    Рис. 6.2. Механизм передачи: слева — при вызове подпрограммы; справа — по заверше- нии работы подпрограммы
    Подпрограмма работает с копией
    =⇒
    доступа к ячейке,
    где хранится сама переменная, не имеет.
    Способ передачи параметров:
    передача по значению
    Используется только для величин, которые не должны измениться после выполнения подпрограммы, то есть для ее исходных данных.
    186

    При вызове подпрограммы на месте параметра, передаваемого по зна- чению, может находиться выражение.
    Важно:
    Тип выражения должен быть совместим по присваива- нию с типом параметра.
    Совместимость по присваиванию
    1
    function Summa(A, B: Real): Real;
    2
    const MyPi = 3.14;
    3
    begin
    4
    Summa := (A + B) * MyPi;
    5
    end;
    6
    begin
    7
    Writeln(Summa(2.5, Pi));
    8
    Writeln(Summa(4, Trunc(Pi)));
    9
    end.
    Недостатки передачи по значению:
    — затраты времени на копирование параметра;
    — затраты памяти в стеке и опасность его переполнения, когда речь идет о параметрах, занимаемых много места, например, массивах большо- го размера. Поэтому более правильно использовать для передачи исходных данных в подпрограмму параметры-константы (см. п.
    10.6.3
    ).
    187

    10.6.2
    Параметры-переменные
    Признаком параметра-переменной является ключевое слово var перед описа- нием параметра.
    Механизм передачи:
    (* см. конспект *)
    Подпрограмма работает непосредственно с переменной из вызывающей программы
    =⇒
    может ее изменить.
    Способ передачи параметров:
    передача по адресу
    Результаты работы подпрограммы должны быть только параметрами- переменными.
    При вызове подпрограммы на месте параметра-переменной может нахо- диться только ссылка на переменную точно того же типа.
    Совместимость по типу
    1
    procedure Summa(A, B: Real; var Sum: Real);
    2
    begin
    3
    Sum := A + B;
    4
    end;
    5
    var A1
    : Integer;
    6
    MySum
    : Real;
    7
    begin
    8
    A1 := 5;
    9
    Summa(A1, 2*A1, MySum);
    10
    Writeln(MySum);
    11
    end.
    . Исходные данные в подпрограмму передавать по адресу не рекомендуется,
    чтобы исключить возможность их непреднамеренного изменения.
    188

    10.6.3
    Параметры-константы
    Признаком параметра-константы является слово const перед описанием пара- метра, например,
    procedure Summa(const A, B: Integer; var Sum: Real);
    Механизм передачи:
    параметры-константы передаются по адре- су, но доступ к ним обеспечивается только для чтения. Поэтому опасность переполнения стека и затраты, связанные с копированием и раз- мещением параметров, исключаются.
    Если данные передаются как параметры-константы, изменять их в подпрограмме нельзя.
    Используются для передачи в подпрограмму исходных данных.
    Возможно для параметров-значений
    1
    procedure Summa(A, B: Integer; var Sum: Real);
    2
    begin
    3
    A := A div 2;
    Sum := A + B;
    4
    end;
    Невозможно для параметров-констант
    1
    procedure Summa(const A, B: Integer; var Sum: Real);
    2
    begin
    3
    A := A div 2; (* вызовет ошибку! *)
    4
    Sum := A + B;
    5
    end;
    При вызове подпрограммы на месте параметра-константы может быть за- писано выражение, тип которого совместим по присваиванию с типом параметра.
    Параметры составных типов (массивы, записи, строки) предпочтительнее пе- редавать как константы.
    189

    10.7
    Параметры–процедуры и параметры–функции
    (Процедуры и функции дальнего вызова)
    Пример 7.1. Подпрограмма для вычисления среднего значения функции f (x)
    на заданном интервале требует в качестве параметров интервал и имя реальной функции f (x).
    Пример 7.2. Подпрограмме для вычисления интеграла b
    a f (x) dx требуются значения a, b и функция f (x).
    Для использования в качестве параметра подпрограммы имени процедуры или функции необходимо описать тип процедурного (функционального) типа.
    Процедурный тип описывает класс процедур или функций, имеющих однотипные заголовки.
    Определение процедурного типа аналогично заголовку подпрограммы, но при этом имя подпрограммы не задается.
    Описание функционального и процедурного типов
    1
    type
    Proc1 = procedure;
    2
    Proc2 = procedure (a, b : Real;
    var c : Real);
    3
    Fun1
    = function: Real;
    4
    Fun2
    = function (x : Real): Real;
    Имена формальных параметров не являются существенными в этих описани- ях.
    Важно только их количество, порядок следования и типы, а также тип результата для функции. Введенный процедурный тип может быть использован при описании формальных параметров подпрограмм. Например,
    Заголовки подпрограмм с параметрами-подпрограммами procedure Menu(x, y : Integer; ShowM : Proc1);
    procedure Menu2(x : Integer; F : Fun2);
    function Summa(eps : Real;
    F : Fun2);
    190

    Если подпрограмма имеет параметр процедурного типа, то при её вызове в качестве фактического параметра используется процедура (функция), заго- ловок которой соответствует заголовку, описанному в процедурном типе. Это должна быть обязательно пользовательская процедура (функция) и при ее описании следует за заголовком указать служебное слово far.
    Пример 7.3. Будем вычислять функцию
    G = F (x, y)z,
    где z ∈ Z, F (x, y) — некоторая функция, x, y ∈ R.
    Демонстрация подпрограмм с параметрами-функциями
    1
    program DemoFar;
    2
    (* см. конспект *)
    Функции Sum и Sum2 можно использовать и обычным способом, например, на- печатать результат работы
    WriteLn(’Summa = ’, Sum(a1, b1);
    . Вместо использования служебного слова far можно указывать директи- ву компилятора, позволяющую управлять типом вызова процедур и функций:
    {$F+} — использовать дальнюю модель вызова (FAR), {$F-} — использовать ближнюю модель вызова (NEAR).
    {$F+}
    function Sum(a, b : Real): Real;
    begin
    Sum := a + b;
    end;
    {$F-}
    По умолчанию установлена {$F-}.
    Директивы компилятора
    — комментарии специального вида, с помо- щью которых программист управляет работой компилятора.
    Пример 7.4. Заменим в предыдущем примере параметр-функцию параметром процедурного типа.
    191

    Описание процедурного типа type Proc1 = procedure (a, b : Real; var Rez: Real);
    Описание процедуры Sum procedure Sum(a, b : Real; var Rez: Real); far;
    begin
    Rez := a + b;
    end;
    Описание процедуры Sum2
    procedure Sum2(a, b : Real; var Rez: Real); far;
    begin
    Rez := sin(a) + sin(b);
    end;
    Описание функции с параметром-процедурой function Prod(a, b : Real;
    PP : Proc1;
    c : Integer): Real;
    var Rez0 : Real;
    begin
    PP(a, b, Rez0);
    Prod := Rez0 * c;
    end;
    Тело программ остается прежним!!
    var a1, b1 : Real;
    c1
    : Integer;
    begin a1 := 0.5;
    b1 := 0.2;
    c1 := 2;
    WriteLn(Prod(a1, b1, Sum, c1));
    WriteLn(Prod(a1, b1, Sum2, c1));
    end.
    192

    10.7.1
    Численное интегрирование
    С геометрической точки зрения интеграл b
    a f (x) dx
    — это площадь криволинейной фигуры, ограниченной линиями: осью абсцисс,
    графиком функции y = f (x), прямыми x = a, x = b.
    На практике фигуру сложной формы заменяют более простой, например, пря- моугольником или трапецией:
    6
    - b
    x y
    a b
    y = f (x)
    r r
    r a+b
    2 6
    - b
    x y
    a b
    y = f (x)
    r r
    b h
    c d
    S
    трап
    =
    c + d
    2
    h
    При реальных вычислениях используются составные формулы численного ин- тегрирования (ЧИ), когда отрезок интегрирования [a, b] разбивается на n ча- стей с шагом h = (b − a)/n, т. е. расстояние между двумя соседними узлами равно h x
    k+1
    − x k
    = h,
    ∀ k.
    - x
    0
    = a x
    1
    x n−1
    x n
    = b
    193

    Формула центральных прямоугольников:
    -
    6
    x y
    y = f (x)
    a x
    1
    x
    2
    x n−1
    b b
    b b
    b b
    r r
    r r
    r r
    I = h n−1
    k=0
    f x
    k
    + x k+1 2
    Формула трапеций:
    -
    6
    x y
    y = f (x)
    a x
    1
    x
    2
    x n−1
    b b
    b b
    b b
    b r
    r r
    r r
    r
    I =
    h
    2
    f (x
    0
    ) + 2
    n−1
    k=1
    f (x k
    ) + f (x n
    )
    194

    Геометрический смысл численных методов интегрирования
    (* см. конспект *)
    Демонстрация интегрирования разными методами (Maple)
    [> restart;
    [> II := Int(f(x), x=a..b);
    [> a:=0.4:
    b := 1.6:
    [> f(x) := sin(x*x);
    [> II = evalf(II);
    [> with(student);
    [> n := 2;
    # число прямоугольников
    [> evalf(middlesum(f(x), x=a..b, n));
    middlebox(f(x), x=a..b, n);
    [> evalf(leftsum(f(x), x=a..b, n));
    leftbox(f(x), x=a..b, n);
    [> evalf(rightsum(f(x), x=a..b, n));
    rightbox(f(x), x=a..b, n);
    Численное интегр. методом прямоугольников
    [> evalf(middlesum(f(x), x=a..b, n));
    Результат:
    число.
    Геометрическая интерпретация числ. интегр. методом прямоугольников
    [> middlebox(f(x), x=a..b, n);
    Результат:
    рисунок.
    195

    Компьютерный эксперимент
    Точное значение интеграла
    1,6 0,4
    sin x
    2
    dx = 0,8239746151.
    ?:

    На сколько отрезков разбивать исходный интервал [a, b], a = 0,4, b = 1,6?
    Ответ зависит от того, с какой точностью требуется получить результат.
    n = 1
    I
    1
    ≈ 1,009765182
    n = 2
    I
    2
    ≈ 0,8781177234 196

    На практике используют составные формулы интегрирования и для оценки погрешности поступают следующим образом:
    1) Вычисляется интеграл I
    n
    — отрезок интегрирования разбивается на n ин- тервалов;
    2) Вычисляется интеграл I
    2n
    — отрезок интегрирования разбивается на 2n ин- тервалов (шаг разбиения при этом уменьшается в два раза);
    3) ε
    a
    — абсолютная погрешность:
    I
    2n
    − I
    n
    3
    ε
    a
    197

    10.7.2
    Реализация численного интегрирования на языке Паскаль
    Процедура для вычисления b
    a f (x) dx (метод прямоугольников)
    procedure IntRect(a, b : Real;
    FF : Func;
    var Int: Real);
    begin
    (* см. конспект *)
    end;
    Описание функционального типа type
    Func = function (x : Real): Real;
    Описание подинтегральной функции f
    1
    (x) = sin x
    2
    function Sin0(x : Real): Real;
    far;
    begin
    Sin0 := sin(x*x);
    end;
    Описание подинтегральной функции f
    2
    (x) = sin x function Sin01(x : Real): Real;
    far;
    begin
    Sin01 := sin(x);
    end;
    В качестве тестового примера возьмем интеграл от функции f (x) = x:
    0,6 0,4
    x dx =
    x
    2 2
    0,6 0,4
    =
    0,6 2
    2

    0,4 2
    2
    =
    0,36 2

    0,16 2
    = 0,18 − 0,08 = 0,1.
    Описание тестовой функции function
    Test0(x : Real): Real;
    far;
    begin
    Test0 := x;
    end;
    198

    Численное интегрирование (полная программа)
    1
    program Integro;
    2
    type
    Func = function (x : Real): Real;
    3
    function
    Test0(x : Real): Real;
    far;
    4 5
    function Sin0(x : Real): Real;
    far;
    6 7
    function Sin01(x : Real): Real;
    far;
    8 9
    procedure IntRect(a, b : Real;
    FF : Func;
    var Int: Real);
    10 11
    var IRect, a0, b0 : Real;
    12
    begin
    13
    a0 := 0.4;
    b0 := 0.6;
    14
    IntRect(a0, b0, Test0, IRect);
    15
    WriteLn(’Test =’, IRect:8:5);
    16
    IntRect(a0, b0, Sin0, IRect);
    17
    WriteLn(’Int1 =’, IRect:8:5);
    18
    IntRect(a0, b0, Sin01, IRect);
    19
    WriteLn(’Int2 =’, IRect:8:5);
    20
    end.
    Результат работы программы:
    Test = 0.10000
    Int1 = 0.04948
    Int2 = 0.09589
    Точные значения интегралов:
    0,6 0,4
    sin x
    2
    dx = 0,05004187240;
    0,6 0,4
    sin x dx = 0,09572537909.

    Чем объясняется хорошее совпадение результатов при замене криволиней- ной фигуры лишь одним прямоугольником?
    (* Ответ см. в конспекте. *)
    199

    Глава 11
    Массивы
    Массив
    — упорядоченная последовательность однотипных данных. От- дельные данные называются элементами массива
    . Тип элементов мас- сива называется базовым
    В языке Pascal массив содержится в последовательном наборе ячеек памяти,
    по одному элементу на ячейку.
    Все элементы массива являются одинаково доступными и могут выбираться произвольно. К любому элементу массива можно обратиться, задав его ин- декс
    , который определяет относительную позицию элемента массива.
    Индексы упорядочены по возрастанию.
    Элементы
    53 −47 35 11 0 13 11
    Индексы (пример 1)
    0 1
    2 3
    4 5
    6
    Индексы (пример 2)
    1 2
    3 4
    5 6
    7
    Массив, содержащий 7 элементов
    Размерностью массива называется число индексов массива.
    Массив, имеющий 1 индекс — одномерный массив (вектор; 1D массив); 2 индек- са — двумерный массив (матрица; 2D массив); 3 индекса — трехмерный массив
    (параллелепипед, заполненный данными; 3D массив).
    Массивы нужны тогда, когда для решения задачи необходимо хранение последовательности значений.
    Но, например, в программе для вычисления суммы
    500
    i=1
    a i
    массив не нужен:
    можно вводить числа по одному и накапливать сумму.
    200

    Характеристики массива:

    (* см. конспект *);
    11.1
    Объявление массивов
    Массив описывается в разделе var с использованием конструкции array[тип_индекса] of базовый_тип;
    базовый_тип — общий для всех элементов тип (любой стандартный или созданный пользователем); тип_индекса — любой из порядковых типов —
    Char, Boolean, перечислимый тип, тип-диапазон.
    В описании массива фиксируются способ индексации,
    тип элементов, длина массива.
    Пример 1.1. Предложение var B: array[1..5] of Integer;
    описывает 1D массив — вектор (b
    1
    , b
    2
    , . . . , b
    5
    ) — с именем B. Элементы массива имеют целый тип, диапазон допустимых значений индекса 1..5 — упорядочен- ный набор натуральных чисел 1, 2, . . . , 5.
    . Стандартные типы Real и Integer не могут быть использованы в каче- стве типа_индекса. Первый, потому что не относится к порядковым; второй —
    слишком обширный. На основе целого типа Integer обычно создаются типы диапазоны, широко применяемые при описании массивов.
    Примеры описаний массивов
    Правильно
    Число элементов
    Неправильно array[1..5] of Integer
    5
    array[Integer] of Integer array[’a’..’e’] of Real
    5
    array[Real] of Integer array[Char] of Real
    ?
    array[5..-5] of Char array[Boolean] of Char
    ?
    array[0.5..1.5] of Real
    201

    11.2
    Индексы массивов
    Доступ к отдельным элементам массива осуществляется при помощи индексов:
    b[3], b[i].
    Индекс должен быть совместим по присваиванию с типом индекса,
    указанным в описании массива.
    . Функции Low и High в случае массивов возвращают младшее и старшее значения в диапазоне индексного типа массива.
    11.3
    Тип-массив
    Объявление массива без предварительного объявления его типа, т. е., например,
    в виде var B: array[1..5] of Integer;
    является плохой практикой программирования.
    В программе принято описать тип (до раздела описаний var)
    type Vector = array[1..5] of Integer;
    Тогда описание вектора b будет выглядеть следующим образом:
    var B : Vector;
    . Описание типа не инициирует выделение памяти для массива — это просто описание структуры массива. Выделение памяти для массива происходит при его описании в разделе var.
    202

    11.4
    Доступ к элементам массива
    Все элементы массива одинаково доступны. Обращаться к элементам массива можно либо в произвольном порядке, либо в последовательном.
    Пример 4.1 (
    плохой
    ). Пусть описаны три вектора:
    type Vector = array[1..5] of Integer;
    var A, B, C : Vector;
    Следующие операторы присваивания являются верными:
    Инициализация элементов массива (присваивание, ввод с клавиатуры)
    1
    begin
    2
    a[5] := 4;
    a[3] := 2;
    a[1] := 0;
    a[2] := 1;
    a[4] := 3;
    3
    b[1] := 4;
    b[2] := 2*a[5];
    b[3] := -b[2];
    4
    b[4] := b[2] Div 3;
    b[5] := 3;
    5
    Write(b[1], b[2], b[3], b[4], b[5]);
    6
    Read(c[1], c[2], c[3], c[4], c[5]);
    7
    end.
    Легко пропустить ошибку (где a[1]? a[4] инициализирован дважды)
    a[5] := 4;
    a[3] := 2;
    a[4] := 0;
    a[2] := 1;
    a[4] := 3;
    203

    Наиболее распространенный способ доступа к элементам массива при чтении и вводе —
    последовательный
    Для этой цели используются циклы (чаще, всего цикл с параметром for).
    Пример 4.2. Пусть описаны два 1D массива:
    Описание массивов
    1
    const Max = 5;
    { число элементов }
    2
    type Vector = array[1..Max] of Integer;
    3
    var A, C : Vector;
    4
    i : Integer;
    Инициализация массивов из предыдущего примера (было)
    a[1] := 0;
    a[2] := 1;
    a[3] := 2;
    a[4] := 3;
    a[5] := 4;
    Read(c[1], c[2], c[3], c[4], c[5]);
    Инициализация элементов массива в цикле
    5
    begin
    { тело программы }
    6
    for i := 1 to Max
    7
    a[i] := i - 1;
    { аналог присваивания значений элементам
    8
    вектора A }
    9
    for i := 1 to Max
    10
    Read(c[i]);
    { аналог ввода элементов вектора C }
    11
    end.
    204

    11.5
    Инициализация массивов при описании
    Инициализация массивов при описании возможна:
    в Borland Pascal 7
    в разделе описания констант, например,
    const A : array[1..5] of Char = (’k’, ’o’, ’t’, ’i’, ’k’);
    Количество констант должно точно соответствовать числу элементов мас- сива. Инициализированный таким образом массив в Borland Pascal 7 можно изменять, несмотря на то, что данные объявлены как константы.
    В Delphi в разделе описания переменных:
    var A : array[1..5] of Char = (’k’, ’o’, ’t’, ’i’, ’k’);
    . Массивы, описанные в разделе var главной программы, обнуляются авто- матически.
    Delphi — Инициализация массива при его описании
    1
    program DemoVec;
    2
    const Max = 5;
    3
    type Vec = array[1..Max] of Integer;
    4
    var i, j : Integer;
    5
    a : Vec = (1, -3, 4, -5, 6);
    6
    begin
    7
    for i := 1 to Max do
    Write(a[i]:3);
    { печать массива }
    8
    Writeln;
    9
    for i := 1 to Max do
    10
    begin
    11
    a[i] := Abs(a[i]);
    Write(a[i]:3);
    12
    end;
    13
    end.
    Результат работы:
    1 -3 4 -5 6
    1 3
    4 5
    6 205

    11.6
    Работа со всем массивом целиком
    Массив целиком можно только копировать или передавать в качестве па- раметра подпрограмме.
    Оператор вида
    A := B;
    { копирование массива B в массив A целиком }
    короче записывается и выполняется быстрее цикла for i := 1 to n do A[i] := B[i];
    . Копирование массива целиком может осуществляться только в том случае,
    если задействованные массивы относятся к одному типу-массиву. Например,
    при описаниях var A : array[1..5] of Integer;
    B : array[1..5] of Real;
    массив A можно скопировать в B только поэлементно. Писать оператор B := A
    нельзя!
    Обмен значениями между двумя массивами
    1
    program AtoB;
    2
    const Max = 5;
    3
    var A, B, Temp : array[1..Max] of Integer;
    4 5
    begin
    6
    ... { ввод элементов массивов A и B }
    7
    { обмен значениями между двумя массивами
    8
    с использованием третьего }
    9
    Temp := A;
    A := B;
    B := Temp;
    10 11
    end.
    206

    11.7
    Обработка подмассивов
    Постановка задачи.
    Составить программу, формирующую список студентов учебной группы.
    Проблема — разное количество студентов: в одной группе может учиться 15
    студентов, а в другой — 25. Если решать эту задачу с использованием массивов,
    то встает вопрос — какой длины массив может потребоваться? В подобных случаях массив создается достаточно обширный — такой, чтобы его хватило для обработки наибольшего набора данных.
    При заполнении массива ведется подсчет числа введенных элементов.
    Заполненный подмассив

    часть массива, содержащая данные.
    Длина заполненного подмассива соответствует числу элементов данных, ре- ально содержащихся в массиве.
    Обработка подмассивов
    1
    program Test;
    2
    const Max = 25;
    { макс. число студентов }
    3
    var A
    : array[1..Max] of string;
    4
    i, KS : Integer;
    { KS - реальное число студентов }
    5
    Fio
    : string;
    6
    begin
    7
    Write(’Введите фамилию или 1 (выход) ’);
    ReadLn(Fio);
    8
    KS := 0;
    9
    { условия продолжение цикла - если не введена
    10
    сигнальная метка и размер массива не превышен }
    11
    while (Fio <> ’1’) and (KS < Max) do
    12
    begin
    13
    KS := KS + 1;
    14
    a[KS] := Fio;
    { занесение данных в массив }
    15
    Write(’Введите фамилию или 1 ’);
    ReadLn(Fio);
    16
    end;
    17
    if KS = Max then WriteLn(’Массив полон’);
    18
    WriteLn(’Список студентов’);
    19
    for i := 1 to KS do
    WriteLn(i:3, ’ ’, a[i]);
    20
    end.
    207

    11.8
    Использование массивов в качестве параметров процедур-функций
    Пример 8.1. Написать программу для получения элементов массива случай- ным образом, печати массива и сравнения двух элементов массива.
    Решение.
    Создадим три подпрограммы:
    InputVec получение массива случайным образом 4–8 строки
    PrintVec печать массива
    9–14
    Sravn сравнение двух элементов массива
    15–18
    Использование параметра-массива
    1
    const
    NMax = 15;
    2
    type
    Vec = array[1..NMax] of Integer;
    3
    var
    A : Vec;
    4
    procedure
    InputVec(N: Integer; var
    A1 : Vec);
    5
    var i : Integer;
    6
    begin
    7
    for i := 1
    to
    N
    do
    A1[i] := Random(10);
    8
    end;
    9
    procedure
    PrintVec(N: Integer; const A1 : Vec);
    10
    var i : Integer;
    11
    begin
    12
    for i := 1
    to
    N
    do
    Write(A1[i]:4);
    13
    Writeln;
    14
    end;
    15
    function Sravn(x, y : Integer): Boolean;
    16
    begin
    17
    Sravn := x = y;
    18
    end;
    19
    begin
    20
    Randomize;
    { инициализация датчика псевдослучайных чисел }
    21
    InputVec(5, A);
    22
    PrintVec(5, A);
    23
    WriteLn(Sravn(a[1], a[5]));
    24
    end.
    208

    Сравнение двух элементов массива (длинный вариант)
    function Sravn(x, y : Integer): Boolean;
    begin if x = y then
    Sravn := True else
    Sravn := False;
    end;
    Пример 8.2 (
    сложение массивов
    ). Складывать массивы можно только поэле- ментно.
    Процедура сложения двух массивов
    1
    procedure Plus(N: Integer; const A1, B1 : Vec;
    var C1 : Vec);
    2
    var i : Integer;
    3
    begin
    4
    for i := 1
    to
    N
    do
    5
    C1[i] := A1[i] + B1[i];
    6
    end;
    209

    11.9
    Использование открытых массивов в качестве параметров
    Использование в качестве параметра подпрограммы открытого массива позволяет указывать базовый тип массива, не фиксируя при этом его размер.
    procedure <Имя_процедуры>(a : array of <базовый тип>);
    Открытый массив может быть только одномерным и состоять из эле- ментов любого типа, кроме файлового.
    При вызове подпрограммы на место открытого массива можно передавать
    1D массив с любым количеством элементов такого же типа.
    Передать открытый массив можно как значение, переменную, константу.
    Соглашение:
    элементы открытого массива нумеруются с нуля. Т. е. для от- крытого массива функция Low(A) всегда возвращает нулевое значение.
    Номер максимального элемента в массиве определяется с помощью функции
    High(A). Т. е. функция High возвращает уменьшенное на единицу число эле- ментов в фактическом параметре.
    Процедура печати массива произвольной длины
    1
    procedure PrintMas(const A : array of Integer);
    2
    var i : Integer;
    3
    begin
    4
    for i := Low(A)
    to
    High(A)
    do
    Write(A[i]:3);
    5
    end;
    Демонстрация работы с открытым массивом
    1
    program DemoMas02;
    2
    (* см. конспект *)
    3
    end.
    210

    11.10
    Поиск элемента в массиве
    11.10.1
    Поиск в массиве наименьшего/наибольшего значения
    (
    )
    Постановка задачи:
    найти Max/Min элемент в массиве и определить зна- чение индекса этого элемента.
    Достаточно найти индекс Max/Min элемента.
    Пример 10.1. Алгоритм поиска индекса максимального элемента запишем в виде процедуры.
    Поиск максимального элемента в массиве
    1
    type Vec = array[1..10] of Integer;
    2 3
    procedure MaxMax(const A1: Vec; var iM: Integer);
    4
    var i : Integer;
    5
    begin
    6
    iM := 1;
    7
    for i := 2 to High(A1) do
    8
    if A1[i] > A1[iM] then iM := i;
    9
    end;
    10 11
    var A
    : Vec;
    12
    MaxI : Integer;
    (* номер макс. эл-нта *)
    13
    begin
    14
    MaxMax(A, MaxI);
    15
    WriteLn(’Max = A[’, MaxI, ’] = ’, A[MaxI]);
    16
    end.
    Результат работы программы для массива (4, 4, 0, 15, 2, 24, 4, −5, 7, 2):
    Max = A[6] = 24 211

    11.10.2
    Линейный поиск элемента в массиве
    (
    )
    Пусть a i
    (i = 1, . . . , n) — элементы целочисленного (необязательно) масси- ва;
    b — некоторое целое число.
    Постановка задачи:
    выяснить входит ли данное число b в массив a
    1
    , . . . , a n
    , и если входит, то каково значение p, для которого a p
    = b.
    Линейный поиск заключается в переборе всех элементов массива и по- очередном их сравнении с искомым элементом. Поиск продолжается до тех пор, пока не случится совпадение, либо не будет достигнут конец массива.
    Результатом поиска является индекс соответствующего элемента.
    Приведем схемы поиска для двух случаев:
    1) искомый элемент имеется в массиве;
    2) искомый элемент в массиве отсутствует.
    A =
    a[5]
    a[4]
    a[2]
    a[3]
    Target — разыскиваемое значение a[1]
    Target
    ?
    = a[i]
    Target=a[1]
    False
    Target=a[2]
    False
    Target=a[3]
    True

    Found:=True
    Found:=False
    A =
    a[5]
    a[4]
    a[2]
    a[3]
    a[1]
    Target=a[1]
    False
    Target=a[2]
    False
    Target=a[3]
    False
    Target=a[5]
    False
    False
    Target=a[4]
    212

    Линейный поиск элемента в массиве
    1
    program Search;
    2
    const Max = 10;
    3
    type Vec = array[1..Max] of Integer;
    4
    var A
    : Vec;
    5
    i, Target : Integer;
    6
    Found
    : Boolean;
    7
    begin
    8
    (* Получение элементов массива *)
    9
    Write(’Введите число для поиска ’);
    ReadLn(Target);
    10 11
    { начало поиска }
    12
    Found := False;
    (* значение Target не найдено *)
    13
    i := 1;
    14
    while (i <= Max) and (not Found) do
    15
    begin
    16
    if a[i] = Target then Found := True
    17
    else i := i + 1;
    (* переход к следующему элементу *)
    18
    end;
    19
    { конец поиска }
    20 21
    (* анализ результата поиска *)
    22
    if not Found then
    23
    WriteLn(’Числа ’, Target, ’ в массиве нет’)
    24
    else
    25
    WriteLn(’Номер первого вхождения ’, i);
    26
    end.
    213

    11.10.3
    Линейный поиск элемента в упорядоченном массиве
    (* см. конспект *)
    Линейный поиск элемента в упорядоченном массиве
    1
    const Max = 10;
    2
    type Vec = array[1..Max+1] of Integer;
    3
    var A : Vec = (0, 1, 4, 5, 12, 20, 24, 35, 37, 38, -1);
    4 5
    begin
    6
    ReadLn(Target);
    7 8
    { начало поиска }
    9
    a[Max+1] := Target;
    i := 1;
    10
    while a[i] < Target do i := i + 1;
    11
    { конец поиска }
    12 13
    Found := (a[i] = Target) and (i <> Max+1);
    14
    WriteLn(’Число ’, Target, ’ в массиве есть ’, Found);
    15
    if not Found then
    16
    Writeln(’Элемент мог бы стоять на месте ’, i);
    17
    else
    18
    WriteLn(’Номер первого вхождения ’, i);
    19
    end.
    . Данный способ можно применять для поиска места вставки нового эле- мента в последовательность.
    214

    11.10.4
    Двоичный поиск элемента в упорядоченном массиве
    (
    )
    Пусть a i
    (i = 1, . . . , n) — элементы целочисленного упорядоченного мас- сива, т. е. a
    1
    < . . . < a n
    ;
    b — некоторое целое число.
    Постановка задачи.
    Прежняя (см. п.
    11.10.2
    ).
    Алгоритм деления пополам.
    Возьмем в качестве границ поиска индек- сы элементов p = 1 и q = n.
    p = 1
    s =
    p+q
    2
    q = n
    До тех пор, пока границы не совпадут, будем делить отрезок индексов по- полам (s = (p + q) div 2) и шаг за шагом сдвигать границы следующим образом:
    a s
    < b p
    q да s+1
    прежнее нет прежнее s
    Поиск закончится, когда p = q. Искомый элемент будет найден, если вы- полняется условие a[p] = Target
    Двоичный поиск элемента в массиве. Вариант 1
    Программу написать самостоятельно.
    Использовать заголовок цикла:
    while p <> q do ...
    . К проверке условия продолжения цикла p <> q можно добавить еще про- верку условия «искомый элемент не найден».
    Двоичный поиск элемента в массиве. Вариант 2
    Программу написать самостоятельно.
    Использовать заголовок цикла:
    while (p <> q) and (a[s] <> Target) do ...
    215

    Пример 10.2. Проследим за процессом поиска элемента методом половинного деления на примере массива:
    a
    1
    = 3
    a
    2
    = 7
    a
    3
    = 8
    a
    4
    = 10
    a
    5
    = 13
    a
    6
    = 15
    a
    7
    = 16
    a
    8
    = 18
    a
    9
    = 21
    a
    10
    = 23
    a
    11
    = 37
    a
    12
    = 39
    a
    13
    = 40
    a
    14
    = 44
    a
    15
    = 53
    A =
    3 7
    8 10 13 15 16 18 21 23 37 39 40 44 53 1
    2 3
    4 5
    6 7
    8 9
    10 11 12 13 14 15
    Разыскиваемый элемент — 43
    s a[s] a[s] < b p
    q
    8 18
    True
    9 15 12 39
    True
    13 15 14 44
    False
    13 14 13 40
    True
    14 14
    Результат поиска: элемента нет
    A =
    b:=43 3
    False
    7 8
    10 13 15 16 18 21 23 37 39 40 44 53 1
    2 3
    4 5
    6 7
    8 9
    10 11 12 13 14 15
    s = (1+15) div 2 = 8
    a[s] < b
    True
    A =
    F
    21 23 37 39 40 44 53 9
    10 11 12 13 14 15
    s = (9+15) div 2 = 12
    a[s] < b
    T
    A =
    40 44 53 13 14 15
    s = (13+15) div 2 = 14
    A =
    40 44 13 14
    s = (13+14) div 2 = 13
    A =
    44 14
    s = (13+15) div 2 = 14

    1   2   3   4   5   6   7   8   9
    написать администратору сайта