23 апреля 2020
Поиск элемента в упорядоченной матрице

В матрице строки и столбцы отсортированы по возрастанию. Нужно найти позиции некоторого элемента, в примере это 100.

\( \begin{matrix} 60 & 64 & 66 & 67 & 71 & 75 & 76 & 77 & 81 & 85 \\ 62 & 70 & 72 & 73 & 77 & 81 & 85 & 89 & 90 & 93 \\ 63 & 71 & 73 & 75 & 79 & 82 & 88 & 93 & 96 & 97 \\ 63 & 81 & 83 & 84 & 86 & 89 & 92 & 96 & 98 & \bf{100} \\ 72 & 84 & 85 & 87 & 89 & 90 & 94 & 97 & 102 & 106 \\ 78 & 85 & 86 & 91 & 94 & 97 & \bf{100} & 101 & 103 & 110 \\ 87 & 90 & 94 & 96 & \bf{100} & 101 & 104 & 108 & 111 & 114 \\ 90 & \bf{100} & 101 & 105 & 106 & 110 & 111 & 113 & 116 & 120 \\ 94 & 103 & 106 & 110 & 111 & 114 & 117 & 121 & 122 & 125 \\ 95 & 111 & 115 & 117 & 119 & 122 & 125 & 127 & 128 & 130 \end{matrix} \)

Число 100 находится в позициях (если считать индексы с нуля): (3, 9), (5, 6), (6, 4) и (7, 1). Как решить такую задачу?

Читать далее →
5 февраля 2019
Как сделать «интерпретатор» кода, как на этом сайте

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

Новое решение строится на промисах и асинхронных функциях async/await. Для примера напишем функцию factorial() для вычисления факториала числа, он определён для целых чисел: \(n!=(n-1)!\times n\), \(0! = 1, 1! = 1\).

Вызывать функцию будем по нажатию на кнопку с идентификатором start.

$('#start').click(async () => {
    buttonPromise = makeButtonPromise();
    const n = 5;
    const result = await factorial(n);
    // ...
});

Читать далее →
18 марта 2018
Нули функции. Численные методы

Постановка задачи: на интервале \([a, b]\) задана функция \(f(x)\), удовлетворяющая некоторым условиям. Известно, что на этом интервале только один корень. Требуется его найти.

Читать далее →
8 ноября 2017
Сортировка Шелла. Интерактивная анимация

Сортировка Шелла — обобщение сортировки вставками, поэтому сперва нужно разобраться с ней.

Скажем, что сперва шаг сортировки равен 5 (на практике это число должно быть другим). Получается пять цветных массивов, которые сортируются по отдельности. Как? С помощью сортировки вставками. До и после:

Читать далее →
8 ноября 2017
Сортировка вставками. Интерактивная анимация

Идея сортировки: берём очередной элемент из ещё не отсортированной части массива (серый цвет) и ищем для него подходящее место в уже отсортированной части массива (чёрный цвет).

Читать далее →
8 ноября 2017
Гномья сортировка. Интерактивная анимация

Идея гномьей (наивной) сортировки такова. Представим, что числа — это горшочки. Гном начинает проверять горшочки слева направо. Пока они упорядочены по возрастанию, он просто продолжает проверять дальше. Как только он встречает горшок, который не на своём месте, он постепенно возвращается влево, находя ему подходящее место. Как только горшочек поставлен куда нужно, гном продолжает идти вправо.

Читать далее →
8 ноября 2017
Сортировка выбором. Интерактивная анимация

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

Читать далее →
6 ноября 2017
Сортировка пузырьком. Интерактивная анимация

Сортировка пузырьком известна многим. Её идея очень проста: берём пары соседних элементов и меняем их местами, если порядок неверный. И так много раз.

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

Читать далее →