Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень) и алгоритмах на языке C!
Идея написать эту статью зародилась из моего поста, после него я начал серию статей, которая раскрывала много интересных моментов — от математических алгоритмов и оптимизации до ГПСЧ.
Если вы видите эту статью, значит еще не все тайны C раскрыты. В этом материале будет еще больше свежих хаков, фанов, трюков, еще больше магии и скорости! А также нетипичных алгоритмов и структур данных, что позволит вам почерпнуть и полезную информацию тоже!
Добро пожаловать в восьмую часть. Прошу под кат — там будет жарко, быстро и очень, очень интересно.
❯ Содержание
Вы можете читать статьи в любом порядке, они независимы друг от друга:
«Математика, биты, магия и немного ненормального программирования на C»
«Фокусы, хаки, магия и прочее ненормальное программирование на C»
❯ Алгоритм «черепахи и зайца» Флойда
Алгоритм придуман Робертом Флойдом и используется для обнаружения циклов в последовательностях, чаще всего в связных списках, но идея применима и к другим структурам, где есть переход по индексам или указателям.
Суть алгоритма: два указателя («черепаха» и «заяц») движутся по последовательности с разной скоростью. Заяц делает два шага за итерацию, черепаха — один. Если в последовательности есть цикл, то заяц неизбежно «догонит» черепаху внутри цикла. Если цикла нет, заяц первым достигнет конца последовательности.
#include <stdio.h> int findCycle(int nums[], int numsSize) { if (numsSize <= 1) return -1; int tortoise = nums[0]; int hare = nums[0]; do { tortoise = nums[tortoise]; hare = nums[nums[hare]]; if (hare < 0 || hare >= numsSize) return -1; } while (tortoise != hare); tortoise = nums[0]; while (tortoise != hare) { tortoise = nums[tortoise]; hare = nums[hare]; } return tortoise; }
Код использует два указателя — медленный (черепаха) и быстрый (заяц). Оба стартуют с начала массива. Медленный движется на 1 шаг: tortoise = nums[tortoise]. Быстрый — на 2 шага: hare = nums[nums[hare]]. Если массив содержит цикл, быстрый рано или поздно догонит медленного внутри цикла. Это первая фаза — обнаружение факта цикла.
После встречи медленного возвращаем в начало массива. Теперь оба движутся синхронно, по 1 шагу. Точка их новой встречи будет точкой входа в цикл. Это вторая фаза — нахождение начала цикла.
Проверка hare < 0 || hare >= numsSize отлавливает выход за границы, что означает отсутствие цикла. Алгоритм работает за O(n) времени и O(1) памяти, не меняя исходные данные. В примере {1,3,4,2,2} последовательность индексов 0→1→3→2→4→2 зацикливается на значениях 2 и 4, а начало цикла — значение 2.
Давайте протестируем код:
int main() { int arr[] = {1, 3, 4, 2, 2}; int size = sizeof(arr) / sizeof(arr[0]); int result = findCycle(arr, size); if (result != -1) { printf("Cycle starts at value: %d\n", result); } else { printf("No cycle found\n"); } return 0; }
Как мы видим, массив становится цикличным на 2: Cycle starts at value: 2.
❯ Конвертация RGB в градации серого
Функция конвертирует цвет из RGB в оттенки серого по формуле яркости. Она принимает три байта: красный, зеленый, синий каналы.
uint8_t rgb_to_grayscale(uint8_t r, uint8_t g, uint8_t b) { return (uint8_t)((r * 77 + g * 150 + b * 29) >> 8); }
Внутри используется взвешенная сумма каналов, потому что человеческий глаз воспринимает яркость цветов по-разному. Зеленый вносит наибольший вклад, затем красный, меньше всего синий. Коэффициенты: 77 для красного, 150 для зеленого, 29 для синего. Сумма коэффициентов 256.
Умножение дает 16-битный промежуточный результат. Сдвиг вправо на 8 бит (деление на 256) нормализует значение обратно в диапазон 0–255. Приведение типа к uint8_t возвращает итоговый байт — яркость пикселя.
❯ XOR-шифрование строки (шифр Вернама)
XOR-шифрование строки (шифр Вернама) — это метод шифрования данных, основанный на принципе «исключающего ИЛИ» (XOR). Также известен как «одноразовый блокнот» или «шифр с одноразовым ключом».
void xor_cipher(char *data, const char *key, size_t len) { for (size_t i = 0; i < len; i++) { data[i] ^= key[i % strlen(key)]; } }
Функция xor_cipher принимает три аргумента: указатель на массив данных data, указатель на ключ key и длину данных len. Она проходит в цикле по каждому байту данных. Для каждого байта выполняется операция XOR (исключающее ИЛИ) между текущим символом данных и соответствующим символом ключа. Если ключ короче данных, его символы используются циклически за счёт операции взятия остатка от деления i на длину ключа. Эта же функция применяется как для шифрования, так и для дешифрования: повторная операция XOR с тем же ключом восстанавливает исходные данные. Алгоритм тотально симметричен и корректен, но на практике небезопасен при повторном использовании короткого ключа.
❯ Алгоритм Брезенхэма для рисования кругов
Алгоритм Брезенхема для рисования кругов — метод растеризации окружностей в компьютерной графике, разработанный Джеком Брезенхемом. Использует только целочисленную арифметику, что делает алгоритм быстрым.
Основная идея алгоритма — отслеживать ошибку между истинной окружностью и аппроксимированной последовательностью пикселей. На каждом шаге алгоритм выбирает пиксель, который минимизирует эту ошибку.
void bresenham_circle(int x0, int y0, int radius) { int x = 0; int y = radius; int d = 3 - 2 * radius; while (x <= y) { plot(x0 + x, y0 + y); plot(x0 - x, y0 + y); plot(x0 + x, y0 - y); plot(x0 - x, y0 - y); plot(x0 + y, y0 + x); plot(x0 - y, y0 + x); plot(x0 + y, y0 - x); plot(x0 - y, y0 - x); if (d < 0) { d = d + 4 * x + 6; } else { d = d + 4 * (x - y) + 10; y = y - 1; } x = x + 1; } }
Алгоритм использует симметрию окружности: рисует только одну восьмую часть, остальные семь точек получаются отражением. Начинает с верхней точки (0, r). На каждом шаге выбирает между движением вправо или по диагонали вниз-вправо. Решение принимает на основе параметра d, который оценивает положение относительно идеальной окружности. Если d отрицательно — точка внутри, идём вправо. Если d >= 0 — точка снаружи, идём по диагонали, уменьшая y. Алгоритм работает пока x не превысит y, что соответствует углу 45 градусов.
Если что, полная реализация с функцией plot ниже:
#include <stdio.h> #define WIDTH 80 #define HEIGHT 40 char buffer[HEIGHT][WIDTH]; void plot(int x, int y) { if (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT) { buffer[y][x] = '*'; } } void clear_buffer() { for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { buffer[y][x] = ' '; } } } void print_buffer() { for (int y = 0; y < HEIGHT; y++) { for (int x = 0; x < WIDTH; x++) { putchar(buffer[y][x]); } putchar('\n'); } } void bresenham_circle(int x0, int y0, int radius) { int x = 0; int y = radius; int d = 3 - 2 * radius; while (x <= y) { plot(x0 + x, y0 + y); plot(x0 - x, y0 + y); plot(x0 + x, y0 - y); plot(x0 - x, y0 - y); plot(x0 + y, y0 + x); plot(x0 - y, y0 + x); plot(x0 + y, y0 - x); plot(x0 - y, y0 - x); if (d < 0) { d = d + 4 * x + 6; } else { d = d + 4 * (x - y) + 10; y = y - 1; } x = x + 1; } } int main() { clear_buffer(); bresenham_circle(WIDTH/2, HEIGHT/2, 15); print_buffer(); return 0; }
❯ Алгоритм Брезенхема для рисования линий
В прошлой статье я разбирал уже это, но я думаю будет полезно в контексте этой статьи рассказать об этом алгоритме еще раз, для тех кто не читал.
Этот же подход, но для отрезков: вместо вычисления координат по уравнению прямой, алгоритм шаг за шагом выбирает следующий пиксель, отслеживая накопленную ошибку.
Сначала вычисляются приращения по осям и направление движения. Основная переменная err хранит разность между этими приращениями. На каждом шаге мы двигаемся по X, по Y или по диагонали — в зависимости от того, куда текущая ошибка указывает как на лучшее приближение к идеальной прямой.
void bresenham_line(int x0, int y0, int x1, int y1) { int dx = abs(x1 - x0); int dy = abs(y1 - y0); int sx = (x0 < x1) ? 1 : -1; int sy = (y0 < y1) ? 1 : -1; int err = dx - dy; while (1) { plot(x0, y0); if (x0 == x1 && y0 == y1) break; int e2 = err * 2; if (e2 > -dy) { err -= dy; x0 += sx; } if (e2 < dx) { err += dx; y0 += sy; } } }
Оба алгоритма избегают умножений и делений с плавающей точкой, заменяя их сложением и сравнением целых чисел. Это делает их быстрыми и удобными для встраивания в графические библиотеки и драйверы. Ключевая идея — не вычислять точные координаты, а итеративно корректировать ошибку, выбирая следующий пиксель так, чтобы визуально линия или окружность выглядели гладкими.
❯ Алгоритм Ричардса (Richard’s Curve)
Алгоритм Ричардса (Richards’ Curve) — это метод оценки параметров нелинейной кривой роста (generalized logistic curve). Модель была предложена британским биологом Ф. Дж. Ричардсом в 1959 году. Она показывает тенденцию количественного роста: в начале она небольшая (стадия бурного роста), затем быстро увеличивается (стадия быстрого роста) и, наконец, стабилизируется в диапазоне значений (стадия насыщения).
Давайте реализуем быструю версию этого алгоритма:
float fast_sin(float x) { const float a = 4.0f / (M_PI * M_PI); const float p = 0.225f; x = a * x * (M_PI - fabs(x)); return p * (x * fabs(x) - x) + x; }
Идея в том, чтобы быстро вычислять синус на ограниченном интервале (от –π до π), используя только умножения, сложение и fabs. Это важно для эмбеддед систем, где нельзя использовать или нет доступа к стандартным методам.
Сначала он делает базовую параболическую волну: x = a * x * (π - |x|). Эта простая формула уже похожа на синус. Затем идёт коррекция погрешности через полином третьей степени: p * (x * |x| - x) + x. Это эквивалентно x + p*x³ - p*x. Коэффициент p=0.225 подобран, чтобы финальная кривая максимально близко легла на настоящий синус, используя минимум вычислений. Всё сводится к нескольким умножениям и сложениям.
❯ Меняем мантиссу числа на инвертированную
Эта функция меняет мантиссу числа на инвертированную, оставляя экспоненту неизменной. Создает «зеркальные» числа с плавающей точкой. Just for fun.
float magic_float_trick(float x) { union { float f; uint32_t i; } u = {x}; u.i = (u.i & 0x7F800000) | (~u.i & 0x007FFFFF); return u.f; }
Через union число интерпретируется и как float, и как целое для битовых операций. Маска 0x7F800000 выделяет экспоненту, а 0x007FFFFF — мантиссу. Инвертировав все биты (~u.i) и применив маску мантиссы, получаем инвертированную мантиссу, которая объединяется с исходной экспонентой. Знак при этом всегда обнуляется.
❯ Алгоритм Флойда–Уоршелла
Алгоритм Флойда–Уоршелла (также известен как алгоритм Флойда, алгоритм Роя — Уоршелла, алгоритм Роя — Флойда или алгоритм WFI) — алгоритм поиска кратчайших путей между всеми парами вершин во взвешенном графе с положительным или отрицательным весом рёбер (но без отрицательных циклов).
Давайте разберем типичную реализацию:
#include <stdio.h> #define INF 99999 #define V 4 void floydWarshall(int graph[][V]) { int dist[V][V]; int i, j, k; for (i = 0; i < V; i++) for (j = 0; j < V; j++) dist[i][j] = graph[i][j]; for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } printf("Матрица кратчайших расстояний:\n"); for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (dist[i][j] == INF) printf("%7s", "INF"); else printf("%7d", dist[i][j]); } printf("\n"); } } int main() { int graph[V][V] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} }; floydWarshall(graph); return 0; }
При запуске мы получаем:
Матрица кратчайших расстояний: 0 5 8 9 INF 0 3 4 INF INF 0 1 INF INF INF 0
Сам алгоритм — это классический пример динамического программирования. Его суть в постепенном улучшении ответа. Мы начинаем с матрицы смежности, где известно прямое расстояние между соседями. Затем, на каждом шаге, разрешаем использовать очередную вершину k в качестве промежуточной. Проверяем, станет ли путь от i к j короче, если мы сначала пойдем от i к k, а потом от k к j. Если да — обновляем значение. После того как мы разрешим использовать в качестве промежуточных все вершины от 0 до V-1, матрица будет содержать истинно кратчайшие пути.
Главные плюсы алгоритма — простота реализации и надежность. Он сам обнаруживает отрицательные циклы (в этом случае расстояние от вершины до себя станет отрицательным). Сложность — O(V³), поэтому для очень больших графов он не подходит. Но для плотных графов или когда V невелико, это отличный выбор.
❯ Алгоритм Карацубы для умножения больших чисел
Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog₂3. В то время как наивный школьный алгоритм, умножение в столбик, требует n² операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
Это рекурсивный алгоритм, который умножает большие числа быстрее школьного способа, разбивая числа на части. Он работает за время порядка n в степени log₂(3), примерно n^1.585, что ощутимо лучше n² для длинных чисел.
#include <stdio.h> #include <math.h> #include <string.h> int getMax(int a, int b) { return (a > b) ? a : b; } long long pow10(int e) { long long r = 1; for (int i = 0; i < e; i++) r *= 10; return r; } long long karatsuba(long long x, long long y) { if (x < 10 || y < 10) { return x * y; } int n = getMax((int)log10(x) + 1, (int)log10(y) + 1); int m = n / 2; long long power = (long long)pow10(m); long long a = x / power; long long b = x % power; long long c = y / power; long long d = y % power; long long ac = karatsuba(a, c); long long bd = karatsuba(b, d); long long abcd = karatsuba(a + b, c + d); return ac * pow10(2 * m) + (abcd - ac - bd) * power + bd; } int main() { long long x = 123456789; long long y = 987654321; long long result = karatsuba(x, y); printf("результат: %lld\n", result); return 0; }
Функция karatsuba принимает два числа. Если они достаточно маленькие (меньше 10), просто перемножает их — это базовый случай рекурсии. Для больших чисел определяется общая длина n и половина длины m. Числа разбиваются на части a, b, c, d с помощью деления и взятия остатка от 10^m.
Затем рекурсивно вычисляются три произведения: ac, bd и произведение сумм (a+b)(c+d). Финальный результат собирается по формуле. За счёт того, что (a+b)(c+d) уже содержит в себе ac и bd, мы можем вычесть их и получить ad + bc, экономя одно умножение.
Важно: этот пример работает с числами в пределах типа long long и использует десятичное основание для простоты. В реальных библиотеках для очень больших чисел (сотни цифр) используют двоичное представление и более сложное управление памятью, но суть алгоритма та же.
При компиляции мы получаем: результат: 121932631112635269. Мы используем свою реализацию pow10 вместо pow(10, ...) из‑за потери точности.
❯ Заключение
Спасибо за прочтение статьи! Я надеюсь, вы узнали что‑нибудь новенькое, или, может быть, какой‑нибудь трюк натолкнул вас на другой интересный алгоритм. Если нашли нюанс в самой статье — пишите в комментарии.
Если вам понравился изложенный материал, могу предложить вам подписаться на мой блог в телеграме. Если, конечно, вам статья понравилась и вы хотите видеть чуть больше.
Примеры работы кода вы можете увидеть в моем репозитории The Art Of Fun C.
❯ Источники
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
Перед оплатой в разделе «Бонусы и промокоды» в панели управления активируйте промокод и получите кэшбэк на баланс.
