📖 Документация Qumir

← Вернуться в Playground

Продвинутые примеры

Оглавление

Алгоритмы сортировки

Быстрая сортировка (Quicksort)

Один из самых эффективных алгоритмов сортировки со средней сложностью O(n log n).

Идея алгоритма:

  1. Выбираем опорный элемент (pivot) — обычно средний элемент массива
  2. Разделяем массив на две части: элементы меньше опорного и больше опорного
  3. Рекурсивно сортируем обе части
алг quicksort(цел n, цел таб A[0:n-1], цел л, цел р)
нач
    цел i, j, m, опор, tmp
    i := л
    j := р
    опор := A[div(л + р, 2)]  | выбираем средний элемент как опорный

    нц пока i <= j
        | ищем элемент слева, который больше опорного
        нц пока A[i] < опор
            i := i + 1
        кц
        | ищем элемент справа, который меньше опорного
        нц пока A[j] > опор
            j := j - 1
        кц
        | меняем местами
        если i <= j то
            tmp := A[i]
            A[i] := A[j]
            A[j] := tmp
            i := i + 1
            j := j - 1
        все
    кц

    | рекурсивно сортируем левую и правую части
    если л < j то
        quicksort(n, A, л, j)
    все
    если i < р то
        quicksort(n, A, i, р)
    все
кон

Почему это работает:

▶ Запустить пример

Сортировка слиянием (Mergesort)

Стабильный алгоритм сортировки с гарантированной сложностью O(n log n).

Идея алгоритма:

  1. Делим массив пополам
  2. Рекурсивно сортируем каждую половину
  3. Сливаем две отсортированные половины в одну
алг merge(цел n, цел таб A[0:n-1], цел таб B[0:n-1], цел l, цел m, цел r)
нач
    цел i, j, k

    | копируем участок в буфер
    нц для i от l до r
        B[i] := A[i]
    кц

    i := l      | указатель на левую часть
    j := m + 1  | указатель на правую часть
    k := l      | указатель на результат

    | сливаем, выбирая меньший элемент
    нц пока (i <= m) и (j <= r)
        если B[i] <= B[j] то
            A[k] := B[i]
            i := i + 1
        иначе
            A[k] := B[j]
            j := j + 1
        все
        k := k + 1
    кц

    | дописываем остаток левой части
    нц пока i <= m
        A[k] := B[i]
        i := i + 1
        k := k + 1
    кц
    | правая часть уже на месте
кон

алг mergesort(цел n, цел таб A[0:n-1], цел таб B[0:n-1], цел l, цел r)
нач
    если l >= r то
        выход
    все
    цел m
    m := div(l + r, 2)
    mergesort(n, A, B, l, m)
    mergesort(n, A, B, m + 1, r)
    merge(n, A, B, l, m, r)
кон

Преимущества:

▶ Запустить пример

Пирамидальная сортировка (Heapsort)

Эффективный алгоритм на основе структуры данных «куча» (heap).

Идея алгоритма:

  1. Строим max-heap из массива (родитель всегда больше детей)
  2. Меняем корень (максимум) с последним элементом
  3. Восстанавливаем свойство кучи для уменьшенного массива
  4. Повторяем, пока массив не отсортирован
алг heapify(цел n, цел таб A[0:n-1], цел i)
нач
    цел largest, left, right, tmp
    largest := i
    left := 2 * i + 1    | левый потомок
    right := 2 * i + 2   | правый потомок

    | находим наибольший среди узла и его детей
    если (left < n) и (A[left] > A[largest]) то
        largest := left
    все
    если (right < n) и (A[right] > A[largest]) то
        largest := right
    все

    | если наибольший не корень — меняем и продолжаем
    если largest <> i то
        tmp := A[i]
        A[i] := A[largest]
        A[largest] := tmp
        heapify(n, A, largest)  | рекурсивно восстанавливаем
    все
кон

алг heapsort(цел n, цел таб A[0:n-1])
нач
    цел i, tmp

    | строим max-heap снизу вверх
    нц для i от div(n - 1, 2) до 0 шаг -1
        heapify(n, A, i)
    кц

    | извлекаем максимумы
    нц для i от n - 1 до 1 шаг -1
        tmp := A[0]
        A[0] := A[i]
        A[i] := tmp
        heapify(i, A, 0)
    кц
кон

Особенности:

▶ Запустить пример

Математика

Метод Гаусса

Классический алгоритм решения систем линейных уравнений Ax = b.

Идея алгоритма:

  1. Прямой ход: приводим матрицу к верхнетреугольному виду
  2. Обратный ход: находим решение, начиная с последней переменной
| прямой ход Гаусса с частичным выбором
нц для k от 0 до n-1
    | выбор ведущей строки по максимуму |A[i,k]|
    _imax := k
    bestSq := A[k,k] * A[k,k]
    нц для i от k+1 до n-1
        curSq := A[i,k] * A[i,k]
        если curSq > bestSq то
            bestSq := curSq
            _imax := i
        все
    кц

    | swap k <-> _imax (перестановка строк)
    если _imax <> k то
        нц для j от k до n-1
            tmp := A[k,j]
            A[k,j] := A[_imax,j]
            A[_imax,j] := tmp
        кц
        tmp := B[k]; B[k] := B[_imax]; B[_imax] := tmp
    все

    p := A[k,k]

    | нормируем ведущую строку
    нц для j от k до n-1
        A[k,j] := A[k,j] / p
    кц
    B[k] := B[k] / p

    | исключаем элементы ниже диагонали
    нц для i от k+1 до n-1
        tmp := A[i,k]
        если tmp <> 0.0 то
            нц для j от k до n-1
                A[i,j] := A[i,j] - A[k,j] * tmp
            кц
            B[i] := B[i] - B[k] * tmp
        все
    кц
кц

Важные детали:

▶ Запустить пример

Черепашья графика

Фрактальное дерево

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

Идея:

использовать Черепаха
алг
нач
    поднять хвост
    назад(120)
    опустить хвост
    дерево(9, 160.0)
кон

алг дерево(цел n, вещ len)
нач
    если n = 0 то
        вперед(len * 0.4)  | конечная веточка
    иначе
        вперед(len * 0.4)  | рисуем часть ствола

        сохранить состояние    | запоминаем позицию
        влево(25)
        дерево(n - 1, len * 0.7)  | левая ветвь
        восстановить состояние  | возвращаемся

        сохранить состояние
        вправо(25)
        дерево(n - 1, len * 0.7)  | правая ветвь
        восстановить состояние
    все
кон

Ключевые команды:

▶ Запустить пример

Снежинка Коха

Классический фрактал, построенный из кривых Коха.

Идея кривой Коха:

  1. Берём отрезок
  2. Делим на три части
  3. Среднюю часть заменяем «треугольным выступом»
  4. Рекурсивно повторяем для каждого отрезка
использовать Черепаха

алг снежинка(цел order, вещ side)
нач
    цел i
    нц для i от 0 до 2
        кох(order, side)
        влево(120)  | три стороны треугольника
    кц
кон

алг кох(цел n, вещ len)
нач
    если n = 0 то
        опустить хвост
        вперед(len)
    иначе
        кох(n - 1, len / 3.0)  | первая треть
        вправо(60)
        кох(n - 1, len / 3.0)  | выступ вверх
        влево(120)
        кох(n - 1, len / 3.0)  | выступ вниз
        вправо(60)
        кох(n - 1, len / 3.0)  | последняя треть
    все
кон

Математика:

▶ Запустить пример

Треугольник Серпинского

Фрактал, состоящий из треугольников с «вырезанной» серединой.

использовать Черепаха

алг маленький_треуг(вещ side)
нач
    цел i
    нц для i от 0 до 2
        вперед(side)
        влево(120)
    кц
кон

алг серпинский(цел n, вещ side)
нач
    если n = 0 то
        маленький_треуг(side)
    иначе
        | рисуем три маленьких треугольника Серпинского
        серпинский(n - 1, side / 2.0)  | нижний левый
        вперед(side / 2.0)
        серпинский(n - 1, side / 2.0)  | нижний правый
        назад(side / 2.0)
        влево(60)
        вперед(side / 2.0)
        вправо(60)
        серпинский(n - 1, side / 2.0)  | верхний
        влево(60)
        назад(side / 2.0)
        вправо(60)
    все
кон

Свойства:

▶ Запустить пример

Кривая дракона

Фрактальная кривая, которая при разворачивании бумаги образует характерный узор.

использовать Черепаха

алг дракон(цел n, вещ step)
нач
    если n = 0 то
        вперед(step)
    иначе
        дракон(n - 1, step)
        влево(90)
        крыла(n - 1, step)  | зеркальная версия
    все
кон

алг крыла(цел n, вещ step)
нач
    если n = 0 то
        вперед(step)
    иначе
        дракон(n - 1, step)
        вправо(90)
        крыла(n - 1, step)
    все
кон

Интересный факт: Если сложить полоску бумаги пополам много раз, а потом развернуть так, чтобы все сгибы были под 90°, получится именно кривая дракона!

▶ Запустить пример

Робот

Заливка области (Flood Fill)

Классический алгоритм заливки замкнутой области, используемый в графических редакторах.

Идея:

  1. Если клетка уже закрашена — выходим (базовый случай)
  2. Закрашиваем текущую клетку
  3. Рекурсивно заливаем все соседние клетки
использовать Робот

алг залей
нач
    если клетка закрашена
        то
            выход  | уже обработана
    все

    закрасить  | закрашиваем текущую

    | рекурсивно обходим соседей
    если сверху свободно
        то
            вверх
            залей
            вниз  | возвращаемся
    все

    если снизу свободно
        то
            вниз
            залей
            вверх
    все

    если слева свободно
        то
            влево
            залей
            вправо
    все

    если справа свободно
        то
            вправо
            залей
            влево
    все
кон

Особенности реализации:

▶ Запустить пример

Обход по стенам

Простой алгоритм обхода периметра области.

использовать Робот

алг обход_стен
нач
    | Идём вдоль стены по часовой стрелке
    нц пока справа свободно
        вправо
        закрасить
    кц

    нц пока снизу свободно
        вниз
        закрасить
    кц

    нц пока слева свободно
        влево
        закрасить
    кц

    нц пока сверху свободно
        вверх
        закрасить
    кц
кон

Применение:

▶ Запустить пример

Вычислительная математика

Уравнение теплопроводности в 3D (Heat3D)

Численное решение трёхмерного уравнения теплопроводности методом конечных разностей.

Физическая задача: Моделируем распространение тепла в трёхмерном кубе. Уравнение теплопроводности:

$\frac{\partial u}{\partial t} = \Delta u = \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} + \frac{\partial^2 u}{\partial z^2}$

Трёхмерные массивы в Кумире:

Ключевая особенность этого примера — использование трёхмерных массивов:

вещ таб u[0:Nx-1, 0:Ny-1, 0:Nz-1]
вещ таб un[0:Nx-1, 0:Ny-1, 0:Nz-1]

Обращение к элементу трёхмерного массива: u[i, j, k] — значение в точке с координатами (i, j, k).

Численная схема:

Используем явную схему Эйлера:

| Явная схема для уравнения теплопроводности
| dt ≤ h²/6 — условие устойчивости для 3D
вещ dt, alpha
alpha := 0.1      | alpha = dt / h² ≤ 1/6
dt := alpha * h2

| Основной цикл по времени
нц для n от 0 до nt-1 шаг 1
    | Обновляем только внутреннюю область
    нц для i от 1 до Nx-2 шаг 1
        нц для j от 1 до Ny-2 шаг 1
            нц для k от 1 до Nz-2 шаг 1
                | Лапласиан через 6 соседей
                un[i,j,k] := u[i,j,k] + alpha * (
                    (u[i+1,j,k] + u[i-1,j,k] +    | соседи по X
                     u[i,j+1,k] + u[i,j-1,k] +    | соседи по Y
                     u[i,j,k+1] + u[i,j,k-1])     | соседи по Z
                    - 6.0 * u[i,j,k])
            кц
        кц
    кц
    | Копируем результат обратно в u
кц

Структура вложенных циклов:

Трёхмерная сетка требует трёх вложенных циклов:

Граничные условия:

Нулевые условия Дирихле на границе (u = 0). Циклы идут от 1 до N-2, чтобы не затрагивать граничные точки.

Начальное условие и точное решение:

| u₀(x,y,z) = sin(πx) sin(πy) sin(πz)
| Точное решение: u(x,y,z,t) = e^{-3π²t} · u₀(x,y,z)

нц для i от 0 до Nx-1 шаг 1
    x := i * h
    нц для j от 0 до Ny-1 шаг 1
        y := j * h
        нц для k от 0 до Nz-1 шаг 1
            z := k * h
            u[i,j,k] := sin(pi * x) * sin(pi * y) * sin(pi * z)
        кц
    кц
кц

Проверка точности:

В конце вычисляем максимальную ошибку, сравнивая численное решение с аналитическим:

decay := exp(-3.0 * pi * pi * t)
err := 0.0
нц для i от 0 до Nx-1 шаг 1
    нц для j от 0 до Ny-1 шаг 1
        нц для k от 0 до Nz-1 шаг 1
            uex := decay * sin(pi * x) * sin(pi * y) * sin(pi * z)
            diff := abs(u[i,j,k] - uex)
            err := max(err, diff)
        кц
    кц
кц

Условие устойчивости:

Для явной схемы в 3D: $\alpha = \frac{dt}{h^2} \leq \frac{1}{6}$

При нарушении этого условия решение «взрывается».

Применение:

▶ Запустить пример

См. также