Массивы

Место 14C

• В кинотеатре 300 мест. Система бронирования не использует 300 переменных с именами Seat1A, Seat1B, Seat1C. Она использует один массив, а ваш билет — это адрес внутри него: ряд 14, место C.
• Одно имя, сотни значений, каждое находится по номеру. Добавьте ряд, и код не изменится; пройдите циклом по номерам, и вы проверите каждое место.
• Почти каждый алгоритм в Paper 2 проходит по массиву: ищет в нем, суммирует, сортирует, находит максимальное значение.
• Этот урок посвящен словарю, объявлениям и четырем алгоритмам, которые требует экзаменатор в псевдокоде и словами.

Словарь терминов

• Массив — это структура данных, хранящая фиксированное количество элементов одного типа данных под одним идентификатором, каждый из которых доступен через индекс.
• Нижняя граница и верхняя граница — это первый и последний допустимые индексы. Количество элементов равно верхней границе минус нижняя граница плюс 1.
• Измерение показывает, сколько индексов нужно элементу: один для списка, два для таблицы.
• В ThisArray[n] ← 42 массив имеет одно измерение, индекс — это переменная-счетчик INTEGER n, а элемент по этому индексу получает значение 42.

Один идентификатор, индекс для каждого элемента, границы с обоих концов

Разобранный пример: объявление массива, необходимого задаче

Обработка массива 1-мерного

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

• Цикл FOR от нижней границы до верхней границы посещает каждый элемент ровно один раз.
• Для суммы, подсчета, максимума или минимума установите переменную-накопитель перед циклом и обновляйте её внутри.

2-мерные массивы

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99      // row 2, column 3

• Первый индекс — это строка, второй — столбец. Вложенные циклы проходят все ячейки: внешний цикл по строкам, внутренний по столбцам.
• Используйте 1-D для одномерного массива и 2-D, когда данные имеют две естественные размерности, например, сетку мест или таблицу оценок по ученикам и предметам.

Grid[row, column], всегда в таком порядке

Разобранный пример: линейный поиск, который может сообщить «не найдено»

FoundAt ← -1
FOR i ← 1 TO n
    IF A[i] = Target THEN
        FoundAt ← i
    ENDIF
NEXT i
IF FoundAt = -1 THEN
    OUTPUT "Not found"
ELSE
    OUTPUT "Found at ", FoundAt
ENDIF

Наибольшее значение и его позиция

Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
    IF A[i] > Largest THEN
        Largest ← A[i]
        Position ← i
    ENDIF
NEXT i
OUTPUT Largest, " at ", Position

• Начните Largest с первого элемента, а не с 0: массив может состоять только из отрицательных чисел.
• Та же форма подсчитывает или выводит непустые элементы: сравните каждый с маркером неиспользуемого значения, "" или -1, и считайте только те, что отличаются.

Сортировка пузырьком

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

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

Каждый переносит оставшееся наибольшее значение в конец

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

Разбор примера: удаление и вставка

Потерянные баллы

Вы поняли