70 классических алгоритмов на встроенном языке 1С
Разработка - Математика и алгоритмы
Файлы
ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.
Подписка PRO — скачивайте любые файлы со скидкой до 85% из Базы знаний
Оформите подписку на компанию для решения рабочих задач
Оформить подписку и скачать решение со скидкойВы можете заказать платную доработку или адаптацию этой разработки под вашу конфигурацию на «Бирже заказов».
- 0% комиссии — оплата напрямую исполнителю;
- Исполнители любого масштаба — от отдельных специалистов до команд под проект;
- Прямой обмен контактами между заказчиком и исполнителем;
- Безопасная сделка — при необходимости;
- Рейтинги, кейсы и прозрачная система откликов.
Для чего это
Инструмент для тех, кто учится или готовится к собеседованию: все классические алгоритмы собраны в одном окне, с человеческим описанием и рабочим кодом на встроенном языке 1С .
Обработка не требует никаких зависимостей: ни БСП, ни общих модулей, ни интернет-соединения, ни внешних компонент. Открывается в любой конфигурации на управляемых формах.
Кому будет полезно
- начинающим разработчикам 1С — как систематизированный тренажёр по базовым алгоритмам;
- тем, кто готовится к собеседованию: все темы, которые обычно спрашивают (сложность, двоичный поиск, хеш-таблица, обходы графов, ДП), в одном месте;
- студентам курсов и преподавателям — как готовый набор примеров на 1С вместо примеров на других языках;
- наставникам и тимлидам — как чек-лист для код-ревью и разбора типичных ошибок реализации.
Как выглядит
Одно окно, две области:
- слева — список из 70 алгоритмов со сквозной нумерацией и штатной строкой поиска по названию;
- справа — название выбранного алгоритма, его описание и пример реализации на встроенном языке 1С с подсветкой синтаксиса (ключевые слова, строки, комментарии, директивы компиляции, числа — цвета как в Visual Studio).
Весь набор хранится в значении формы: при переключении строки запросы к базе не выполняются, поэтому список листается без задержек.
Что внутри: 70 алгоритмов, 7 групп
Поиск и отбор
- Линейный поиск в массиве
- Двоичный поиск в отсортированном массиве
- Двоичный поиск левой и правой границы (lower bound и upper bound)
- Быстрый выбор k-го элемента (quickselect)
- Поиск минимума и максимума за один проход
- Мажоритарный элемент (алгоритм Бойера — Мура)
- Поиск пропущенного числа через побитовое исключительное ИЛИ (XOR)
- Бинарный поиск по ответу (минимизация монотонного критерия)
Сортировки
- Пузырьковая сортировка
- Сортировка вставками
- Сортировка выбором
- Сортировка Шелла
- Быстрая сортировка (рекурсивная, с разделением по опорному элементу)
- Сортировка слиянием
- Пирамидальная сортировка (куча, heapsort)
- Сортировка подсчётом (для неотрицательных целых чисел)
- Поразрядная сортировка (radix sort, LSD)
- Слияние двух отсортированных массивов
Строки
- Переворот строки и проверка на палиндром
- Проверка анаграмм (подсчёт символов)
- Подсчёт частоты символов (Соответствие)
- Сжатие строки RLE (кодирование длин серий)
- Префиксные суммы (быстрая сумма на отрезке)
- Поиск подстроки (алгоритм Кнута — Морриса — Пратта)
- Поиск подстроки Рабина — Карпа (хеширование)
- Z-функция строки
- Редакционное расстояние (Левенштейн)
- Наибольшая общая подпоследовательность (динамическое программирование)
- Префиксное дерево (trie) для поиска слов и префиксов
- Алгоритм Ханта — Шиманского (построение разницы двух версий текста)
Числа и математика
- Факториал (итеративная и рекурсивная реализации)
- Числа Фибоначчи (итеративно и с мемоизацией через Соответствие)
- НОД двух чисел (алгоритм Евклида, итеративный и рекурсивный)
- Решето Эратосфена (простые числа до N)
- Разложение числа на простые множители
- Быстрое возведение в степень (двоичное)
- Перевод целого числа в заданную систему счисления
- Перевод чисел в римскую запись и обратно
- Биномиальный коэффициент через динамическое программирование (треугольник Паскаля)
- Числа Каталана (динамическое программирование)
- Размен монет (жадный алгоритм)
- Размен монет через динамическое программирование (минимум монет)
Графы
- Обход графа в ширину (BFS) на Соответствие и Массив
- Обход графа в глубину (DFS, рекурсия)
- Топологическая сортировка зависимостей (алгоритм Кана)
- Алгоритм Дейкстры (кратчайшие расстояния во взвешенном графе)
- Алгоритм Беллмана — Форда (кратчайшие пути с отрицательными весами)
- Алгоритм Флойда — Уоршелла (все пары кратчайших путей)
- Минимальное остовное дерево (алгоритм Прима)
- Проверка двудольности графа (раскраска в два цвета)
- Компоненты сильной связности (Тарьян; альтернатива — Косарайю)
- Максимальный поток: Форд — Фалкерсон (дополняющий путь в ширину)
- Поиск A* (A-star) с эвристикой
Динамическое программирование и жадные алгоритмы
- Задача о рюкзаке 0/1 (динамическое программирование)
- Максимальная сумма подмассива (алгоритм Кадане)
- Наибольшая возрастающая подпоследовательность (динамическое программирование)
- Скользящее окно: максимальная сумма отрезка заданной длины
- Метод двух указателей: пара элементов с заданной суммой
- Слияние пересекающихся интервалов
Структуры данных, перебор и прочее
- Хеш-таблица методом цепочек
- Двоичное дерево поиска (вставка, поиск, обход)
- Связный список (односвязный, на структурах)
- LRU-кэш (вытеснение давно не использованных записей)
- Проверка правильности скобочной последовательности (стек)
- Вычисление выражения в обратной польской записи (стек)
- Ханойские башни (рекурсия, вывод последовательности ходов)
- Задача о N ферзях (перебор с возвратом)
- Генерация всех перестановок (перебор с возвратом)
- Удаление дубликатов из массива (Соответствие)
- Задача: старшая из трёх версий программы (сравнение версий вида 8.1.009.125)
Чем отличается от «ещё одной шпаргалки»
- Код написан идиоматично для 1С: Массив, Соответствие, Структура, СтрРазделить, СтрСоединить — без имитации синтаксиса других языков и без самодельных «умных» обёрток.
- Это рабочие функции и процедуры, а не иллюстрации: их можно скопировать в общий модуль и использовать. В примерах для наглядности оставлены директивы &НаСервере — при переносе в общий модуль их нужно убрать (в общем модуле директивы не ставятся).
- Подсветка синтаксиса реализована собственным небольшим лексером (без внешних библиотек и ActiveX) и выводится в «Поле HTML документа».
- Нет ни одной строки, зависящей от конкретной конфигурации: только встроенный язык и универсальные типы.
Требования
Платформа 1С:Предприятие 8.3, управляемые формы; любая конфигурация. Обработка внешняя, регистрация в справочнике дополнительных обработок не требуется — достаточно открыть файл через «Файл — Открыть».
Публикуемый файл собран на платформе 8.3.27 — это же значение указано в режиме совместимости. Если нужна поддержка более старых версий, обработку нужно пересобрать под нужную версию: в коде используются СтрШаблон(), СтрРазделить(), СтрСоединить() и Цел(), которых нет в совсем старых 8.3.
Чего обработка не делает (чтобы не было сюрпризов)
- не исполняет и не проверяет приведённый код на ваших данных — это справочник, а не песочница;
- не является production-библиотекой: набор учебный, часть реализаций сознательно упрощена ради читаемости (например, без оптимизации хвостовой рекурсии);
- список плоский, без дерева категорий: категория указана в описании, навигация — поиском по названию и нумерацией;
- не содержит тестов и эталонных ответов — только код и разбор типичных ошибок.
Как запустить
- Скачать файл .epf.
- В 1С:Предприятие — «Файл — Открыть», выбрать файл обработки.
- Если конфигурация поддерживает дополнительные обработки — можно добавить туда, но это не обязательно.
- Выбрать алгоритм в списке слева; при необходимости — отфильтровать список строкой поиска.
Технические подробности (для любопытных)
- одна управляемая форма, один реквизит-таблица значений; набор алгоритмов формируется функцией в модуле формы, обращений к базе нет;
- HTML-разметка примера строится на сервере при активации строки; лексер распознаёт комментарии, строковые литералы с удвоенными кавычками, директивы компиляции, числа и ключевые слова;
- объём: около 3 000 строк модуля формы, из них около 2 000 — строки примеров кода; файл модуля — 276 КБ.
- https://github.com/sqeioker/algorithms
Проверено на следующих конфигурациях и релизах:
- 1С:Деньги, релизы 2.0.44.40
Вступайте в нашу телеграмм-группу Инфостарт