Сергей Иванов

Сложные конструкции в псевдокоде

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

Циклы

Циклы служат для выполнения повторяющихся вычислений. Мы будем использовать два вида циклов: while и for. Цикл while выглядит следующим образом:

i = 0
while i < 5:
    print(i)
    i = i + 1

Синтаксис следующий: ключевое слово while, за которым следует условие, двоеточие и тело цикла. Этот код означает "выполнить тело цикла, пока условие истинно". В данном случае фрагмент печатает числа от 0 до 4.

Вот как выглядит цикл for:

sum = 0

for i in (1, 9):
    sum = sum + i

print(sum) // 45, сумма чисел от 1 до 9

Конструкция (1, 9) обозначает диапазон чисел от 1 до 9. Последнее число включено в диапазон: мы используем замкнутый интервал_, который включает все свои предельные точки. В общем случае конструкция for i in (a, b) означает, что переменной i последовательно присваиваются все числа из диапазона (a, b).

Массивы

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

array[1, 10] // 10-элементный массив с индексами от 1 до 10

Здесь переменная array обозначает массив из 10 элементов. Мы также можем инициализировать массив некоторыми данными в явном виде:

fib = [0, 1, 1, 2, 3, 5, 8] // массив с именем fib

Две наиболее часто используемые операции для массивов - это определение длины и доступ к элементам. Перечисление элементов начинается с 1. Как вы, возможно, знаете, индексы массивов в программировании часто начинаются с 0, но мы будем использовать обычный псевдокодовый подход. Давайте посмотрим, как это работает:

x = fib[4] // x равно 2
length = len(fib) // длина равна 7

for i in (1, len(fib)):
    print(fib[i])

Последний цикл for перебирает числа в массиве fib и выводит их все на экран.

Еще одна полезная операция - получение подмассива массива. Она выполняется следующим образом:

array = [0, 3, 2, 4, 1]
subarray = array[2, 4]
print(subarray) // 3, 2, 4

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

Функции

Функция - это часть программного кода, к которой можно обратиться из другого места программы, которая может принимать параметры (аргументы) и возвращать значение результата. Мы часто работаем с функциями, потому что они позволяют нам лучше понять смысл вещей и позволяют нам в нашем псевдокоде игнорировать некоторые детали реализации. Теперь давайте узнаем, как написать функцию с помощью псевдокода. Ниже приведена функция, которая вычисляет среднее значение чисел в массиве: 

function calc_mean(array):
    mean = 0

    for i in (1, len(array)):
        mean = mean + array[i]
    
    return mean / len(array)

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

Реализация простых алгоритмов в псевдокоде

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

function find_max(array):
    if len(array) == 0 then:
        return 0

    max = array[1]
    
    for i in (2, len(array)):
        if array[i] > max then:
            max = array[i]
    
    return max

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

function merge(left, right):
	merged[1, len(left) + len(right)] // новый массив 
    
    i = 1 // 
    j = 1 // индексы для цикла
    k = 1 // 
    
    // итерация по двум массивам, пока в обоих остались элементы
    while i <= len(left) and j <= len(right):
        if left[i] < right[j] then:    // помещаем элемент из левого массива в объединенный массив
            merged[k] = left[i]
            i = i + 1 // переходим к следующему элементу в левом массиве
        else:
            merged[k] = right[j] // помещаем элемент из правого массива в объединенный массив
            j = j + 1 // переход к следующему элементу в правом массиве
        k = k + 1 // переход к следующему элементу в объединенном массиве
                
    while i <= len(left):    // перемещаем оставшийся элемент левого массива в объединенный массив
        merged[k] = left[i]
        i = i + 1
        k = k + 1

    while j <= len(right):   // перемещаем оставшийся элемент правого массива в объединенный массив
        merged[k] = right[j]
        j = j + 1
        k = k + 1

    return merged

Обратите внимание, что мы не заботимся о передаче аргументов по значению, по ссылке и так далее. Если вы изменяете какую-либо переменную внутри функции, эти изменения сохраняются за пределами функции. Таким образом, если вам нужно сохранить аргумент неизменным, просто создайте его копию для работы с ним. Рассмотрим пример функции swap, которая меняет местами две переменные:

function swap(a, b):
    temp = a
    a = b
    b = temp

c = 3
d = 5

swap(c, d)

print(c) // 5
print(d) // 3

Резюме

Познакомились с некоторыми продвинутыми концепциями, которые мы используем в псевдокоде: циклы, массивы и функции. Помните: в этом диалекте массивы начинаются с 1, и мы используем замкнутые диапазоны!

https://hyperskill.org/learn/step/20922

← Назад