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

  • На каком шаге прервется сортировка при использовании II варианта метода сортировки обменом для вектора из предыдущего примера

  • Кем и когда был изобретён данный алгоритм

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


    Скачать 3.84 Mb.
    НазваниеЛекциям по курсу Информатика
    Анкорlekcii_shiryaevoy.pdf
    Дата11.07.2018
    Размер3.84 Mb.
    Формат файлаpdf
    Имя файлаlekcii_shiryaevoy.pdf
    ТипЛекция
    #19640
    страница8 из 9
    1   2   3   4   5   6   7   8   9
    a[14] = 43?
    a[s] < b
    T
    a[s] < b
    T
    F
    F
    216

    Разыскиваемый элемент — 7
    s a[s] a[s] < b p q
    8 18
    False
    1 8
    4 10
    False
    1 4
    2 7
    False
    1 2
    1 3
    True
    2 2
    Результат поиска: элемент № 2
    A =
    b:=7 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
    s = (1+8) div 2 = 4
    a[s] < b
    T
    A =
    A =
    s = (1+2) div 2 = 1
    A =
    s = (1+4) div 2 = 2

    a[2] = 7?
    a[s] < b
    T
    a[s] < b
    T
    F
    F
    1 2
    3 4
    5 6
    7 16 15 13 10 8
    7 3
    8 18 1
    2 3
    4 10 8
    7 3
    1 3
    2 7
    2 7
    217

    11.10.5
    Понятие временной сложности
    Характер зависимости времени выполнения программы или подпрограммы от размера решаемой задачи называется временной сложностью
    Пример 10.3. 1) Если формула времени выполнения имеет вид t = a, то временная сложность O(1), т. е. t — величина порядка 1. Это означает, что время выполнения постоянно и не зависит от размера задачи.
    2) Если формула времени выполнения имеет вид t = a + bN,
    то временная сложность O(N ), т. е. при достаточно больших N , t ∼ N .
    3) Если формула времени выполнения имеет вид t = a + bN + cN
    2
    ,
    то временная сложность O(N
    2
    ).
    Чтобы выяснить временную сложность процесса, фактически необходимо знать лишь тот член формулы времени выполнения, который растет быстрее других с увеличением размера задачи. Это можно узнать, рассмотрев только одну стро- ку программы, а именно ту, которая выполняется чаще других (или одну их таких строк, если несколько строк выполняется одинаковое число раз). Форму- ла для числа выполнений такой строки определяет временную сложность всего процесса.
    Точное измерение времени выполнения каждой строки программы затрудни- тельно, если речь идет о программе, написанной на языке высокого уровня.
    Т.е.
    время исполнения является условным и измеряется в условных единицах
    218

    11.10.6
    Сравнение линейного и двоичного поисков
    N
    t t
    L
    t
    B
    (* см. конспект *)
    219

    11.11
    Методы работы с одномерными массивами
    11.11.1
    Замена элементов массива
    Заменять можно элементы с некоторым значением, а можно — элементы с опре- деленными номерами.
    Замена отрицательных чисел нулями (замена по значению)
    for i := 1 to Max do if a[i] < 0 then a[i] := 0;
    Замена элементов с четными номерами нулями (замена по номеру)
    for i := 1 to Max do if not Odd(i) then a[i] := 0;
    11.11.2
    Перестановка элементов массива
    Перестановка элементов массива производится обычным способом: обмен зна- чениями между парой переменных осуществляется с использованием третьей переменной.
    Перестановка элементов массива с номерами k1 и k2
    t := a[k1];
    a[k1] := a[k2];
    a[k2] := t;
    220

    11.11.3
    Удаление элементов из одномерного массива
    Удалять элементы из массива можно по значению элемента или по его номеру.
    Если удаление идет по значению элемента, то сначала необходимо найти номер этого элемента, а затем использовать метод удаления по номеру.
    Реально удалить элемент из статического массива невозможно
    Способ «удаления»:
    выделение подмассива, не содержащего удаляемого элемента.
    Пример 11.1 (
    удаление по номеру
    ). Удалить элемент массива с номером 3.
    Решение.
    Начиная с заданного номера, осуществляется сдвиг всех элементов массива влево. Последний элемент зануляется.
    Массив до удаления элемента a
    1
    a
    2
    a
    3
    a
    4
    a
    5
    a
    6
    Процесс «удаления» элемента a
    1
    a
    2
    a
    3
    = a
    4
    a
    4
    = a
    5
    a
    5
    = a
    6
    a
    6
    = 0
    Выдаваемый на печать подмассив a
    1
    a
    2
    a
    3
    a
    4
    a
    5
    Удаление по номеру
    1
    program DemoDel1;
    2
    const Max = 10;
    3
    var a
    : array[1..Max] of Integer;
    4
    i, Nom : Integer;
    5
    begin
    6
    InputVec(Max, A);
    (* получение элементов массива *)
    7
    WriteLn(’Введите № удаляемого элемента ’);
    ReadLn(Nom);
    8
    for i := Nom to
    Max - 1
    do
    9
    a[i] := a[i+1];
    (* сдвиг влево *)
    10
    a[Max] := 0;
    (* последний элемент равен 0 *)
    11
    PrintVec(Max-1, A);
    (* печать нового массива *)
    12
    end.
    221

    Пример 11.2 (
    удаление по значению
    ). Пусть все элементы массива разные.
    Удалить из массива максимальный элемент.
    Решение.
    Сначала определяется номер максимального элемента. Начиная с но- мера, соответствующего удаляемому элементу, осуществляется сдвиг всех эле- ментов массива. Последний элемент зануляется.
    Удаление по значению
    Программу написать самостоятельно.
    См. также п.
    11.10.3
    на стр.
    214 222

    11.11.4
    Вставка элемента в одномерный массив
    Для вставки элементов в массив нужно при описании массива предусмотреть,
    что количество элементов массива будет увеличиваться.
    Вставка элементов может осуществляться

    по номеру
    , т. е. в определенную позицию массива;

    по значению
    . Алгоритм заключается в поиске номера разыскиваемого эле- мента, а затем вставке нового элемента по номеру.
    Пример 11.3 (
    вставка по номеру
    ). Вставить некоторое заданное число в 1D
    массив на место с заданным номером.
    Решение.
    Начиная с заданного номера, осуществляется сдвиг всех элементов массива вправо.
    Пусть k — позиция для вставки элемента (например, k = 4); x — значение вставляемого элемента.
    Массив до вставки элемента a
    1
    a
    2
    a
    3
    a
    4
    a
    5
    a
    6
    Массив после вставки элемента a
    1
    a
    2
    a
    3
    a
    4
    = x a
    5
    = a
    4
    a
    6
    = a
    5
    a
    7
    = a
    6
    Вставка по номеру
    1
    program DemoIns;
    2
    const M = 5;
    3
    var a
    : array[1..M+1] of Integer;
    4
    i, k, x : Integer;
    5
    begin
    6
    InputVec(M, A);
    x := 8;
    7
    Write(’Позиция? ’);
    ReadLn(k);
    8
    for i := M
    downto k do a[i+1] := a[i];
    9
    a[k] := x;
    10
    PrintVec(M+1, A);
    (* печать нового массива *)
    11
    end.
    223

    11.12
    Сортировка массива
    Многие программы выполняются эффективнее, если данные, которые они об- рабатывают, предварительно отсортированы. Сортировать данные можно по возрастанию (↑) их значений или по убыванию (↓).
    Кошкин
    Мышкин
    Енотов
    Лисичкин Медведев
    ↑ Енотов
    Кошкин
    Лисичкин Медведев
    Мышкин
    ↓ Мышкин Медведев Лисичкин Кошкин
    Енотов
    4 2
    65 17 14 11 23 3
    ← →
    2 3
    4 11 65 23 17 14
    Постановка задачи сортировки массива:
    дан массив x
    1
    , . . . , x n
    , эле- менты которого попарно различны; требуется переставить элементы мас- сива так, чтобы после перестановки они были упорядочены в порядке воз- растания: x
    1
    < . . . < x n
    (убывания: x
    1
    > . . . > x n
    ).
    224

    11.12.1
    Сортировка выбором
    Сортировка выбором основана на идее многократного выбора: сначала находится наибольший элемент, затем второй по величине и т. д.
    Алгоритм сортировки выбором (I вариант):
    1) найти элемент с наибольшим значением
    ;
    2) поменять значениями найденный элемент и
    последний
    ;
    3) уменьшить на единицу количество просматриваемых элементов;
    4) если <количество элементов для следующего просмотра больше единицы>,
    то <повторить пункты, начиная с 1-го>
    5 1
    10 3
    6 5
    1 6
    3 10 5
    1 3
    6 10 3
    1 5
    6 10 1
    3 5
    6 10
    Сортировка выбором. Результат: a[1]<...1
    for i := N
    downto 2 do
    2
    begin
    3
    imax := 1;
    4
    for j := 2
    to i
    do
    5
    if a[j] > a[imax]
    then imax := j;
    6
    (* перестановка эл-тов *)
    7
    y := a[imax];
    8
    a[imax] := a[i];
    9
    a[i] := y;
    10
    end;
    . Количество просмотров во внешнем цикле: N-1.
    Количество шагов: при N = 5 — 10;
    при N = 10 — 45.
    225

    Алгоритм сортировки выбором (II вариант).
    Отличие состоит в том, что сдвиг границы просматриваемых элементов происходит слева.
    1) найти элемент с наименьшим значением
    ;
    2) поменять значениями найденный элемент и
    первый из просматриваемого подмассива;
    3) сдвинуть левую границу просматриваемых элементов вправо;
    4) если <количество элементов для следующего просмотра больше единицы>,
    то <повторить пункты, начиная с 1-го>
    5 1
    10 3
    6 1
    5 10 3
    6 1
    3 10 5
    6 1
    3 5
    10 6
    1 3
    5 6 10
    Сортировка выбором. Результат a[1] < ... < a[n]
    1
    for i := 1
    to
    N
    do
    2
    begin
    3
    imin := i;
    4
    for j := i + 1
    to
    N
    do
    5
    if a[j] < a[imin]
    then imin := j;
    6 7
    y := a[imin];
    8
    a[imin] := a[i];
    9
    a[i] := y;
    10
    end;
    226

    11.12.2
    Сортировка обменом
    Сортировка обменом предусматривает систематический обмен значени- ями (местами) тех пар, в которых нарушается упорядоченность, до тех пор,
    пока таких пар не останется.
    Алгоритм сортировки обменом (метод пузырька).
    Применительно к упорядочиванию по возрастанию:
    последовательным просмотром x
    1
    , . . . , x n
    найти i такое, что x i
    > x i+1
    ;
    поменять x i
    и x i+1
    местами, продолжить просмотр с элемента x i+1
    и т. д. Тем самым в результате первого просмотра наибольшее число передвинется на по- следнее место.
    Следующие просмотры начинать опять сначала, уменьшая на единицу количе- ство просматриваемых элементов. Массив будет упорядочен после просмотра,
    в котором участвовали только первый и второй элементы.
    Сортировка обменом, I вариант
    1
    for i := 1
    to
    N - 1
    do
    2
    for j := 1
    to
    N - i do
    3
    begin
    4
    if a[j] > a[j+1]
    then
    5
    begin
    6
    y := a[j];
    a[j] := a[j+1];
    a[j+1] := y;
    7
    end;
    8
    end;
    Пример 12.1. Результат работы программы на примере массива 4 7 2 1 3 5.
    i проверяются j
    1 4
    7 2
    1 3
    5
    n-1 2
    4 2
    1 3
    5 7
    n-2 3
    2 1
    3 4 5 7
    n-3 4
    1 2
    3 4 5 7
    n-4 5
    1 2 3 4 5 7
    n-5
    Здесь i — шаг; j — количество проверок на шаге i; « » обозначены попарные проверки.
    227

    II вариант реализации метода сортировки обменом — экономичный.
    Опишем пе- ременную Sort: Boolean. Если Sort = True, значит перестановка на данном шаге была произведена, в противном случае Sort остается равным False. Если на некотором шаге не было произведено ни одной перестановки, то сортировка прекращается.
    Сортировка обменом, II вариант
    1
    Sort := True;
    (*
    массив надо сортировать *)
    2
    i := 1;
    3
    while Sort do
    4
    begin
    5
    Sort := False;
    6
    for j := 1
    to
    N - i do
    7
    begin
    8
    if a[j] > a[j+1]
    then
    9
    begin
    10
    Sort := True;
    (* была произведена перестановка *)
    11
    y := a[j];
    a[j] := a[j+1];
    a[j+1] := y;
    12
    end;
    13
    end;
    14
    i := i+1;
    15
    end;

    На каком шаге прервется сортировка при использовании II варианта метода сортировки обменом для вектора из предыдущего примера?
    Для вектора
    5 4
    3 2
    1 0
    представить процесс сортировки по возрастанию методом обмена в виде таб- лицы. Даст ли здесь выигрыш экономичный вариант сортировки?
    228

    11.12.3
    Сортировка включением (простыми вставками)
    Алгоритм сортировки включением.
    Применительно к упорядочиванию по воз- растанию:
    просматривать последовательно a
    2
    , . . . , a n
    и каждый новый эле- мент a i
    вставлять на подходящее место в уже упорядоченную совокупность a
    1
    , . . . , a i−1
    . Это место определяется последовательным сравнением a i
    с упоря- доченными элементами a
    1
    , . . . , a i−1
    Сортировка включением, I вариант
    1
    for i := 2 to N do
    2
    begin
    3
    y := a[i];
    j := i - 1;
    4
    while (j >= 1) and (y < a[j]) do
    5
    begin
    6
    a[j+1] := a[j];
    j := j - 1;
    7
    end;
    8
    a[j+1] := y;
    9
    end;
    Здесь условие j >= 1 предотвращает выход за начало списка.
    II вариант реализации алгоритма сортировки включением.
    Массив дополняется барьерным элементом a
    0
    = y, где y — вставляемое зна- чение. Диапазон индексов в определении типа-массива необходимо расширить:
    ... array[0..N] of ...
    Введение барьерного элемента позволяет из условия цикла убрать проверку возможности выхода за начало списка (j >= 1).
    Сортировка включением, II вариант (барьерный элемент)
    3
    y := a[i];
    j := i - 1;
    a[0] := y;
    4
    while y < a[j] do ...
    229

    Оптимизация алгоритма сортировки методом вставок.
    (* см. конспект *)
    Сортировка включением, III вариант
    1
    imin := 1; { I шаг метода выбора }
    2
    for i := 2 to N
    do
    3
    if a[i] < a[imin] then imin := i;
    4
    if (imin <> 1) then { перестановка только в случае a[1] > a[2] }
    5
    begin
    6
    y := a[1];
    7
    a[1] := a[imin];
    8
    a[imin] := y;
    9
    end;
    10
    { метод вставок }
    11
    for i := 3 to N
    do
    12
    begin
    13
    y := a[i];
    j := i - 1;
    14
    while (y < a[j]) do ...
    15
    end;
    230

    Результаты обоих вариантов сортировок одного и того же вектора:
    14 7
    3 1
    11
    Сортировка массива вставками
    Стандартный метод
    14 7
    3 1
    11 7
    14 3
    1 11 3
    7 14 1
    11 1
    3 7
    14 11 1
    3 7
    11 14 7 перестановок в методе вставок
    Оптимизированный метод
    14 7
    3 1
    11
    поиск минимума
    1 7
    3 14 11 1
    3 7
    14 11 1
    3 7
    14 11 1
    3 7
    11 14 2 перестановки в методе вставок
    В таблице подчеркнуты проверяемые на данном шаге элементы.
    Жирным выделен элемент, для которого ищется подходящее место.
    Для вектора
    5 4
    3 2
    1 0
    представить процесс сортировки по возрастанию двумя вариантами метода вставок в виде таблиц. Даст ли здесь выигрыш оптимизированный вариант сортировки?
    231

    11.12.4
    Слияние двух упорядоченных массивов
    Сортировка слиянием (merge sort)
    — алгоритм сортировки структуры данных, который упорядочивает её в определённом порядке.
    Упорядочивать слиянием можно любые структуры данных, доступ к элементам которых можно получать последовательно (массивы, списки,. . . ).
    Сортировка слиянием — пример использования принципа
    «разделяй и властвуй»
    : сначала задача разбивается на несколько под- задач меньшего размера. Затем эти задачи решаются непосредственно или рекурсивно. Окончательно, их решения комбинируются и получается ре- шение исходной задачи.

    Кем и когда был изобретён данный алгоритм?
    232

    Задача слияния двух входных упорядоченных массивов A и B состоит в формировании упорядоченного выходного массива C, содержащего все элементы из входных массивов.
    Алгоритм слияния для упорядоченных по неубыванию массивов.
    • элемент a
    1
    сравнивается с элементом b
    1
    и наименьший из них записывается в массив C;
    • если наименьшим был a
    1
    , то на следующем шаге сравниваются a
    2
    и b
    1
    , а если наименьшим был b
    1
    , то будут сравниваться a
    1
    и b
    2
    и т. д.
    Если на очередном шаге окажется, что из одного входного массива все элемен- ты переписаны в C, то переписывается элемент из другого массива.
    A
    B
    1 2
    1 1
    4 4
    2 3
    4 5
    10 6
    14 9
    12 7
    13 8
    19 10
    Внизу указан номер элемента в новом массиве.
    C = 1 1
    1 2
    2 3
    4 4
    4 5
    10 6
    12 7
    13 8
    14 9
    19 10
    Слияние двух упорядоченных массивов
    1
    (* см. конспект *)
    233

    11.13
    Двумерные массивы
    Двумерный массив (матрица) содержит информацию, обычно представлен- ную в табличной форме. По своей форме матрицы бывают квадратные
    A
    2×2
    =
    a
    11
    a
    12
    a
    21
    a
    22
    (количество строк квадратной матрицы называют ее порядком) и пря- моугольные
    A
    2×3
    =
    a
    11
    a
    12
    a
    13
    a
    21
    a
    22
    a
    23
    ,
    A
    3×2
    =



    a
    11
    a
    12
    a
    21
    a
    22
    a
    31
    a
    32



    11.13.1
    Описание двумерных массивов
    Описание массива const N = 3;
    M = 4;
    type Mas = array[1..N,1..M] of Integer;
    var A : Mas;
    Здесь описана матрица A, состоящая из 3 × 4 целочисленных элементов
    A
    3×4
    =



    a
    11
    a
    12
    a
    13
    a
    14
    a
    21
    a
    22
    a
    23
    a
    24
    a
    31
    a
    32
    a
    33
    a
    34



    234

    11.13.2
    Размещение двумерных массивов в памяти
    Компиляторы Pascal содержат двумерные массивы в смежных ячейках.
    Элементы массива обычно содержатся в памяти по рядам (ряд 1, ряд 2 и т. д.).
    Для того чтобы получить доступ к определенному элементу массива, компи- лятор вычисляет смещение
    (offset) этого элемента относительно первого эле- мента массива.
    Для вычисления смещения компилятору необходимо знать размер каждого элемента в байтах и
    число элементов в ряду
    Оба эти значения можно почерпнуть из описания типа-массива.
    Опишем массив, имеющий (m2-m1+1)-строк и (n2-n1+1)-столбцов:
    var MasA : array[m1..m2, n1..n2] of <Тип>.
    Количество байтов памяти, занимаемых массивом,
    определяется по фор- муле
    ByteSize = (m2 - m1 + 1) × (n2 - n1 + 1) × SizeOf(Тип).
    (13.1)
    Смещение для элемента MasA[Row, Col] определяется по формуле:
    ByteNumber =
    (n2 - n1 + 1)
    количество столбцов
    ×(Row - m1)+(Col - n1) ×SizeOf(Тип).
    (13.2)
    235

    Пример 13.1. Вычислить смещение для элементов массива со следующим описанием.
    type Mas = array[1..3, 1..3] of Char;
    var A : Mas;
    На рисунке изображено расположение массива A в памяти компьютера.

    Содержимое ряда массива
    X
    ←− A[1,1] (смещение равно 0)
    1
    O

    O
    2
    X
    O
    ←− A[2,3] (смещение равно 5)
    X
    3

    X
    Формула (
    13.2
    )
    (n2 - n1 + 1) × (Row - m1) + (Col - n1) × SizeOf(Тип)
    теперь упрощается, т. к. сразу известно количество элементов в столбцах (ин- дексы описанного массива начинаются с единицы) и т. к. каждый элемент мас- сива занимает 1 байт памяти. Т. е. смещение для элемента A[Row,Col] опреде- ляется по следующей формуле:
    Offset = RowSize × (Row − 1) + (Col − 1),
    (13.3)
    здесь RowSize — размер ряда (т. е. количество столбцов).
    Поскольку размер ряда RowSize = 3 (т. е. три элемента в ряду), при использо- вании формулы (
    13.3
    ) получим значение 0 для элемента A[1,1] и значение 5
    для элемента A[2,3].
    Вычислить смещения для элементов A[1,5], A[2,3] и A[4,2] массива A
    с описанием var A : array[1..4, 1..5] of Integer;
    Ответы для проверки:
    8;
    14;
    32.
    236

    11.14
    Обработка двумерных массивов
    11.14.1
    Доступ к элементам 2d массива
    К элементам 2d массива возможны три метода доступа:
    1.
    Произвольный доступ
    . Элемент для обработки выбирается случайно,
    в зависимости от данных, введенных пользователем.
    2.
    Доступ по рядам
    . Сначала обрабатываются все элементы I ряда, затем все элементы II ряда и так далее.
    3.
    Доступ по столбцам
    . Сначала обрабатываются все элементы I столбца,
    затем все элементы II столбца и так далее.
    При доступе к элементам 2d массива по рядам и по столбцам, используются вложенные циклы.
    Шаблон доступа к 2d массиву Tabl по рядам for индекс_для_рядов... do for индекс_для_столбцов... do обработка элемента Tabl[индекс_для_рядов, индекс_для_столбцов]
    Шаблон доступа к 2d массиву Tabl по столбцам for индекс_для_столбцов... do for индекс_для_рядов... do обработка элемента Tabl[индекс_для_рядов, индекс_для_столбцов]
    Типичные операции, выполняемые над 2D массивами
    Название операции
    Рекомендуемый метод доступа
    Инициализация всех элементов массива опре- деленным значением по рядам или столбцам
    Вывод элементов массива по рядам
    Вычисление суммы всех элементов массива по рядам или столбцам
    Вычисление суммы элементов каждого ряда по рядам
    Вычисление суммы элементов каждого столбца по столбцам
    Замена значений элементов вводимыми дан- ными произвольный
    Перестановка элементов массива произвольный
    237

    11.14.2
    Инициализация массива
    Даны описания const NMax = 4; { количество строк }
    MMax = 3; { количество столбцов }
    type Mas = array[1..NMax, 1..MMax] of Integer;
    var a
    : Mas;
    i,
    { индекс строки }
    j
    : Integer;
    { индекс столбца }
    Ввод с клавиатуры
    WriteLn(’Введите элементы массива’);
    for i := 1
    to
    NMax do for j := 1
    to
    MMax do begin
    Write(’a[’, i, ’,’, j, ’] = ’);
    ReadLn(a[i,j])
    end;
    Инициализация элементов массива по заданному закону for i := 1
    to
    NMax do for j := 1
    to
    MMax do a[i,j] := 10*i + j;
    Результат:
    каждый элемент массива A представляет собой число, отражающее номер строки и номер столбца, т. е.
    A
    4×3
    =





    a
    11
    a
    12
    a
    13
    a
    21
    a
    22
    a
    23
    a
    31
    a
    32
    a
    33
    a
    41
    a
    42
    a
    43





    =





    11 12 13 21 22 23 31 32 33 41 42 43





    Инициализация массива при его описании const Max = 5;
    type
    Mas2 = array[1..Max-1, 1..Max] of Integer;
    var i, j : Integer;
    const
    A : Mas2 = ( (1, 3, 4, 5, 6),
    (-1, -3, -4, -5, -6),
    (10, 30, 41, 51, 61),
    (-1, 3, -4, 5, -6)
    );
    238

    11.14.3
    Печать массива
    Печать массива procedure PrintMas(NMax,MMax: Integer; const A0: Mas2);
    var i, j: Integer;
    begin for i := 1
    to
    NMax do begin for j := 1
    to
    MMax do
    Write(a0[i,j]:3); { печать по столбцам }
    WriteLn;
    { переход на новую строку }
    end;
    end;
    begin
    PrintMas(Max-1, Max, A);
    end.
    Результат работы программы:
    1 3
    4 5
    6
    -1 -3 -4 -5 -6 10 30 41 51 61
    -1 3 -4 5 -6
    Написать функцию для вычисления смещения для любого элемента массива с описанием:
    var A : array[1..4, 1..5] of Integer.
    Написать процедуру для печати в виде таблицы смещений для всех элемен- тов массива с описанием var A : array[1..4, 1..5] of Integer.
    Результат работы программы:
    0 2
    4 6
    8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 239

    11.14.4
    Суммирование элементов массива
    Суммирование всех элементов массива
    Sum := 0;
    for i := 1
    to
    3
    do for j := 1
    to
    4
    do
    Sum := Sum + a[i,j];
    Вычислить сумму элементов заданной строки в массиве
    Sum := 0;
    for j := 1
    to
    MMax do
    Sum := Sum + a[Nom,j];
    Здесь Nom — номер строки для суммирования.
    Пример 14.1. Создать вектор, хранящий сумму элементов каждой строки массива.
    Решение.
    Количество элементов нового вектора должно совпадать с количе- ством строк исходного массива.
    Вычисление суммы элементов в каждой строке массива
    1
    (* см. конспект *)
    240

    11.14.5
    Перестановка элементов массива
    Пример 14.2. Дан двумерный массив A, состоящий из 2n × 2n элементов. По- менять первую строку массива с последней строкой, вторую — с предпоследней и т. д.
    Исходный массив —
    1 0 1 5 2 9 2 7 3 5 0 3 4 7 4 8 4 7 4 8 3 5 0 3 2 9 2 7 1 0 1 5
    — преобразованный массив.
    Перестановка элементов массива
    1
    const M = 4;
    2
    type Mas = array[1..M, 1..M] of Integer;
    3
    const A : Mas = ( ... );
    4
    var i, j, TimeI : Integer;
    5
    begin ...
    6
    for i := 1
    to
    M div 2
    do
    7
    for j := 1
    to
    M
    do
    8
    begin
    9
    TimeI := a[i,j];
    10
    a[i,j] := a[M-(i-1),j];
    11
    a[M-(i-1),j] := TimeI;
    12
    end; ...
    13
    end.
    241

    Глава 12
    Строковый тип данных
    Строки используются в программах, предназначенных для обработки тексто- вых данных — текстовых редакторах и простейших базах данных.
    Строка эквивалентна массиву символов (не более 255).
    0 — байт длины 1 2
    3
    Нулевой элемент строки хранит длину строки (в виде двоичного символа).
    К отдельным элементам (символам) строки можно обращаться как к элементам массива:
    s[1] — первый символ строки,. . . ,
    s[Length(s)] — последний символ строки.
    Для определения длины строки служит функция Length(s). Данная функ- ция определяет фактическую длину строки, хранящейся в указанной пере- менной (а не величину предельного размера строки, установленную при опи- сании переменной типа string).
    242

    Длина строки в Turbo Pascal и Delphi
    1
    const sDL = ’Длина строки = ’; (* константа строкового типа *)
    2
    var s
    : string[5];
    3
    s2
    : string;
    4
    begin
    5
    s
    := ’Cat’;
    WriteLn(sDL, Length(s));
    6
    s
    := ’CatDog’;
    WriteLn(sDL, Length(s));
    7
    s2 := ’CatDog’;
    WriteLn(sDL, Length(s2));
    8
    end.
    Результат работы программы:
    Длина строки = 3
    Длина строки = 5
    (* длина не может быть > объявленной *)
    Длина строки = 6
    
    
    ¨
    ©
    Длина строки непостоянна и определяется содержащимися в ней данными.
    . Так как точно известно, что строка в
    Turbo Pascal может содержать не более 255 символов, то для описания переменной, которой будет присваиваться значение длины строки sL := Length(s);
    достаточно использовать тип Byte (var sL : Byte;).
    В
    Turbo Pascal определить длину строки можно также
    , используя функ- цию Ord: Ord(s[0]).
    Длина строки в TP и Delphi
    1
    var s : string[5];
    2
    begin
    3
    s
    := ’Cat’;
    WriteLn(Ord(s[0]));
    4
    end.
    В
    Delphi
    , если определить строку, указав при описании ее длину, то эта строка будет иметь «старый стиль» (а-ля Turbo Pascal) и к ней также будет применим вызов функции Ord(s[0]). В противном случае, вызов функции Ord(s[0])
    неприменим.
    243

    Длина строки в Delphi
    1
    var s
    : string[5] = ’Cat’;
    2
    s2
    : string = ’CatDog’;
    3
    begin
    4
    WriteLn(Ord(s[0]));
    5
    WriteLn(Ord(s2[0]));
    (* вызовет ошибку трансляции *)
    6
    end.
    12.1
    Нулевая строка
    Нулевая строка содержит нуль символов.
    Нулевая строка и ее размер
    1
    var s
    : string[50];
    2
    begin
    3
    s := ’’;
    4
    WriteLn(’Длина строки = ’, Length(s));
    5
    end;
    Результат работы программы:
    Длина строки = 0 244

    12.2
    Некоторые операции над строками
    (см. также п.
    4.1.8
    )
    Для строк установлены те же отношения порядка, как и в словаре; можно применять 6 операций отношения (>, <,. . . ).
    Сравнение двух строк
    1
    const s1 = ’Иванов’;
    2
    var s : string;
    3
    begin
    4
    ReadLn(s);
    5
    if s1 = s then WriteLn(’однофамильцы’);
    6
    end.
    Сравнение символов в строке if s[1] = s[Length(s)] then
    WriteLn(’совпадают первый и последний символы’);
    Написать функцию для ответа на вопрос: является ли введенная строка палиндромом.
    Проверить, какие значения возвращают функции Low и High для перемен- ных строкового типа в Turbo Pascal и в Delphi. Использовать строки с описа- ниями string[5] и string.
    В Pascal определена операция сцепления строк —
    конкатенация
    . Для кон- катенации строк может быть использован оператор «
    +
    » или функция
    Concat(строка1, строка2,...)
    «Склейка» двух строк
    1
    const s1 = ’ - студент’;
    2
    var s : string;
    3
    begin
    4
    Write(’Фамилия ’);
    ReadLn(s);
    5
    WriteLn(s + s1);
    (* или WriteLn(Concat(s,s1)); *)
    6
    end.
    . Если в результате конкатенации строка окажется длиннее 255 символов
    (в TP), она усекается после 255 символа.
    245

    Пример 2.1. Дана строка. Получить новую строку, переставив символы ис- ходной строки в обратном порядке.
    Перестановка символов в строке
    1
    var InStr,
    { исходная строка }
    2
    TStr
    : string;
    { новая строка }
    3
    i
    : Integer;
    4
    begin
    5
    InStr := ’Baobab’;
    6
    TStr := ’’;
    7
    for i := Length(InStr) downto 1 do
    8
    TStr := TStr + InStr[i];
    9
    WriteLn(’Исх. строка [>’, InStr);
    10
    WriteLn(’Нов. строка [>’, TStr);
    11
    end.
    12.3

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