Algo1C: Решение алгоритмических задач на базе 1С:Предприятие [Часть #6]

24.09.24

Разработка - Математика и алгоритмы

Решаем новые задачи из LeetCode и CodeWars!

Йо, меня зовут Наби. Заранее благодарю за чтение и желаю продуктивно провести время! Если после прочтения возникнут вопросы, пожелания или предложения, то буду рад ознакомиться со всем в комментариях!


Предисловие:

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

В этой части вас ждут еще более интересные алгоритмические задачи!

Перед началом чтения решения задачи, хочу призвать каждого к самостоятельному решению задачи, чтобы после вы могли сравнить своё решение с моим и обсудить это в комментариях. Буду рад послушать ваше мнение! Давайте, приступим!


Новое в конфигурации Algo1C (Последние 5 версий):

Актуальную версию конфигурации вы можете загрузить здесь (Нажмите на строку)

- 0.5 : Добавлена возможность выбирать контекст исполнения кода, например: НаСервере или НаКлиенте

- 0.4 : Исправлена ошибка при выводе содержимого исключения

- 0.3 : Добавлена возможность сохранять и загружать задачи; Внесены небольшие изменения в интерфейс

- 0.2 : Исправлена ошибка при выводе результата (Отдельная благодарность SAShikutkin)

 


Решение задач:

 
 Задача 1

 Платформа: CodeWars

 Название задачи: Maximum subarray sum

 Ссылка на задачу: https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c (Нажмите на строку)

 Сложность: 5 kyu

 Тэги: Алгоритмы, Списки, Динамическое программирование, Фундаментальные, Производительность

 Оригинальное описание задачи:

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
# should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

Пояснение:

От нас требуется в данном нам массиве, найти последовательность чисел с наибольшей суммой и затем вернуть эту сумму. Например в примере из оригинала, самую большую сумму образует последовательность чисел от 3(индекс) по 6(индекс). Давайте придумаем решение!


Решение:

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

ИсходныйМассив = Новый Массив;
ИсходныйМассив.Добавить(-2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-3);
ИсходныйМассив.Добавить(4);
ИсходныйМассив.Добавить(-1);
ИсходныйМассив.Добавить(2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-5);
ИсходныйМассив.Добавить(4);
//
МаксимальнаяСумма = 0;
ТекущаяСумма = 0;
Для Каждого Стр Из ИсходныйМассив Цикл
	ТекущаяСумма = ТекущаяСумма + Стр;
	Если ТекущаяСумма < 0 Тогда
		ТекущаяСумма = 0;
	ИначеЕсли ТекущаяСумма > МаксимальнаяСумма Тогда
		МаксимальнаяСумма = ТекущаяСумма;
	КонецЕсли;
КонецЦикла;
//
Вывод = МаксимальнаяСумма;

Заключение:

Интересная была задача и решение, как мне кажется, получилось неплохим и более менее оптимальным!

 
 Задача 2
 
 Задача 3
 
 Задача 4
 
 Задача 5

Заключение:

Ну что ж, пока на этом всё, надеюсь статья была увлекательной для вас, благодарю за внимание. Подключайтесь к решению алгоритмических задач вместе со мной, делитесь вашим мнением и решениями в комментариях! Увидимся в новой статье!

Алгоритмы Математика. Оптимизация кода LeetCode CodeWars

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    2709    stopa85    12    

35

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    6538    user1959478    50    

36

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    2642    maksa2005    8    

25

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    10103    7    SpaceOfMyHead    18    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    3922    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

В статье анализируются средства платформы для решения системы линейных уравнений в 1С. Приводятся доводы в пользу некорректной работы встроенных алгоритмов, а значит потенциально некорректного расчета себестоимости в типовых конфигурациях.

23.11.2022    3002    gzharkoj    14    

24

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    8848    7    kalyaka    11    

44
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. s22 22 25.09.24 08:58 Сейчас в теме
ответ не верный в 1

если все числа меньше 0, то что будет ответом?
5. webester 26 25.09.24 12:24 Сейчас в теме
(1) В условиях сказано, что если все числа отрицательные надо вернуть ноль и если список пустой тоже.
2. webester 26 25.09.24 10:47 Сейчас в теме
Благодаря уже существующей в 1С функции, нам не придётся сильно заморачиваться с решением
Ну правильно, здесь же задача не на решение алгоритмов, зачем заморачиваться.
3. RocKeR_13 1360 25.09.24 12:12 Сейчас в теме
(2) Что-то не пойму, вообще в чем сложность и интерес сей задачи-то?)
6. Gesperid 2 26.09.24 09:16 Сейчас в теме
(3) Сложности нет, но варианты реализации могут быть интересны.
Например, можно увидеть, что в 1С срезов нет.
СтрокаЦифр = СтрСоединить(ИМ);
СтрШаблон("(%1) %2-%3", Сред(СтрокаЦифр, 1, 3), Сред(СтрокаЦифр, 4, 3), Сред(СтрокаЦифр, 7, 4))
4. webester 26 25.09.24 12:15 Сейчас в теме
(3)Могу уверить, ты не одинок в этом.
зы: планки сарказм, не хватает таки?
Оставьте свое сообщение