Минимализмы 2

22.02.18

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

Следующая серия "минимализмов" [http://infostart.ru/public/306536/]. Также, как и в предыдущей статье, здесь приведена подборка коротких оригинальных решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

В предыдущей статье "Минимализмы" в итоге было приведено двадцать одно решение. Просматривать статью и дрбавлять новые решения стало неудобно. Поэтому следующая серия решений оформлена в виде отдельной публикации. Для удобства более новые решения теперь помещаются в начало текста.

38. Удаление повторяющихся символов в начале или конце текста

http://www.forum.mista.ru/topic.php?id=765792

Функции СокрЛ, СокрП, СокрЛП удаляют любое количество пробелов в начале или конце строки. Этим можно воспользоваться, чтобы удалить другие начальные или конечные повторяющиеся символы, заменив их на пробел, а затем выполнив обратную замену. Например, чтобы удалить любое количество точек в конце строки, можно воспользоваться выражением:

СтрЗаменить(СокрП(СтрЗаменить(ИсходнаяСтрока, ".", " ")), " ", ".")

Правда, если исходная строка изначально содержит пробелы, то результат будет неправильным. В этом случае предварительно требуется заменить пробелы каким-либо редким сочетанием символов, а после преобразования выполнить обратную замену.

СтрЗаменить(СтрЗаменить(СокрП(СтрЗаменить(СтрЗаменить(ИсходнаяСтрока, " ", Символы.НПП), ".", " ")), " ", "."), Символы.НПП, " ")

37. Генератор вариантов формул

http://forum.infostart.ru/forum86/topic146521/

В данной задаче требуется сформировать список строк, каждая из которых будет являться вариантом формулы, содержащей аргументы X1, X2, ..., Xmax, знаки арифметических операций и скобки. Этот список затем можно использовать для решений задач типа "расставьте знаки арифметических операций и скобки между заданными числами, чтобы результат вычислений давал заданное число". Функция, решающая данную задачу, может иметь следующий вид:

Функция СписокФормул(От, До)
    Перем Результат, Сч, Оп; // для безопасности
    Результат = Новый СписокЗначений;
    Если От >= До Тогда
        Результат.Добавить("X" + От);
        Результат.Добавить("( - X" + От + ")")
    Иначе 
        Для Сч = От По До - 1 Цикл
            ПравыеЧасти = СписокФормул(Сч + 1, До); // для скорости
            Для каждого Слева Из СписокФормул(От, Сч) Цикл
                Для каждого Справа Из ПравыеЧасти Цикл
                    Для Оп = 1 По 3 Цикл
                        Результат.Добавить("(" + Слева + " " + Сред("+*/", Оп, 1) + " " + Справа + ")")
                    КонецЦикла 
                КонецЦикла
            КонецЦикла     
        КонецЦикла 
    КонецЕсли;
    Возврат Результат
КонецФункции // СписокФормул()

Логика тут такая: Цепочка аргументов разными способами разбивается на две части: операцией между первым и вторым, вторым и третьим, третьим и четвертым аргументами и так далее. Варианты формул для левой и правой части цепочки вычисляются рекурсивно. Затем варианты комбинируются, конкатенируясь с тремя (кроме минуса) разными вариантами соединяющих их операций. Скобки обрамляют результат. Когда диапазон номеров аргументов сужается до одного, возвращается два варианта: Xj и ( - Xj). Знак минус обрабатывается особым образом, поскольку минус может быть унарной операцией. 

Например, для четырех аргументов функция выдает 2 160 различных формулы, последняя из которых имеет вид:

(((( - X1) / ( - X2)) / ( - X3)) / ( - X4))

 

36. Алгоритм перебора всех возможных сочетаний элементов

http://forum.infostart.ru/forum86/topic146528/

На входе массив из элементов: {X1, X2, ..., Xm}. Требуется составить все возможные сочетания элементов без учета размещения: {X1}, {X2}, ..., {Xm}, {X1, X2}, ..., {X1, Xm},...,{X2, Xm},...,{X1, X2, ..., Xm}. Другими словами, требуется получить все возможные подмножества множества элементов, заданного в исходном массиве.

Вот функция, решающая данную задачу:

Функция ВсеПодмножества(Множество) 
    Ответ = Новый Массив;
    Ответ.Добавить(Новый СписокЗначений);
    Для ИндексЭлемента = 0 По Множество.Количество() - 1 Цикл
        Для ИндексВарианта = 0 По Ответ.Количество() - 1 Цикл
            Ответ.Добавить(Ответ[ИндексВарианта].Скопировать());
            Ответ[ИндексВарианта].Добавить(Множество[ИндексЭлемента])
        КонецЦикла
    КонецЦикла;
    Возврат Ответ
КонецФункции

Результат функции - массив списков значений, содержащих разные подмножества элементов исходного массива. Массив включает и пустое подмножество (на последнем месте).

35. Выбрать в запросе одну запись из нескольких

http://www.forum.mista.ru/topic.php?id=764178

Имеется таблица, содержащая, например,  колонки Ф, К1, К2, К3, К4. Для каждого значения Ф в тоблице может быть несколько записей.

Ф  К1   К2   К3   К4 
 Петя  1 1 1 1
Петя 2 0 0 0
Петя 3 0 0 0
Вася 5 5 5 5
Женя 4 4 4 4

 

Требуется получить таблицу, включающую по одной (любой) записи для каждого значения Ф.

Ф  К1   К2   К3   К4 
 Петя  1 1 1 1
Вася 5 5 5 5
Женя 4 4 4 4

 

Несмотря на простоту формлировки, у задачи нет простого решения, если только не использовать коррелированный запрос. С использованием коррелированного запроса решение получается очень простым:

ВЫБРАТЬ РАЗЛИЧНЫЕ Ф, К1, К2, К3, К4
ИЗ Дано
ГДЕ (Ф, К1, К2, К3, К4) 
В (ВЫБРАТЬ ПЕРВЫЕ 1 * ИЗ Дано КАК ВСЁ ГДЕ ВСЁ.Ф = Дано.Ф)

При использовании коррелированных запросов нельзя забывать о подводных камнях этого механизма, в частности о том, что он может служить причиной падения производительности запроса. Кроме того, в некоторых версиях файлового варианта условие ГДЕ из-за ошибки платформы 8.2 не срабатывает.

34. Как свернуть таблицу значений в коде, но получить не сумму, а максимум

http://www.forum.mista.ru/topic.php?id=716861

http://www.forum.mista.ru/topic.php?id=760950

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

Дано.Сортировать("Поле1, Поле2");

Для ё = 1 По Дано.Количество() - 1 Цикл
	Если Дано[ё].Поле1 = Дано[ё - 1].Поле1 И Дано[ё].Поле2 = Дано[ё - 1].Поле2 Тогда
		Дано[ё].Поле3 = МИН(Дано[ё].Поле3, Дано[ё - 1].Поле3); // = МАКС(Дано[ё].Поле3, Дано[ё - 1].Поле3);
		Дано[ё - 1].Поле3 = 0
	КонецЕсли 
КонецЦикла;

Дано.Свернуть("Поле1, Поле2", "Поле3");

Здесь Поле1, Поле2 - поля группировки, а Поле3 - поле, в котором ищется минимум в группировках.

Заменив функцию МИН на функцию МАКС, получим агрегатную функцию максимум, если убрать первый оператор в цикле, то будут выбираться все последние записи в группировках, а если в цикле оставить только оператор

Дано[ё].Поле3 = 0

то будут выбираться первые значения в группировках.

В обсуждении http://www.forum.mista.ru/topic.php?id=766103 родился еще более короткий вариант:

Дано.Сортировать("Поле1, Поле2, Поле3 Убыв"); //для МАКС, Дано.Сортировать("Поле1, Поле2, Поле3"); //для МИН
Для ё = 1 По Дано.Количество() - 1 Цикл
    Если Дано[ё].Поле1 = Дано[ё - 1].Поле1 И Дано[ё].Поле2 = Дано[ё - 1].Поле2 Тогда
        Дано[ё].Поле3 = 0
    КонецЕсли 
КонецЦикла;
Дано.Свернуть("Поле1, Поле2", "Поле3");

Чтобы не записывать каждый раз конкретные названия полей группировки, можно обобщить приведенный выше фрагмент, задавая строку имен полей группировок:

Дано.Сортировать(ИменаПолейГруппировки);

Для ё = 1 По Дано.Количество() - 1 Цикл
	Повтор = Истина;
	Для каждого Элемент Из Новый Структура(ИменаПолейГруппировки) Цикл
		Повтор = Повтор И (Дано[ё][Элемент.Ключ] = Дано[ё - 1][Элемент.Ключ])  
	КонецЦикла; 
	Если Повтор Тогда 
		Дано[ё][Ресурс] = МИН(Дано[ё][Ресурс], Дано[ё - 1][Ресурс]);
		Дано[ё - 1][Ресурс] = 0
	КонецЕсли 
КонецЦикла;

Дано.Свернуть(ИменаПолейГруппировки, Ресурс);

В принципе, можно обойтись и без сортировки, если использовать соответствие. Для случая группировки по одному полю, нужный фрагмент кода будет иметь вид:

Сток = Новый Соответствие;

Для каждого Строка Из Дано Цикл 
	Ключ = Строка[ПолеГруппировки];
	Если Сток[Ключ] = Неопределено Тогда 
		Сток[Ключ] = Строка
	Иначе 
		Сток[Ключ][Ресурс] = МИН(Сток[Ключ][Ресурс], Строка[Ресурс]);
		Строка[Ресурс] = 0
	КонецЕсли 
КонецЦикла;

Дано.Свернуть(ПолеГруппировки, Ресурс);

 

33. Поиск кратчайших путей по алгоритму Флойда-Уоршолла

http://forum.infostart.ru/forum24/topic144086/

Функция, решающая данную задачу:

Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
    // загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
    Пути = Новый Соответствие;
    Для каждого Дуга Из Дуги Цикл
        Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
        Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
    КонецЦикла;
    // три вложенных цикла по узлам графа
    Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин  
        Для каждого Узел2 Из Пути Цикл 
            Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
                Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ 
                    Длина = Пути[Узел2.Ключ][Узел3.Ключ];
                    Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
                    Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
                КонецЦикла 
            КонецЕсли 
        КонецЦикла 
    КонецЦикла;
    // восстановление пути
    Путь = Дуги.СкопироватьКолонки("Куда, Длина");
    Путь.Добавить().Куда = Откуда;
    Путь.Добавить().Куда = Куда;
    Путь[1].Длина = Пути[Откуда][Куда];
    Для каждого Узел Из Пути Цикл 
        Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено 
            И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
            ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
        КонецЕсли
    КонецЦикла;
    Путь.Сортировать("Длина");
    Возврат Путь
КонецФункции // КратчайшийПуть()

Данное решение иллюстрирует использование соответствия при решении задач на графах. Благодаря этому достигается существенный выигрыш по быстродействию. Например, приведенная функция примерно на 30% опрережает по быстродействию решение задачи поиска пути в московском метро запросом, приведенное в статье "Определение кратчайших путей, критических путей одним запросом".

С другой стороны, и алгоритм Флойда и алгоритм матричного умножения относятся к классу задач "All Pairs Shortest Paths (APSP) problem", то есть для определения расстояния между парой вершин являются избыточными.  В данной задаче (для заданной пары вершин) лучше использовать алгоритм Дейкстры.

32. Определение длины строки в запросе методом половинного деления

//infostart.ru/public/439822/

В исходной статье был продемонстрирован оригинальный алгоритм определения длины строки в запросе. Однако при высокой скорости вычислений выражение для получения длины строки получается чрезвычайно громозким. На каждую возможную длину строки требуется записать вариант "ТОГДА". В приведенном ниже решении этот недостаток устранен:

ВЫБРАТЬ
    Стр, Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   0, 512) = "" ТОГДА Х -   1 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   1, 512) = "" ТОГДА Х -   2 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   3, 512) = "" ТОГДА Х -   4 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   7, 512) = "" ТОГДА Х -   8 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  15, 512) = "" ТОГДА Х -  16 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  31, 512) = "" ТОГДА Х -  32 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  63, 512) = "" ТОГДА Х -  64 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 127, 512) = "" ТОГДА Х - 128 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 255, 512) = "" ТОГДА Х - 256 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 511, 512) = "" ТОГДА Х - 512 ИНАЧЕ Х КОНЕЦ КАК Х
ИЗ    Дано КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ

Для строки длиной до 1024 символов используется система из 10-ти вложенных запросов. Исходная таблица, кроме самой строки, должна содержать начальное значение поиска Х, равное 1024.

Данный вариант не учитывает в длине строки концевые пробелы. Если это действительно требуется, то придется использовать вот такой вариант:

ВЫБРАТЬ
    Стр, Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   0, 1) + "!" = "!" ТОГДА Х -   1 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   1, 1) + "!" = "!" ТОГДА Х -   2 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   3, 1) + "!" = "!" ТОГДА Х -   4 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -   7, 1) + "!" = "!" ТОГДА Х -   8 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  15, 1) + "!" = "!" ТОГДА Х -  16 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  31, 1) + "!" = "!" ТОГДА Х -  32 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х -  63, 1) + "!" = "!" ТОГДА Х -  64 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 127, 1) + "!" = "!" ТОГДА Х - 128 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 255, 1) + "!" = "!" ТОГДА Х - 256 ИНАЧЕ Х КОНЕЦ Х
ИЗ    (ВЫБРАТЬ Стр, ВЫБОР КОГДА ПОДСТРОКА(Стр, Х - 511, 1) + "!" = "!" ТОГДА Х - 512 ИНАЧЕ Х КОНЕЦ Х
ИЗ    Дано КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ) КАК ВЗ

31. Подсчет записей, содержащих одинаковые неупорядоченные пары значений

http://www.forum.mista.ru/topic.php?id=760508

Если в некоторой таблице есть два поля, заполняемые в произвольном порядке, то как посчитать число "одинаковых" записей?

К примеру, для таблицы "два любимых блюда" 

 Блюдо1   Блюдо2 
Овсянка Омлет
Плов Борщ
Омлет Овсянка
 Пельмени   Шашлык 
Борщ Плов

так можно посчитать число различных комбинаций блюд:

Блюдо1 Блюдо2  Количество 
Овсянка Омлет 2
Борщ Плов 2
 Пельмени   Шашлык  1

 

Собственно, запрос, решающий данную задачу:

ВЫБРАТЬ А, Б, КОЛИЧЕСТВО(*) 
ИЗ (ВЫБРАТЬ А, Б ИЗ Дано ОБЪЕДИНИТЬ ВЫБРАТЬ Б, А ИЗ Дано ГДЕ А <> Б) КАК ВЗ 
ГДЕ А <= Б
СГРУППИРОВАТЬ ПО А, Б

30. Первый пропущенный артикул

http://www.forum.mista.ru/topic.php?id=759443

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

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

Для максимизации скорости запрос преобразования в число записан иначе, чем в исходной статье.  Кроме того, для "надежности" вместо коррелированного запроса используется группировка, хотя запись при этом также получается более длинной:

ВЫБРАТЬ
	ВЫБОР ПОДСТРОКА(Артикул, 6, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ 
  + ВЫБОР ПОДСТРОКА(Артикул, 5, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ * 10
  + ВЫБОР ПОДСТРОКА(Артикул, 4, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ * 100
  + ВЫБОР ПОДСТРОКА(Артикул, 3, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ * 1000
  + ВЫБОР ПОДСТРОКА(Артикул, 2, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ * 10000
  + ВЫБОР ПОДСТРОКА(Артикул, 1, 1)КОГДА"1"ТОГДА 1 КОГДА"2"ТОГДА 2 КОГДА"3"ТОГДА 3 КОГДА"4"ТОГДА 4 КОГДА"5"ТОГДА 5 КОГДА"6"ТОГДА 6 КОГДА"7"ТОГДА 7 КОГДА"8"ТОГДА 8 КОГДА"9"ТОГДА 9 ИНАЧЕ 0 КОНЕЦ * 100000 КАК Х
ПОМЕСТИТЬ Числа
ИЗ Дано
ДЛЯ ИЗМЕНЕНИЯ
;
ВЫБРАТЬ 
    Х, 
    ЛОЖЬ КАК Свободен
ПОМЕСТИТЬ ЧислаПлюс
ИЗ Числа
ОБЪЕДИНИТЬ
ВЫБРАТЬ	
    Х + 1, 
    ИСТИНА
ИЗ Числа
;
ВЫБРАТЬ ПЕРВЫЕ 1
    Х КАК ПервыйСвободныйАртикул
ИЗ ЧислаПлюс
СГРУППИРОВАТЬ ПО Х
ИМЕЮЩИЕ КОЛИЧЕСТВО(*) = 1 И МАКСИМУМ(Свободен) = ИСТИНА

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

Обратное преобразование числового артикула в строковый здесь не делается. Это возможно, но большого смысла в этом нет. Преобразование числового артикула  в строковый легче сделать вне запроса перед присвоением нового артикула.

29. Количество дней, когда товар был на складе

http://forum.infostart.ru/forum14/topic141252/

Обычный подход к решению этой задачи - рассчитать "остатки на каждый день" и подсчитать дни наличия товара. Предлагается другой подход: найти все интервалы отсутствия товара и вычесть их общую длину из длины периода. Получается следующий запрос:

ВЫБРАТЬ
    Движения.Склад,
    Движения.Номенклатура,
    Движения.Период,
    Движения.КоличествоНачальныйОстаток,
    Движения.КоличествоКонечныйОстаток
ПОМЕСТИТЬ Движения
ИЗ
    РегистрНакопления.ТоварыНаСкладах.ОстаткиИОбороты(&НачалоПериода, &КонецПериода, Секунда, , ) КАК Движения
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
    Движения.Склад,
    Движения.Номенклатура,
    Движения.Период,
    Движения.КоличествоНачальныйОстаток,
    Движения.КоличествоКонечныйОстаток
ПОМЕСТИТЬ ДополненныеДвижения
ИЗ
    Движения КАК Движения

ОБЪЕДИНИТЬ

ВЫБРАТЬ РАЗЛИЧНЫЕ
    НачальныеНули.Склад,
    НачальныеНули.Номенклатура,
    &НачалоПериода,
    0,
    0
ИЗ
    Движения КАК НачальныеНули

ОБЪЕДИНИТЬ

ВЫБРАТЬ РАЗЛИЧНЫЕ
    КонечныеНули.Склад,
    КонечныеНули.Номенклатура,
    &КонецПериода,
    0,
    0
ИЗ
    Движения КАК КонечныеНули
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
    Точки.Склад,
    Точки.Номенклатура,
    Точки.Период,
    МАКСИМУМ(Точки.КоличествоНачальныйОстаток) КАК КоличествоНачальныйОстаток,
    МАКСИМУМ(Точки.КоличествоКонечныйОстаток) КАК КоличествоКонечныйОстаток
ПОМЕСТИТЬ ТочкиВремени
ИЗ
    ДополненныеДвижения КАК Точки

СГРУППИРОВАТЬ ПО
    Точки.Склад,
    Точки.Номенклатура,
    Точки.Период
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
    Точки.Склад,
    Точки.Номенклатура,
    МАКСИМУМ(Слева.Период) КАК НачалоОтсутствия,
    Точки.Период
ПОМЕСТИТЬ Интервалы
ИЗ
    ТочкиВремени КАК Точки
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТочкиВремени КАК Слева
        ПО Точки.Склад = Слева.Склад
            И Точки.Номенклатура = Слева.Номенклатура
            И (Точки.КоличествоНачальныйОстаток = 0)
            И (Слева.КоличествоКонечныйОстаток = 0)
            И Точки.Период > Слева.Период

СГРУППИРОВАТЬ ПО
    Точки.Склад,
    Точки.Номенклатура,
    Точки.Период

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ РАЗЛИЧНЫЕ
    Точки.Склад,
    Точки.Номенклатура,
    &КонецПериода,
    &НачалоПериода
ИЗ
    Движения КАК Точки
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
    Интервалы.Склад,
    Интервалы.Номенклатура,
    СУММА(РАЗНОСТЬДАТ(Интервалы.Период, Интервалы.НачалоОтсутствия, СЕКУНДА)) / 60 / 60 / 24 КАК ДнейНаличия
ИЗ
    Интервалы КАК Интервалы

СГРУППИРОВАТЬ ПО
    Интервалы.Склад,
    Интервалы.Номенклатура

Чтобы обработать "особые случаи" (когда в начале или в конце интервала остаток будет нулевым), потребовалось добавить записи - "заглушки" по краям интервала. Чтобы учесть возможность, когда периодов отсутствия не было, потребовалось добавить записи полного интервала, из которых при группировке вычитаются интервалы отсутствия. 
Из-за этих особых случаев запрос получился длинным, но по идее он простой. Большим плюсом этого подхода является то, что он замечает движения в течении дня. Если же ориентироваться только на остатки в начале/конце дня, то на складе типа "гардероб" (завезли и тут же продали) товар будет всегда отсутствовать.

Возможно, при небольшом объеме данных необходимости повышать быстродействие, выделяя более редкие интервалы отсутствия товаров, и не возникнет. Тогда можно просуммировать собственно интервалы наличия, что выливается в гораздо более короткий запрос (сразу для дней, но можно переделать и для секунд):

ВЫБРАТЬ
	Движения.Период,
	Движения.Склад,
	Движения.Номенклатура,
	Движения.КоличествоКонечныйОстаток
ПОМЕСТИТЬ Движения
ИЗ
	РегистрНакопления.ТоварыНаСкладах.ОстаткиИОбороты(&НачалоПериода, &КонецПериода, ДЕНЬ, ДвиженияИГраницыПериода, Склад = &Склад) КАК Движения
;
ВЫБРАТЬ
	Интервалы.Склад,
	Интервалы.Номенклатура,
	СУММА(Интервалы.Интервал) КАК ДнейНаличия
ИЗ
	(ВЫБРАТЬ
		Было.Склад КАК Склад,
		Было.Номенклатура КАК Номенклатура,
		РАЗНОСТЬДАТ(Было.Период, МИНИМУМ(Стало.Период), ДЕНЬ) КАК Интервал
	ИЗ
		Движения КАК Было
			ВНУТРЕННЕЕ СОЕДИНЕНИЕ Движения КАК Стало
			ПО Было.Склад = Стало.Склад
				И Было.Номенклатура = Стало.Номенклатура
				И (Было.КоличествоКонечныйОстаток > 0)
				И Было.Период < Стало.Период
		СГРУППИРОВАТЬ ПО
		Было.Период,
		Было.Склад,
		Было.Номенклатура) КАК Интервалы
СГРУППИРОВАТЬ ПО
	Интервалы.Склад,
	Интервалы.Номенклатура

 

28. Движения периодического регистра сведений без повторов

http://forum.infostart.ru/forum26/topic140198/

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

ВЫБРАТЬ
    Дано.Дата КАК Дата,
    Дано.Цена
ИЗ
    Дано КАК Дано
        ЛЕВОЕ СОЕДИНЕНИЕ Дано КАК Слева
        ПО (Слева.Дата < Дано.Дата)
СГРУППИРОВАТЬ ПО
    Дано.Дата,
    Дано.Цена
ИМЕЮЩИЕ
    ЕСТЬNULL(МАКСИМУМ(Слева.Дата), 0) <> ЕСТЬNULL(МАКСИМУМ(ВЫБОР Слева.Цена КОГДА Дано.Цена ТОГДА Слева.Дата КОНЕЦ), 1)

Или вот еще решение через коррелированный запрос (всегда требуется тестировать производительность таких вариантов!)

ВЫБРАТЬ
    Дано.Дата КАК Дата,
    Дано.Цена
ИЗ
    Дано КАК Дано
ГДЕ
    НЕ Дано.Цена В
                (ВЫБРАТЬ ПЕРВЫЕ 1
                    Слева.Цена
                ИЗ
                    Дано КАК Слева
                ГДЕ
                    Слева.Дата < Дано.Дата
                УПОРЯДОЧИТЬ ПО
                    Слева.Дата УБЫВ)

27. Округление в большую сторону

http://www.forum.mista.ru/topic.php?id=752392

Этот прием ранее уже применялся в минимализмах, как часть другого решения, но его можно показать и отдельно, поскольку такие задачи встречаются.

Для округления числа Ч в бОльшую сторону можно применять выражение:

М - Цел(М - Ч)

где М = 999999999 или больше, при необходимости.

В качестве дополнения красивый прием, взятый из чужого кода. Абсолютное значение числа Ч:

Макс(Ч, -Ч)

26. Сравнение двух массивов

http://www.forum.mista.ru/topic.php?id=750240

Задача заключается в том, чтобы сравнить два массива и вывести те их элементы, которые не встречаются в обоих массивах, то есть выполнить операцию исключающего ИЛИ для массивов. С использованием соответствия функция сравнения получается достаточно простой:

Функция ИсключающееИЛИ(Массив1, Массив2)    
    Результат = Новый Массив;    
    Повтор = Новый Соответствие;    
    Для каждого Элемент Из Массив1 Цикл
        Повтор[Элемент] = ?(Повтор[Элемент] = Неопределено, Ложь, Истина)
    КонецЦикла;    
    Для каждого Элемент Из Массив2 Цикл
        Повтор[Элемент] = ?(Повтор[Элемент] = Неопределено, Ложь, Истина)
    КонецЦикла;    
    Для каждого Элемент Из Повтор Цикл
        Если НЕ Элемент.Значение Тогда
            Результат.Добавить(Элемент.Ключ)
        КонецЕсли 
    КонецЦикла;    
    Возврат Результат
КонецФункции

Если в массиве могут быть только даты (в исходной задаче было так), то можно использовать другой принцип, сократив один цикл:

Функция ИсключающееИЛИ1(Массив1, Массив2)    
    Результат = Новый Массив;    
    Строка1 = ЗначениеВСтрокуВнутр(Массив1);
    Строка2 = ЗначениеВСтрокуВнутр(Массив2);    
    Для каждого Элемент Из Массив1 Цикл
        Если НЕ Найти(Строка2, Формат(Элемент,"ДФ=ггггММддЧЧммсс")) Тогда
            Результат.Добавить(Элемент)
        КонецЕсли 
    КонецЦикла;    
    Для каждого Элемент Из Массив2 Цикл
        Если НЕ Найти(Строка1, Формат(Элемент,"ДФ=ггггММддЧЧммсс")) Тогда
            Результат.Добавить(Элемент)
        КонецЕсли 
    КонецЦикла;    
    Возврат Результат
КонецФункции

25. Объединение непересекающихся интервалов в запросе

http://www.forum.mista.ru/topic.php?id=748551

Задача заключается в том, чтобы собрать в один непрерывный интервал все время проживание гостя в гостинице, если между интервалами не было перерывов. То есть для таблицы

 НачалоПериода   КонецПериода   Гость
1.01.2001 2.01.2001  Росс Геллер 
3.01.2001 4.01.2001  Росс Геллер
7.01.2001 8.01.2001 Росс Геллер

должно получиться

 НачалоПериода   КонецПериода   Гость
1.01.2001 4.01.2001  Росс Геллер 
7.01.2001 8.01.2001  Росс Геллер

Это делает следующий запрос, являющийся развитием идей решения задачи 14 из предыдущей статьи на случай интервалов:

ВЫБРАТЬ
    Дано.НачалоПериода,
    Дано.КонецПериода,
    Дано.Гостиница,
    Дано.ФизическоеЛицо,
    СУММА(РАЗНОСТЬДАТ(Слева.НачалоПериода, Слева.КонецПериода, ДЕНЬ) + 1) КАК Интеграл
ПОМЕСТИТЬ ДаноПлюс
ИЗ
    Дано КАК Дано
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Слева
        ПО (Слева.НачалоПериода <= Дано.НачалоПериода) 
           И Дано.Гостиница = ДаноСлева.Гостиница 
           И Дано.ФизическоеЛицо = ДаноСлева.ФизическоеЛицо
СГРУППИРОВАТЬ ПО
    Дано.НачалоПериода,
    Дано.КонецПериода,
    Дано.Гостиница,
    Дано.ФизическоеЛицо
;
ВЫБРАТЬ
    МИНИМУМ(Дано.НачалоПериода) КАК НачалоПериода,
    МАКСИМУМ(Дано.КонецПериода) КАК КонецПериода,
    Дано.Гостиница,
    Дано.ФизическоеЛицо
ИЗ
    ДаноПлюс КАК Дано
СГРУППИРОВАТЬ ПО
    ДОБАВИТЬКДАТЕ(Дано.КонецПериода, ДЕНЬ, -Дано.Интеграл),
    Дано.Гостиница,
    Дано.ФизическоеЛицо

24. Генерация случайных чисел с логарифмическим распределением

http://www.forum.mista.ru/topic.php?id=747493

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

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

Вот необходимые для решения этой задачи функции:

Перем ГСЧ; 
Перем МассивФункцииРаспределения Экспорт;

Функция Вероятность(К, Тэта)
    Возврат -1 / log(1 - Тэта) * Pow(Тэта, К) / К
КонецФункции
// все вероятности нарастающим итогом, послелнее значение == 1, это будет функция распределения
Функция Распределение(Тэта)
    Ответ = ТаблицаВыбора.ВыгрузитьКолонку(0);
    // табулируем вероятности
    Для ё = 1 По Ответ.Количество() Цикл
        Ответ[ё - 1] = Вероятность(ё, Тэта)
    КонецЦикла;
    ВГраница = Ответ.ВГраница();
    // наращиваем итог
    Для ё = 1 По ВГраница Цикл
        Ответ[ё] = Ответ[ё] + Ответ[ё - 1]
    КонецЦикла;
    // нужно нормировать, так как число строк в ТЗ ограничено в отличии от случая "классического" логарифмического распределения
    Для ё = 0 По ВГраница Цикл
        Ответ[ё] = Ответ[ё] / Ответ[ВГраница]
    КонецЦикла;
    Возврат Ответ    
КонецФункции

Функция ЛогарифмическоеСлучайноеЧисло() Экспорт
    Икс = ГСЧ.СлучайноеЧисло(0, 4294967295) / 4294967295;
    Для ё = 0 По МассивФункцииРаспределения.ВГраница() Цикл
        Если Икс <= МассивФункцииРаспределения[ё] Тогда
            Возврат ё + 1
        КонецЕсли
    КонецЦикла
КонецФункции

Процедура Подготовка() Экспорт
    МассивФункцииРаспределения = Распределение(Тэта);
КонецПроцедуры

ГСЧ = Новый ГенераторСлучайныхЧисел();

ТаблицаВыбора здесь - это таблица значений, из которой производится выбор элементов.

23. Оптимизация подбора кусков заданного суммарного метража методом ветвей и границ

http://www.forum.mista.ru/topic.php?id=745022&page=1

http://forum.infostart.ru/forum26/topic138663/

Имеется таблица "Метраж", содержащая информацию о количестве кусков и их метраже: индекс куска, количество кусков, размер куска, общий метраж индекса. Требуется при вводе заданного метража подобрать куски, оптимально составляющие заданный метраж. Желательно использовать минимум кусков вообще и минимум разных кусков.

Задача решается методом ветвей и границ. Этот метод заключается в сокращенном переборе вариантов. Сокращение достигается за счет предварительной оценки развиваемого варианта. Если оценка хуже уже полученного рекорда, развитие прекращается. В первую очередь развиваются самые перспективные варианты.

Решение представляет собой две функции. В первой производится подготовка, а во второй рекурсивной функции - собственно решение:

 

Процедура КнопкаСформироватьНажатие(Кнопка) 
    РабочаяТаблица = Метраж.Выгрузить(); 
    РабочаяТаблица.ЗаполнитьЗначения(Метраж.Итог("Имеется"), "НужноВзять"); 
    Метраж.ЗагрузитьКолонку(РабочаяТаблица.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
    РабочаяТаблица.ЗаполнитьЗначения(0, "НужноВзять"); 
    РабочаяТаблица.Сортировать("Коэффициент Убыв"); 
    ПодборКусков(РабочаяТаблица, РабочаяТаблица.Количество() - 1, Требуется) 
КонецПроцедуры

Процедура ПодборКусков(РабочаяТаблица, ВГраница, ЗаданнаяСумма, УжеВзяли = 0) Экспорт  
    Если ВГраница < 0 ИЛИ ЗаданнаяСумма < 0 ИЛИ УжеВзяли >= Метраж.Итог("НужноВзять") Тогда //промах  
        Возврат      
    ИначеЕсли ЗаданнаяСумма = 0 Тогда //фиксируем решение  
        Ответ = РабочаяТаблица.Скопировать( , "НомерСтроки, НужноВзять"); 
        Ответ.Сортировать("НомерСтроки"); 
        Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять")  
    КонецЕсли;  
    Курсор = РабочаяТаблица[ВГраница];  
    Для НужноВзять = 0 По Курсор.Имеется Цикл  
        Курсор.НужноВзять = НужноВзять;  
        ПодборКусков(РабочаяТаблица, ВГраница - 1, ЗаданнаяСумма - НужноВзять * Курсор.Коэффициент, УжеВзяли + НужноВзять);          
        Курсор.НужноВзять = 0 
    КонецЦикла 
КонецПроцедуры // ПодборКусков() 

  

22. Объединение данных двух периодических регистров

http://forum.infostart.ru/forum26/topic111009/

Есть два периодических регистра. Первый содержит количества на дату (РегистрКоличество), а второй - состояния на дату (РегистрСостояние). Даты двух регистров независимы друг от друга. Требуется запросом построить третий "регистр", являющийся объединением первых двух, чтобы показывались соответствующие друг другу даты, количества и состояния.

Вот короткое решение с использованием коррелированных запросов (ахтунг!):

ВЫБРАТЬ
    ВЫБОР
        КОГДА ТаблицаКоличества.Дата > ТаблицаСостояний.Дата
            ТОГДА ТаблицаКоличества.Дата
        ИНАЧЕ ТаблицаСостояний.Дата
    КОНЕЦ КАК Дата,
    ТаблицаКоличества.Количество КАК Количество,
    ТаблицаСостояний.Состояние КАК Состояние
ИЗ
    ТаблицаКоличества КАК ТаблицаКоличества
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТаблицаСостояний КАК ТаблицаСостояний
        ПО (ТаблицаСостояний.Дата В
                    (ВЫБРАТЬ
                        МАКСИМУМ(ТаблицаСостояний.Дата)
                    ИЗ
                        ТаблицаСостояний КАК ТаблицаСостояний
                    ГДЕ
                        ТаблицаСостояний.Дата <= ТаблицаКоличества.Дата)
                ИЛИ ТаблицаКоличества.Дата В
                    (ВЫБРАТЬ
                        МАКСИМУМ(ТаблицаКоличества.Дата)
                    ИЗ
                        ТаблицаКоличества КАК ТаблицаКоличества
                    ГДЕ
                        ТаблицаКоличества.Дата <= ТаблицаСостояний.Дата))

 

 

приемы программирования решения

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

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

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

1 стартмани

30.01.2024    1714    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

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

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

19.10.2023    4316    user1959478    50    

34

Регулярные выражения на 1С

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

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

1 стартмани

09.06.2023    7343    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

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

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

1 стартмани

21.03.2022    7817    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

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

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4414    fishca    13    

36

Интересная задача на Yandex cup 2021

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

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8793    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7713    dusha0020    8    

70
Отзывы
59. ildarovich 7846 04.07.16 23:09 Сейчас в теме
(58) Ovrfox, посмотрел еще раз внимательно код из (35) и (54). Увидел, наконец, существенную разницу своего (действительно с избыточным перебором) и вашего решения задачи 23.
Ваша идея в том, чтобы вести перебор в порядке возрастания числа кусков. Сначала все варианты с одним куском, потом с двумя, с тремя и так далее. При этом, чтобы пропустить начальный этап, жадным алгоритмом выбирается минимально необходимое число кусков. Это действительно эффективная стратегия для решения этой конкретной задачи, вы меня убедили.
Мне пришлось переписать рекурсию для реализации этой стратегии. Получилось достаточно кратко.
Проверю все еще раз и поменяю решение в статье.
А пока вот моя реализация перебора из (35). Если вместо массива хранить вариант в строке из "0" и "1", то вот функция, получающая следующий вариант на основе текущего в коде "роста". Без циклов!
Функция СледующийКод(Код)
	Возврат Прав(СтрЗаменить(Код, "1", "0") + Лев("1" + Код, Найти(Код, "0")) 
	+ ?(Найти(Код, "01"), "0", "") + Сред(Код, Найти(Код + "01", "01") + 2), СтрДлина(Код))
КонецФункции

Для начального значения "00000" получаем последовательность:
"00000","00001","00010","00100","01000","10000","00011","00101",
"01001","10001","00110","01010","10010","01100","10100","11000",
"00111","01011","10011","01101","10101","11001","01110","10110",
"11010","11100","01111","10111","11011","11101","11110","11111",
"00000".
Остальные комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Synoecium 777 24.02.16 06:44 Сейчас в теме
27. Округление в большую сторону
Есть более универсальный способ округлить в большую (или меньшую) сторону, который можно использовать в запросах, в коде и даже в вычисляемых полях СКД. По ссылке на ветку мисты есть упоминание о нем, но мне показалось что не очень внятно описано. Идея состоит в добавлении (или вычитании) числа близкого к 0.5 и округления по математическим правилам. Для запроса округление в большую и меньшую сторону будет выглядеть так:
ВЫБРАТЬ ВЫРАЗИТЬ (&Значение+0.499999 КАК Число(15,0) ) КАК ОкругленноеВБольшуюСторону,
ВЫРАЗИТЬ (&Значение-0.499999 КАК Число(15,0) ) КАК ОкругленноеВМеньшуюСторону

Для отрицательных чисел можно предусмотреть условие с отдельной веткой если не устраивает округление по данной формуле
7. ildarovich 7846 24.02.16 16:51 Сейчас в теме
(1) Synoecium, тут я с вами поспорю:
1) Правильное выражение для округления в меньшую строну (взятие целого) вот такое:
ВЫРАЗИТЬ (&Значение-0.5 КАК Число(15,0) ) КАК ОкругленноеВМеньшуюСторону
Это все кругом используют, а вам нужно будет пересмотреть свой код в продакшен, так как на значении 0.999999 у вас будет получаться не 0 как правильно, а 1, что может вызывать трудноуловимые ошибки;
2) Выражение
ВЫРАЗИТЬ (&Значение+0.499999 КАК Число(15,0) ) КАК ОкругленноеВБольшуюСторону
вроде бы работает, но не правильно обрабатывает значение 0.0000009 и меньше - будет округлять их в меньшую строну, а не в большую. Поэтому в том обсуждении, на которое вы ссылались девяток было больше (помните - "не спортивно"). Хотя это дело вкуса, но мне кажется легче контролировать диапазон значений (выбором М), чем точность (числом девяток), с которой иногда случаются всякие фокусы.
NESSS; json; +2 Ответить
12. Synoecium 777 25.02.16 06:54 Сейчас в теме
(7) Вы за мой продакшен не беспокойтесь, мы здесь обсуждаем вашу статью.

ВЫРАЗИТЬ (&Значение-0.5 КАК Число(15,0) ) КАК ОкругленноеВМеньшуюСторону


дает неправильное решение для значения 0 например (получится -1 что неверно), но для положительных чисел соглашусь, такой вариант позволяет повысить точность. Предложенный метод нужно применять понимая ограничения накладываемые точностью вычислений, точность будет не менее, чем количество девяток в сдвиге (в приведенной формуле до 5 знаков).

вроде бы работает, но не правильно обрабатывает значение 0.0000009 и меньше - будет округлять их в меньшую строну, а не в большую.


так и задумано, нужно применять метод, зная про ограничения.
14. ildarovich 7846 25.02.16 09:27 Сейчас в теме
(12) Synoecium, для избежания коллизии [0] -> -1 лично я пишу в запросе
ВЫРАЗИТЬ (&Значение + 0.5 КАК Число(15,0) ) - 1 КАК ЦелаяЧасть
Что касается 27, то речь там идет прежде всего о коде, а не о запросе. В запросе мне как-то не приходилось пока с округлением в бОльшую сталкиваться, но добавлять 0.499999 лично я бы не стал, впрочем, ваши аргументы я услышал.
2. TODD22 18 24.02.16 07:44 Сейчас в теме
К минимализму 34. Ещё бы пример как свернуть ТЗ а текстовые строки сложить конкатенацией.... Вчера как раз бился над этим.
Ответ[ё] = Ответ[ё] / Ответ[ВГраница]

Ну и буква "ё" в коде это моветон.
SkyHunter; +1 1 Ответить
3. ildarovich 7846 24.02.16 11:30 Сейчас в теме
(2) TODD22, свернуть строки конкатенацией можно так:
Дано.Сортировать("Поле1, Поле2");
ё = Дано.Количество();
Пока ё > 1 Цикл
	ё = ё - 1;
    Если Дано[ё - 1].Поле1 = Дано[ё].Поле1 И Дано[ё - 1].Поле2 = Дано[ё].Поле2 Тогда
        Дано[ё - 1].Поле3 = Дано[ё - 1].Поле3 + Дано[ё].Поле3;
        Дано.Удалить(ё)
    КонецЕсли 
КонецЦикла;
Показать
Но я бы не стал объединять этот прием с другими. В 34 можно находить агрегатные максимум, минимум и так далее для части полей НАРЯДУ с обычным суммированием для других полей. А при конкатенации ненужные строки приходится жестко удалять, поэтому по смыслу прием другой, хотя тоже короткий и полезный.
4. ildarovich 7846 24.02.16 11:41 Сейчас в теме
(2) TODD22, по поводу буквы "ё". Хотелось бы разобраться откуда растут ноги у этого убеждения. Здесь уже был спор на эту тему. Да, 1С когда-то в каких-то замшелых инструкциях не рекомендовала эту букву. Но почему? -Не является ли это просто нездоровым консерватизмом человека, написавшего инструкцию, позицией КакБыЧегоНеВышло? Не пора ли ее пересмотреть? Буква ё очень нарядная и украшает код, особенно в качестве итератора. Как i или j.
Многие на партнерском форуме поддержали идею реабилитировать эту букву.
CyberBob; user601481_t; DrAku1a; NESSS; user612495_easydurrrr; AnryMc; grimih; proger1c81; susumi83; artbear; so-quest; soulsteps; _also; orfos; Yashazz; +15 Ответить
5. TODD22 18 24.02.16 11:50 Сейчас в теме
(4)
Многие на партнерском форуме

5 человек на форуме это далеко не многие:)

Я например считаю что если есть требование и это стандарт то нужно его придерживаться. Не зависимо от того есть технические сложности или нет.

А то что "кто то считает" букву нарядной это же не аргумент.

Я видел код людей которые считали нарядным делать счётчики i j в коде 1С. И вообще кто только как свой код не наряжает.

А хотелось бы видеть код приближенный максимально к стилю в типовых. Что бы потом того кто наряжал добрым словом не вспоминать.
AKnyazkov; +1 Ответить
6. TODD22 18 24.02.16 11:51 Сейчас в теме
(4)
Не пора ли ее пересмотреть?

Как только в соглашениях по написанию кода не будет написано что нельзя использовать букву ё тогда можно будет и пересмотреть.
А так получается что ты пересмотрел в одностороннем порядке :)
37. AnryMc 849 16.06.16 10:31 Сейчас в теме
(4)
Буква ё очень нарядная и украшает код, особенно в качестве итератора.

;-))
71. DenisCh 11.11.16 09:43 Сейчас в теме
(4) "1С когда-то в каких-то замшелых инструкциях не рекомендовала эту букву."

Достаточно вспомнить приснопамятный Счётчик() в 77
8. DJDUH 17 24.02.16 17:27 Сейчас в теме
За 37. Генератор вариантов формул особое спасибо!
9. Evil Beaver 8100 24.02.16 17:30 Сейчас в теме
Маэстро вообще любит переменные с именами ж, ё, й и подобные. Сильно помогает в попытках разобраться с кодом :)
mike_grig; abasovit; SkyHunter; +3 Ответить
10. TODD22 18 24.02.16 17:56 Сейчас в теме
(9) Evil Beaver, Так про "й, щ, ы" ничего не сказано в соглашении :) А вот про ё сказано явно.
11. DrAku1a 1678 25.02.16 02:37 Сейчас в теме
Единственное, что может быть как претензия к букве "ё" - это то, что она стоит отдельно от основного алфавитного ряда в таблице ASCII-символов. Ну и ёщё - не любят эту букву в печатных изданиях (это очень-очень давняя история). Я за то, чтобы реабилитировать Ё. Но вот, как счётчик цикла... Читаем код в стиле рэпа :)

Автору в очередной раз - Респект!
Не могу понять, как работает запрос из "35. Выбрать в запросе одну запись из нескольких"?
13. klinval 337 25.02.16 09:21 Сейчас в теме
В запросе "35. Выбрать в запросе одну запись из нескольких" не хватает "РАЗЛИЧНЫЕ". Например если в конце таблицы добавить ещё одну запись Петя 1 1 1 1, то появится дубляж. "Различные" это исправит.
ildarovich; +1 Ответить
15. ildarovich 7846 25.02.16 09:29 Сейчас в теме
(13) klinval, согласен, поправлю в статье
16. Synoecium 777 25.02.16 11:26 Сейчас в теме
Минимализм 35. Интересное решение через коррелированный запрос, не знал про такой. По условию задачи предполагается, что нам неважно какая именно из записей с одинаковыми ключами (ключом в данном случае выступает поле Ф) попадет в результирующую выборку. Однако на практике часто необходимо выбрать записи согласно какому то порядку, тогда можно использовать следующий метод, при условии, что неключевые поля можно сравнивать по условию <,>:
ВЫБРАТЬ
Дано.Ф,
Дано.К1,
Дано.К2,
Дано.К3,
Дано.К4
ИЗ
Дано КАК Дано
ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Дано1
ПО Дано.Ф = Дано1.Ф
И (ВЫБОР
КОГДА Дано.К1 > Дано1.К1
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 > Дано1.К2
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 = Дано1.К2
И Дано.К3 > Дано1.К3
ТОГДА ИСТИНА
КОГДА Дано.К1 = Дано1.К1
И Дано.К2 = Дано1.К2
И Дано.К3 = Дано1.К3
И Дано.К4 >= Дано1.К4
ТОГДА ИСТИНА
ИНАЧЕ ЛОЖЬ
КОНЕЦ)

СГРУППИРОВАТЬ ПО
Дано.Ф,
Дано.К1,
Дано.К2,
Дано.К3,
Дано.К4

ИМЕЮЩИЕ
КОЛИЧЕСТВО(Дано1.Ф) = 1

При использовании следует учесть, что среди записей не должно быть полных дубликатов, так как они будут исключены из выборки.
ildarovich, интересно узнать, можно ли в коррелированном запросе использовать упорядочивание, для решения такой задачи?
ildarovich; +1 Ответить
18. ildarovich 7846 25.02.16 12:03 Сейчас в теме
(16) Synoecium, нет, не прокатывает, только если не множественные операнды - то есть уникальное поле еще нужно. А так вот такое сообщение появляется:
Недопустимо использовать упорядочивание внутри запроса, вложенного в операцию В с множественными операндами, если есть обращения к полям внешнего запроса
83. пользователь 28.07.20 18:56
Сообщение было скрыто модератором.
...
17. igormiro 714 25.02.16 11:48 Сейчас в теме
Большое спасибо за статью. Однозначно +.
Вот еще очень нужная функция, помещает таблицу значений, или табличную часть, в менеджер временных таблиц.
              Функция    ПоместитьТаблицуВМенеджерВременныхТаблиц(Знач ТаблицаИсточник, ИмяТаблицы = "ТЗ", МенеджерВТ = Неопределено, Колонки = Неопределено) Экспорт
	 
	 Если ТипЗнч(ТаблицаИсточник) <> Тип("ТаблицаЗначений") Тогда
		 Сообщить("Ошибка таблицы источника данных!", СтатусСообщения.Внимание);
		 Возврат Неопределено;
	 КонецЕсли;
	 
	 Если МенеджерВТ = Неопределено Тогда
		 МенеджерВТ = Новый МенеджерВременныхТаблиц;
	 КонецЕсли;
	 
	 ТекстЗапроса = ""; 
	 Если Колонки = Неопределено Тогда
		 ТаблицаРез = ТаблицаИсточник;
		 Для каждого стр Из ТаблицаРез.Колонки Цикл
			 Если ПустаяСтрока(ТекстЗапроса) Тогда
				 ТекстЗапроса = "Выбрать " +ИмяТаблицы +"."+ стр.Имя + " как " +стр.Имя +", 
				 |";
			 Иначе
				 ТекстЗапроса = ТекстЗапроса +ИмяТаблицы +"."+ стр.Имя + " как " +стр.Имя +", 
				 |";					
			 КонецЕсли;			
		 КонецЦикла;
	 Иначе
		 ТаблицаРез = ТаблицаИсточник.Скопировать();
		 МассивКолонок = ОбщегоНазначения.РазложитьСтрокуВМассивПодстрок(Колонки,","); 
		 Сч = 0; 
		 Пока Сч < ТаблицаРез.Колонки.Количество() Цикл
			 Стр = ТаблицаРез.Колонки[Сч];
			 Если МассивКолонок.Найти(Стр.Имя) <> Неопределено Тогда
				 Если ПустаяСтрока(ТекстЗапроса) Тогда
					 ТекстЗапроса = "Выбрать " +ИмяТаблицы +"."+ стр.Имя + " как " +стр.Имя +", 
					 |";
				 Иначе
					 ТекстЗапроса = ТекстЗапроса +ИмяТаблицы +"."+ стр.Имя + " как " +стр.Имя +", 
					 |";			
				 КонецЕсли;	
				 Сч = Сч + 1;
			 Иначе
				 ТаблицаРез.Колонки.Удалить(Стр);
			 КонецЕсли;
		 КонецЦикла;
	 КонецЕсли;
	 
	 ТекстЗапроса = Лев(ТекстЗапроса, СтрДлина(ТекстЗапроса)-3);                                                 
	 ТекстЗапроса = ТекстЗапроса + " поместить "+ ИмяТаблицы +"
	 |  из &" + ИмяТаблицы + " как " + ИмяТаблицы
	 +" ;";
	 Запрос = Новый Запрос;
	 Запрос.МенеджерВременныхТаблиц = МенеджерВТ;
	 Запрос.Текст =  ТекстЗапроса;
	 Запрос.УстановитьПараметр(ИмяТаблицы,ТаблицаРез);
	 Попытка
		 Запрос.Выполнить();
	 Исключение
		 Сообщить(""+ОписаниеОшибки(), СтатусСообщения.Внимание);
		 МенеджерВТ = Неопределено;
	 КонецПопытки;
	 
	 Возврат МенеджерВТ;      
	 
 КонецФункции
Показать
19. ildarovich 7846 25.02.16 12:07 Сейчас в теме
(17) igormiro, да, полезная функция. Давно хочу этот функционал к своей функции НовыйЗапрос добавить.
20. manlak 77 25.02.16 16:43 Сейчас в теме
Минимализм 35 на 1С 8.2 не работает, в том числе и на SQL,
т.е. если набрать, то выдаст изначальную таблицу

ВЫБРАТЬ
	"Петя" КАК Ф,
	1 КАК К1,
	1 КАК К2,
	0 КАК К3,
	0 КАК К4
ПОМЕСТИТЬ Дано

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Петя",
	1,
	1,
	0,
	1

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Петя",
	1,
	0,
	1,
	0

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Вася",
	1,
	1,
	0,
	0

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	"Женя",
	1,
	1,
	0,
	0
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Дано.Ф,
	Дано.К1,
	Дано.К2,
	Дано.К3,
	Дано.К4
ИЗ
	Дано КАК Дано
ГДЕ
	(Дано.Ф, Дано.К1, Дано.К2, Дано.К3, Дано.К4) В
			(ВЫБРАТЬ ПЕРВЫЕ 1
				ВСЁ.Ф,
				ВСЁ.К1,
				ВСЁ.К2,
				ВСЁ.К3,
				ВСЁ.К4
			ИЗ
				Дано КАК ВСЁ
			ГДЕ
				ВСЁ.Ф = Дано.Ф)
Показать
21. klinval 337 25.02.16 16:54 Сейчас в теме
(20) manlak, У меня всё работает (см. прикрепленный файл). В консоль запросов кинул полностью ваш запрос без изменений, в результирующей таблице 3 строки!
Прикрепленные файлы:
22. manlak 77 26.02.16 10:43 Сейчас в теме
(21) klinval, это если открывать в стандартном 8.2 "упп-демо" консоле отчетов (операции - обработка - Консоль отчетов), то выйдет 5 строк.
Если создать новый внешний отчет и скопировать код, тоже самое, будет 5 строк. Задачу можно решить через "максимум" в запросе на полях "К *"
25. klinval 337 29.02.16 13:59 Сейчас в теме
(22) manlak, выполнение такого запроса не должно зависеть от конфигурации. Хоть на пустой БД - везде должно быть одинаково! Возможно есть какая-нибудь зависимость от версии платформы? У меня на 8.3.7.1845 3 строчки! А у вас какая версия платформы?
28. lion11 143 27.05.16 10:13 Сейчас в теме
(20), (21). Действительно, п.35 на 8.2 не работает, а на 8.3. работает. Есть идеи, как заставить работать на 8.2?
23. arithmometr 152 26.02.16 14:23 Сейчас в теме
Минимализм 27. Округление в большую сторону
Я пользуюсь таким методом:
Окр(Ч + 0.5, 0); Окр(Ч + 0.05, 1); и т.п.
24. ildarovich 7846 26.02.16 15:00 Сейчас в теме
(23) arithmometr, почитайте обсуждение по ссылке, там было много разных методов, которые не все выдерживали критику. Ваш метод не соответствует пониманию округления в бОльшую в том смысле, что Окр(1+0.5, 0) дает 2, а по идее эта операция должна давать 1. Из тех предложений к предлагаемому вами методу ближе "неспортивный" (его так сам автор обозвал) метод Окр(Ч + 0.4999999999).
EMelihoff; +1 Ответить
26. pm74 199 25.03.16 12:04 Сейчас в теме
(0) К п. 36 пустой элемент массива я бы все же из результата убрал.
алгоритм в прикладных задачах имеет смысл использовать для множества не повторяющихся элементов.
Хотя с математической точки зрения все безукоризненно.
27. ildarovich 7846 25.03.16 12:25 Сейчас в теме
(26) pm74, думал над этим: ...с одной стороны лишняя запись в результате...с другой стороны ничему не мешает, совпадает с определением, текст программы короче, кому нужно допишет проверку... Вот эти рассуждения и перевесили, поэтому оставил элемент с пустым списком значений в результирующем массиве.
29. Ovrfox 14 15.06.16 14:47 Сейчас в теме
К задаче 31
Более быстрый и правильный код
ВЫБРАТЬ А, Б, КОЛИЧЕСТВО(*)
ИЗ (ВЫБРАТЬ А, Б ИЗ Дано ГДЕ А <= Б
ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ Б, А ИЗ Дано ГДЕ А > Б) КАК ВЗ
ubnkfl; Caliban; ildarovich; +3 Ответить
32. ildarovich 7846 15.06.16 22:17 Сейчас в теме
(29) Ovrfox, превосходное решение! Очевидно, лучше приведенного в статье. В общем-то, обсуждения для этого и нужны, чтобы находить такие решения.
Для себя вижу урок в том, что не потратил достаточно времени на улучшение решения задачи 31. А чувство неудовлетворенности путанностью условий в запросе было.
73. denis_aka_wolf 79 09.12.16 09:18 Сейчас в теме
(29) Ругается что поля А и Б не входят в группу
Весь мой запрос:

ВЫБРАТЬ "Овсянка" А, "Омлет" Б
ПОМЕСТИТЬ Дано 
ОБЪЕДИНИТЬ
ВЫБРАТЬ "Плов","Борщ"
ОБЪЕДИНИТЬ
ВЫБРАТЬ "Омлет","Овсянка"
ОБЪЕДИНИТЬ
ВЫБРАТЬ "Пельмени","Шашлык"
ОБЪЕДИНИТЬ
ВЫБРАТЬ "Борщ","Плов"
;

ВЫБРАТЬ А, Б, КОЛИЧЕСТВО(*) 
ИЗ (ВЫБРАТЬ А, Б ИЗ Дано ГДЕ А <= Б 
       ОБЪЕДИНИТЬ ВСЕ 
       ВЫБРАТЬ Б, А ИЗ Дано ГДЕ А > Б) ВЗ
Показать
74. ildarovich 7846 09.12.16 12:36 Сейчас в теме
(73) Вы правы, в запросе в 29 не хватает последней строчки СГРУППИРОВАТЬ ПО А,Б.
В итоге текст запроса должен выглядеть так:
ВЫБРАТЬ А, Б, КОЛИЧЕСТВО(*) 
ИЗ (ВЫБРАТЬ А, Б ИЗ Дано ГДЕ А <= Б 
       ОБЪЕДИНИТЬ ВСЕ 
       ВЫБРАТЬ Б, А ИЗ Дано ГДЕ А > Б) ВЗ
СГРУППИРОВАТЬ ПО А,Б
30. Ovrfox 14 15.06.16 15:21 Сейчас в теме
28 постановка задачи бредовая. Не могу предположить кому это нужно
Хотя запросы и решают поставленную задачу
33. ildarovich 7846 15.06.16 22:46 Сейчас в теме
(30) Ovrfox, мне постановка задачи бредовой не кажется. Да и ссылка говорит о том, что задача не придуманная. Этот запрос устраняет избыточность. А вообще с избыточностью приходится сталкиваться на каждом шагу. Взять хотя бы тоже кодирование RLE.
По сути, эта задача обратная по отношению к задаче "цены на каждый день", где избыточность намеренно вводится. Если там "распаковка", то тут "сжатие".
Сценариев использования довольно много.
Вот, например, возьмите сериализованные версии объектов, постройте методом из http://infostart.ru/public/336783/ хэши версий, да и уберите повторяющиеся версии. Ну и тому подобное.
31. Ovrfox 14 15.06.16 17:14 Сейчас в теме
Задача 23. Оптимизация подбора кусков заданного суммарного метража методом ветвей и границ
Не правильно решена: (как минимум не достаточно быстро)
Согласно решению есть цикл с реурсией. т.е. сложность задачи это n!
На самом деле требуется отобрать К кусков из N. В самом худшем случае к-во вариантов (по биному ньютона) 2^N (два в степени N) Откуда легко видеть , что сложность задачи слишком преувеличена.
В общем случае задачу лучше решать стандартным методом перебора вариантов:
1. Все куски, которые можно разделить, разделить и записать в массив (т.е. не строка с 4 кусками по 50 ,а 4 отдельных куска по 50)
2. Написать алгоритм, который выполнить перестановку кусков.
3. Для каждой перестановки простым способом посчитать разбиение (например суммировать куски в порядке возрастания номеров до набора нужной суммы)
Желательно объединить алгоритмы 2 и 3 чтобы не вычислять перестановку, которая не изменит результата, получаемого в 3.

Я считаю. что написать оптимизацию перестановок более чем по 1-му условию будет очень сложно (т.е. либо оптимизировать по количеству кусков, либо по кол-ву строк . если нужно оба условия - то отбирать полученные варианты по первой оптимизации и выбирать из них оптимальный по второму условию)
34. ildarovich 7846 15.06.16 23:15 Сейчас в теме
(31) Ovrfox, думаю, тут вы не до конца разобрались в коде.
Никакого n! там нет. Порядок использования кусков в разных вариантах одинаков и перестановок тут нет.
Оценка количества перебираемых вариантов: К1хК2хК3х...xKn, где К1 - увеличенное на 1 число кусков первого индекса и так далее.

Если все вытянуть в строку, как вы предлагаете, то в блоках кусков одного индекса будет лишний перебор из-за одинаковости вариантов 1000, 0100, 0010, 0001 (для четырех кусков первого индекса). А в целом 2^(К1+К2+К3+...+Kn) >> К1хК2хК3х...xKn, когда К > 2.

А вообще в целом решение выполнено в том же направлении мыслей, которые у вас описаны. Шаги 2 и 3 именно что объединены. Двухкритериальная оптимизация там неявная и именно последовательная: главный-второстепенный критерий. Вместо перестановки на каждом уровне рекурсии выбирается различное число кусков. Почитайте обсуждение по ссылке. Там были еще разные варианты совмещения критериев.

Это решение несколько раз проверено на двух конкретных практических задачах. Но мне оно ничем, кроме своей краткости не интересно.

Кстати, я тут ошибся с классификацией метода. Это метод сокращенного перебора, но не метод ветвей и границ. У МВГ должна быть структура данных для хранения множества не просмотренных вариантов с их оптимистичными оценками. Тут такой структуры нет, хотя и ветвления и отсечение и присутствуют.

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

Для продолжения спора на тему "недостаточно быстро" умозрительных построений недостаточно - нужно будет реализовать свое решение. Можно будет сравнить.
36. Ovrfox 14 16.06.16 10:24 Сейчас в теме
2(34)
Предположим что все отрезы разные, и нам нужны два наименьших отреза. При этом сумма двух наименьших больше длинны каждого куска
Число кусков 10
Предложенный вариант решения выполнится
на первом уровне 9 раз
на втором уровне вложенности 8 раз
и т.д
Т.е. , не N!, а (N-1)!
Если воспользоваться решением из 35-го поста или даже набором вариантов из 23-й задачи
То в худшем случае это будет 2 в степени N минус 1 вариант. Уверяю Вас, это значительно меньше.
42. ildarovich 7846 16.06.16 13:39 Сейчас в теме
(36) Ovrfox, вот еще ссылка на тему, где применялась это решение http://forum.infostart.ru/forum86/topic150129/.

Задал в своей обработке (прилагается) ваши данные (смотрите скриншот). При входе в функцию там стоит сообщить
Процедура ПодборКусков(РабочаяТаблица, ВГраница, ЗаданнаяСумма, Кусков, Использовано, Пустых, УжеВзяли = 0, УжеПустых = 0, УжеИспользовано = 0) Экспорт
	
	Сообщить("Шаг подбора");
	
	Если ВГраница < 0 ИЛИ ЗаданнаяСумма < 0	ИЛИ УжеВзяли > Кусков ИЛИ УжеИспользовано > Использовано Тогда
Из скриншота видно, что шагов подбора выполнилось 28. Это не факториал.
Прикрепленные файлы:
Рюкзак.erf
43. Ovrfox 14 17.06.16 11:11 Сейчас в теме
(42) Да. я уже писал, что я пересчитал ряд и худшая оценка совпадает со всеми вариантами, а именно 2 в степени N минус 1
Код перебора мой, написал специально под задачу. Когда использую сам - обычно совмещаю 2 и 3-й шаги, поэтому код совсем другой. Идея - таже.
44. ildarovich 7846 17.06.16 11:22 Сейчас в теме
(43) Ovrfox, если вторая часть про мой ответ в (40), то я имел ввиду "код Грэя" https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%93%D1%80%D0%B5%D1%8F . Он является математической основой алгоритма, который вы привели в (35).
45. Ovrfox 14 21.06.16 10:06 Сейчас в теме
(44) Было интересно читать о коде Грея. Не могу утверждать, что алгиртмы чем-то похожи - я не нашел похожего алгоритма генерации кода Грея.
Но согласно определению кода грея - мой алгоритм генерит последовательность, которая им не является. Т.е. на определенных шагах алгоритма следующее значение отличается от предыдущего более чем на один элемент.
46. ildarovich 7846 21.06.16 11:51 Сейчас в теме
(45) Ovrfox, да, я уже понял, что поторопился с выводами. Нужно будет повнимательнее рассмотреть код, приведенный в (35). Беглый взгляд не помог мне прояснить идею.
Все же кажется, что если ставится задача просто перебрать все варианты подряд по одному, то код должен быть короче.
Нужно просто ввести счетчик вариантов, а вхождение элемента в вариант определять наличием единицы в двоичном представлении счетчика.
Функция ПолучитьСледующий(Вариант, НомерВарианта = 0, Разряд = 0)
    Вариант.Очистить();
    Код = НомерВарианта;
    Пока Код > 0 Цикл
        Если  Код % 2 Тогда
            Вариант.Добавить(Разряд)
        КонецЕсли;
        Код = Цел(Код / 2);
        Разряд = Разряд + 1 
    КонецЦикла;
    НомерВарианта = НомерВарианта + 1;
    Возврат Истина;
КонецФункции
Показать
Зато запрограммировал перебор в коде Грэя (чуть позже покажу), решил новым способом обработку битовых строк. Для меня обсуждение оказалось полезным.
47. Ovrfox 14 21.06.16 18:00 Сейчас в теме
(46) Для простого перебора - конечно. Но идея в том, что следующий вариант берется из текущего. А текущий может быть получен специальным способом.
Для перебора отрезов: отрезы уже упорядочены по величине. Первый вариант мы набираем в лоб, начиная с больших кусков. И можем продолжить перебор, пропустив все меньшие варианты. При этом мы не храним все полученные варианты - т.е. не тратим на них память. Для больших чисел (а 20 - это уже большое, т.к. к-во вариантов миллион) это может кардинально улучшить процесс перебора (если для хранения вариантов оперативной памяти будет недостаточно).
49. ildarovich 7846 22.06.16 12:08 Сейчас в теме
+(46) (45) Ovrfox, вот новая статья "Простая и быстрая эмуляция операций с битовыми строками". На идеи, изложенные в ней, меня натолкнуло наше обсуждение.
Там показано, как получить новый вариант из старого изменением одного элемента (исключением или добавлением). Без единого цикла!
По сравнению с кодом в (35) это и проще и быстрее.
Решение в (35) вам будет трудно защитить, как мне кажется. Поскольку в нем нет ясной математической идеи, а у перебора на основе кода Грэя она есть.
50. Ovrfox 14 22.06.16 12:58 Сейчас в теме
(49) Я взял свой код из практики решений как раз аналогично вида задач, как с отрезами.
Как вы догадываетесь, простой перебор это слишком много вариантов. Их количество нужно уменьшать.
Код грея нельзя согласовать с отбором очередного начального варианта, а мой код можно. Именно соединение этих алгоритмов приводит к значительной эффективности общего алгоритма.

Спасибо за ссылку на интересную статью.
51. ildarovich 7846 22.06.16 13:18 Сейчас в теме
(50) Ovrfox, мне кажется, мы потеряли нить рассуждений...
Мне казалось, что первоначально код из (35) предлагался для задачи 36, чтобы не хранить варианты, а проверять их сразу.
Если хотите применить этот код к задаче 23, то доработайте его для нее! И попробуйте найти им решение задачи как на картинке в (42). Вы увидите, что чисто переборный метод здесь не годится. Метод из 23 не чисто переборный. Он отсекает в процессе перебора множество решений.
Предлагать код из (35) к решению задачи 23 очень и очень неправильно.
Когда вы попробуете его доработать, то пройдете длинный путь и придете таки к варианту наподобие предложенного в статье.
Чтобы в этом убедиться, нужно взять из (42) обработку. Я ее уже приготовил для вас. Встроить туда свой код. И попытаться переиграть по времени мою функцию. У вас ничего не получится. Следовательно, все, что вы говорили и говорите (?) о якобы неэффективности решения задачи 23, об оценках его трудоемкости и о каких-либо преимуществах перебора из (35) - бездоказательно.
52. Ovrfox 14 22.06.16 16:08 Сейчас в теме
(51) Хорошо, я напишу
А Вы пока исправьте ошибку
Алгоритм в вашей обработке не возвращает результат, если в него входит максимальное значение (т.е. строка с наибольшими кусками)
53. ildarovich 7846 22.06.16 17:17 Сейчас в теме
(52) Ovrfox, ОК, вот поправленная обработка из (42). Поменял местами проверку условий промаха и фиксации решения. В статье поменяю позже, когда еще раз всесторонне проверю.
Прикрепленные файлы:
Рюкзак.erf
54. Ovrfox 14 23.06.16 11:59 Сейчас в теме
(53) Добавил алгоритм подбора кусков, добавил также поиск следующего варианта (Кнопка продолжить).
Исходный алгоритм перенес на кнопку "Перебор"
Кстати, Ваш алгоритм выполняет отбор меньшими кусками, а в условии задачи, как я понял, требуется отбор большими кусками. Исправить просто - изменить порядок сортировки на противоположный.
Алгоритмы можно сравнивать просто зрительно, настолько сильно отличается время работы алгоритмов. Для замедления "переборного" алгоритма нужно увеличить кол-во кусков. И количество требуемых кусков в отборе.
По к-ву шагов сравнивать нельзя, это "попугайные" показатели.
Прикрепленные файлы:
Рюкзак.erf
55. ildarovich 7846 24.06.16 12:04 Сейчас в теме
(54) Ovrfox, посмотрел, спасибо, буду все это объяснять, но чуть позже.
56. Ovrfox 14 24.06.16 13:08 Сейчас в теме
(55) Как я уже говорил, но повторю еще раз. Основная идея предложенного мной алгоритма в том, что текущего варианта достаточно для продолжения поиска следующих вариантов.
Ну и конечно то, что нет рекурсии или предварительного создания всех возможных вариантов.
Хотя, конечно же , при плохих начальных условиях алгоритм будет все же перебирать варианты.
57. ildarovich 7846 24.06.16 13:47 Сейчас в теме
(56) Ovrfox, я это понял.

Я не согласен с тем, что вы подаете свой алгоритм как лучший. Сейчас я думаю, что они, по крайней мере, равноценны. Основная разница между ними - в том, что "мой" принципиально основан на рекурсии. А ваш - на цикле. В результате мой гораздо короче, а ваш проще останавливать и продолжать с прерванного места. Но и тот и другой можно подстроить на примерно одинаковую трудоемкость.

Хочу также объяснить почему получилась разница в быстродействии в обработке из (54) (не в пользу моего решения). Дело в том, что рекурсия перебирает все варианты, не худшие уже найденных. Она не останавливается, найдя первое решение. То есть в одной кнопке две ваших: остановить и продолжить, продолжить, продолжить.
Поэтому честнее было бы сравнивать скорость до попадания на фрагмент
ЗаданнаяСумма = 0 Тогда //фиксируем решение  
        Ответ = РабочаяТаблица.Скопировать( , "НомерСтроки, НужноВзять"); 
        Ответ.Сортировать("НомерСтроки"); 
        Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять")
Также у вас (как я понял) только один критерий - число кусков. Это - классическая задача о ранце. И вариант, как вы правильно и делаете, нужно развивать, беря максимально возможное количество самых больших кусков.
В моем решении "заказчик" (не настоящий, а собеседник на форуме) еще хотел обойтись минимальным количеством типоразмеров и по возможности выбирать типоразмеры до нуля. Поэтому у меня перебор не идет так круто в сторону решения из минимального количества кусков. Это также его задерживает. Но это можно перенастроить, поменяв на обратный порядок в цикле:
Для НужноВзять = - Курсор.Имеется По 0 Цикл
Но все же в данной статье я делал акцент на краткости кода и демонстрации того, что сложные задачи (без ущерба для производительности) можно решать иногда несколькими строчками. Пример именно об этом. Ваше решение буду иметь ввиду. Если придется использовать, постараюсь записать его короче.
58. Ovrfox 14 24.06.16 15:00 Сейчас в теме
(57) Решение, которое я предоставил все же лучше, потому что объеденены в нем два этапа
2-й (Подбор кусков в лоб с наибольших кусков) и
3-й Собственно перебор вариантов.
Из-за этого пересечения часть неподходящих варинатов отсеивается на каждом проходе

А именно - когда мы уменьшаем к-во в i-той строке - мы не перебираем все варианты для кусков с i+1 по n , а начинаем с уже ограниченного оставшимся метражом подбором кусков.
Поэтому к-во вариантов, которые отсеиваются без проверки значительно превышает кол-во проверяемых вариантов.

PS: Меня просто смутило то, что задача с порядком сложности 2^N решается путем прямого перебора.
Я считаю, выкладывать подобный код нужно для того, чтобы его не использовали. Как , например, алгоритм сортировки пузырьком.
59. ildarovich 7846 04.07.16 23:09 Сейчас в теме
(58) Ovrfox, посмотрел еще раз внимательно код из (35) и (54). Увидел, наконец, существенную разницу своего (действительно с избыточным перебором) и вашего решения задачи 23.
Ваша идея в том, чтобы вести перебор в порядке возрастания числа кусков. Сначала все варианты с одним куском, потом с двумя, с тремя и так далее. При этом, чтобы пропустить начальный этап, жадным алгоритмом выбирается минимально необходимое число кусков. Это действительно эффективная стратегия для решения этой конкретной задачи, вы меня убедили.
Мне пришлось переписать рекурсию для реализации этой стратегии. Получилось достаточно кратко.
Проверю все еще раз и поменяю решение в статье.
А пока вот моя реализация перебора из (35). Если вместо массива хранить вариант в строке из "0" и "1", то вот функция, получающая следующий вариант на основе текущего в коде "роста". Без циклов!
Функция СледующийКод(Код)
	Возврат Прав(СтрЗаменить(Код, "1", "0") + Лев("1" + Код, Найти(Код, "0")) 
	+ ?(Найти(Код, "01"), "0", "") + Сред(Код, Найти(Код + "01", "01") + 2), СтрДлина(Код))
КонецФункции

Для начального значения "00000" получаем последовательность:
"00000","00001","00010","00100","01000","10000","00011","00101",
"01001","10001","00110","01010","10010","01100","10100","11000",
"00111","01011","10011","01101","10101","11001","01110","10110",
"11010","11100","01111","10111","11011","11101","11110","11111",
"00000".
39. Ovrfox 14 16.06.16 11:34 Сейчас в теме
2(34) (36) Оценил алгоритм еще раз. Получил оценку 2 в степени N
Делаю вывод, что алгоритм скорее всего правильный. Но не верю.
Привести пример, когда он неправильный не могу.
35. Ovrfox 14 16.06.16 10:08 Сейчас в теме
К задаче 36. Алгоритм перебора всех возможных сочетаний элементов
Касается задачи 23
Хранить в массиве все варианты - достаточно грубо, особенно когда вариантов много , а решение можно найти в первой тысяче вариантов.
Например такой код получения вариантов значительно проще
 Функция ПолучитьСледующий(Вариант, Кво)
	КвоВварианте = Вариант.ВГраница();
	Сдвиг = 0;	Нач = 0;
	Для Обр = 0 По КвоВварианте Цикл
		Если Вариант[КвоВварианте - Обр]= Кво - Сдвиг Тогда
			Сдвиг = Сдвиг + 1;
			Вариант.Удалить(КвоВварианте - Обр);
		Иначе
			Нач = Вариант[КвоВварианте - Обр] + 1;
			Вариант[КвоВварианте - Обр] = Нач;
			прервать;
		КонецЕсли; 
	КонецЦикла;
	Если Сдвиг < Кво Тогда
		Если Вариант.ВГраница() = -1 Тогда
			Сдвиг = Сдвиг + 1;
		КонецЕсли;
		Для Ном = 1 По Сдвиг Цикл
			Вариант.Добавить(Нач+Ном);
		КонецЦикла; 
	ИначеЕсли Сдвиг <> 0 Тогда
		Возврат Ложь;
	КонецЕсли; 
	Возврат Истина;
КонецФункции
Показать

Где в качестве начального варианта нужно использовать либо специальный массив с 0, либо просто первый вариант (массив , содержащий индекс 1)
Приведенный код получает следующий вариант на основе предыдущего и НЕ Повторяет варианты, идентичные за исключением перестановки элементов.

ildarovich; +1 Ответить
40. ildarovich 7846 16.06.16 12:31 Сейчас в теме
(35) Ovrfox, код Грэя? - Мне он очень нравится, согласен. Но когда мне это понадобится, постараюсь написать сам.
48. Ovrfox 14 21.06.16 18:04 Сейчас в теме
(35) (39) (43) И кстати, алгоритм действительно перебирает все варианты. Но происходит это в лоб оценка О(2^N-1)
38. AnryMc 849 16.06.16 10:34 Сейчас в теме
Просто ассоциировалось...
Сафронова Наталья Григорьевна
МИНИМАЛИЗМЫ;
1
У творчества немало бед.
И не возможно не предвидеть;
Писать стихи, других обидеть.
А не писать - себе во вред.
корум; ildarovich; +2 Ответить
41. ildarovich 7846 16.06.16 12:39 Сейчас в теме
(38) AnryMc, вот это тоже подходит к случаю (Анна Ахматова):
Когда б вы знали, из какого сора
Растут стихи, не ведая стыда.
Как желтый одуванчик у забора,
Как лопухи и лебеда.
Сердитый окрик, дегтя запах свежий,
Таинственная плесень на стене...
И стих уже звучит, задорен, нежен.
На радость всем и мне.
60. Ovrfox 14 05.07.16 14:08 Сейчас в теме
Обязательно посмотрю новый алгоритм.
Жаль, что рекурсивный алгорим скорее всего не позволит продолжить перебор вариантов.
61. ildarovich 7846 07.07.16 12:48 Сейчас в теме
(60) Ovrfox, вот, можете посмотреть, что пока получается. Это рекурсия с ПРОДОЛЖЕНИЕМ перебора вариантов. Пока не могу решить, стоит ли логику продолжения оставлять для статьи, поскольку код все таки усложняется (это все, связанное с переменной ОК, которая равна ИСТИНА с момента нахождения очередного решения: чтобы вернуться из рекурсии, а затем зайти на те же места).
Но все равно код ОЧЕНЬ короткий:
Функция ОдинВариант(Стек, ё, Сумма, ОК) Экспорт
	Стек[ё].НужноВзять = ?(ОК, Стек[ё].НужноВзять, Мин(Стек[ё].Имеется, Цел(Сумма / Стек[ё].Коэффициент)));
	Пока ё > 0 
		И (Сумма > Стек[ё].НужноВзять * Стек[ё].Коэффициент ИЛИ ОК) 
		И НЕ ОдинВариант(Стек, ё - 1, Сумма - Стек[ё].НужноВзять * Стек[ё].Коэффициент, ОК) 
		И НЕ ОК 
		И Стек[ё].НужноВзять > 0 Цикл
		Стек[ё].НужноВзять = Стек[ё].НужноВзять - 1
	КонецЦикла;
	ОК = ?(Сумма = Стек[ё].НужноВзять * Стек[ё].Коэффициент, НЕ ОК, ОК);
	Один = НЕ ОК И Стек[ё].НужноВзять = Стек[ё].Имеется;
	Стек[ё].НужноВзять = ?(ОК, Стек[ё].НужноВзять, 0);
	Возврат Один
КонецФункции

Процедура ОсновныеДействияФормыРекурсия(Кнопка)
	Стек = Метраж.Выгрузить();
	Стек.ЗаполнитьЗначения(0, "НужноВзять");
	Стек.Сортировать("Коэффициент Возр");
	ОдинВариант(Стек, Стек.Количество() - 1, Требуется, Ложь);
	Ответ = Стек.Скопировать( , "НомерСтроки, НужноВзять"); 
    Ответ.Сортировать("НомерСтроки"); 
    Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
КонецПроцедуры

Процедура ОсновныеДействияФормыРекурсияПродолжить(Кнопка)
	Стек = Метраж.Выгрузить();
	Стек.Сортировать("Коэффициент Возр");
	ОдинВариант(Стек, Стек.Количество() - 1, Требуется, Истина);
	Ответ = Стек.Скопировать( , "НомерСтроки, НужноВзять"); 
    Ответ.Сортировать("НомерСтроки"); 
    Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
КонецПроцедуры
Показать
Прикрепленные файлы:
РюкзакСравнение.erf
62. Ovrfox 14 12.07.16 11:39 Сейчас в теме
(61) Здравствуйте
Я немного упростил (для понимания) ваш алгоритм рекурсии и заодно дополнил нерекурсивной функцией
После чего возник вопрос - в чем смысл рекурсии для подобного алгоритма? Цикл лень написать?
Функция ОдинВариант(Стек, Всё, Знач Сумма = 0) Экспорт
	ё=?(Сумма=0,0, Всё + 1);
	Пока Истина Цикл
		Пока ё > 0 цикл
			ё = ё - 1;
			Стек[ё].НужноВзять = Мин(Стек[ё].Имеется, Цел(Сумма / Стек[ё].Коэффициент));
			Сумма = Сумма - Стек[ё].НужноВзять * Стек[ё].Коэффициент;
			Если Сумма = 0 тогда
				Возврат Истина;
			КонецЕсли;
		КонецЦикла;
		Пока ё <= Всё И Стек[ё].НужноВзять = 0 Цикл
			ё = ё + 1;
		КонецЦикла;
		если ё <= Всё Тогда
			Сумма = Сумма + Стек[ё].Коэффициент;
			Стек[ё].НужноВзять = Стек[ё].НужноВзять -1;
		Иначе
			Возврат Ложь;
		КонецЕсли;
	КонецЦикла;
КонецФункции

Функция ОдинВариантРекурсия(Стек, Всё, Знач Сумма = 0, ё) Экспорт
	Пока ё > 0 цикл
		ё = ё - 1;
		Стек[ё].НужноВзять = Мин(Стек[ё].Имеется, Цел(Сумма / Стек[ё].Коэффициент));
		Сумма = Сумма - Стек[ё].НужноВзять * Стек[ё].Коэффициент;
		Если Сумма = 0 тогда
			Возврат Истина;
		КонецЕсли;
	КонецЦикла;
	Пока ё <= Всё И Стек[ё].НужноВзять = 0 Цикл
		ё = ё + 1;
	КонецЦикла;
	если ё <= Всё Тогда
		Сумма = Сумма + Стек[ё].Коэффициент;
		Стек[ё].НужноВзять = Стек[ё].НужноВзять -1;
		Возврат ОдинВариантРекурсия(Стек, Всё, Сумма , ё);
	КонецЕсли;
	Возврат Ложь;
КонецФункции

Процедура ОсновныеДействияФормыРекурсия(Кнопка)
    Стек = Метраж.Выгрузить();
    Стек.ЗаполнитьЗначения(0, "НужноВзять");
    Стек.Сортировать("Коэффициент Возр");
    ОдинВариант(Стек, Стек.Количество()-1, Требуется);
    Ответ = Стек.Скопировать( , "НомерСтроки, НужноВзять"); 
    Ответ.Сортировать("НомерСтроки"); 
    Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
КонецПроцедуры

Процедура ОсновныеДействияФормыРекурсияПродолжить(Кнопка)
    Стек = Метраж.Выгрузить();
    Стек.Сортировать("Коэффициент Возр");
    //ОдинВариант(Стек, Стек.Количество()-1);
    ОдинВариантРекурсия(Стек, Стек.Количество()-1,0,0);
    Ответ = Стек.Скопировать( , "НомерСтроки, НужноВзять"); 
    Ответ.Сортировать("НомерСтроки"); 
    Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять"); 
КонецПроцедуры
Показать
63. ildarovich 7846 13.07.16 10:44 Сейчас в теме
(62) Ovrfox, Спасибо за код. Он поучительный. Соображений по его поводу у меня довольно много. Поэтому разобью их на несколько комментариев.
Внешне код (я сейчас про цикл) мне нравится. Своей эффективностью. Отсутствием избыточности. Если бы играл в команде "против рекурсии", постарался написать бы именно такой. Очень понравились манипуляции с суммой "околоноля".
Но я здесь играю за рекурсию. И приведенный код как нельзя лучше подчеркивает ее необходимость.
Именно рекурсивная форма записи (и только она, как предполагаю) позволит обосновать (доказать) корректность приведенного не рекурсивного кода. А именно то, что он 1) не зациклится, 2) не пропустит никакого варианта. А также оценить количество выполняемых операций. А доказательство необходимо, одних тестовых просчетов просчетов обычно не достаточно. Тем более в комбинаторных задачах, где тестов не нагенерируешься.
Или скажите, как вы для себя надежно обосновывали то, что беготня вверх-вниз курсора по стеку дает нужный результат.
Если взять две формы одной и той же программы: рекурсивную и не рекурсивную, то рекурсивная будет обладать большей степенью абстракции, позволяющей легче обосновать ее правильность. Как будто написана на языке более высокого уровня. Взамен она более затратна (для большинства языков).
Поэтому правильный путь, как я считаю - это изначально записывать алгоритм в рекурсивной (более компактной и самодоказываемой) форме. А затем, при необходимости, раскрывать рекурсию, чтобы добиться большей скорости работы.
64. ildarovich 7846 13.07.16 10:45 Сейчас в теме
(62) Ovrfox, +(63)
Ну и теперь о конкретике:

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

Думаю, поэтому вы и задали себе такой вопрос: а зачем такая (хвостовая) рекурсия (как у вас) вообще нужна.
У вас не проверяется ситуация исчерпанности метража в оставшейся зоне поиска, поэтому для задачи подбора 1023 из кусков 1-2-4-8-16-32-64-128-256-512 после варианта 1-1-1-1-1-1-1-1-1-1 программа будет перебирать все 1022 возможностей, чтобы убедиться, что вариантов больше нет. Тогда как "моя" рекурсия, да и ваша предыдущая редакция на это время тратить не будет.

Это я к тому, что ваш вариант "упрощения" привел к утрате кое-каких полезных свойств. По сути, это раскрытая рекурсия в исправленном варианте из статьи, если перебирать от большего к меньшему. Он был в моих комментариях. Вы же сами его критиковали за избыточный перебор.

Кстати, цикломатическая сложность у нас одинакова, а число строк у меня меньше. Это объективные показатели сложности. Ну, а субъективная понимаемость в моем коде, очевидно, похуже.

Поэтому я думаю отказаться от выхода-захода при нахождении варианта. Видимо, вернусь к варианту фиксации решения без прерывания поиска. Ведь это бывает нужно только при интерактивном выборе, которым все варианты использования алгоритма не ограничиваются. Это улучшит понимаемость. Также хочу делать отсечку при наборе числа кусков больше текущего рекорда при движении вниз, чтобы поиск велся строго в порядке улучшения достижений, а то сейчас число кусков сильно прыгает. Ну и из спортивного интереса сейчас смотрю вариант вообще без цикла (с его заменой на еще одну рекурсию). Может, еще короче получится. Это ведь "минимализмы".
65. Ovrfox 14 14.07.16 10:10 Сейчас в теме
Вы ошиблись, оба мои варианта тождественны и , хотя отличаются от Вашего, но созданы на основе одного алгоритма.
Более того, если на вход обоих функций подать неправильно упорядоченную таблицу элементов - то жадный алгоритм подбора вариантов может отбросить варианты, которые могли быть правильными. (т.е. не все варинаты будут перебраны). И , кстати, ваш алгоритм поведет себя точно также.
Что касается защиты решения. Во первых, я утверждаю, что решение одно в трех лицах. Во вторых, при анализе алгоритма, что в рекурсии, что в цикле будет анализироваться один шаг. Т.е. доказательство сходимости алгоритма одно и тоже. Просто представлены две реализации. Шаг как тело цикла и шаг как тело рекурсивной функции.
Что касается оптимальности кода. Накладные расходы на рекурсию достаточно велики. В моем и вашем случае - это составит один вызов рекурсивной функции на одну строку таблицы данных. Каждый вызов - это дубль внутренних переменных и передаваемых по значению переменных. Поэтому с точки зрения быстродействия я считаю цикл более оптимальным.
Что касается красоты кода, то я считаю красивым не более короткий код, а тот код, который приятно читать, т.е. понятный код, а уже во вторых - более короткий (но именно потому, что тратиться меньше времени на его восприятие). Именно поэтому я не считаю рекурсию красивой.
66. ildarovich 7846 14.07.16 11:01 Сейчас в теме
(65) Ovrfox, давайте разберемся по порядку, начиная с конкретики, с кода:
оба мои варианта тождественны
- какие это варианты? Если вы про два варианта в (62) - согласен.
Я имел ввиду разницу в поведении вашего варианта из (54) и из (62). И имел ввиду как ведет себя поиск в задаче: 1-2-4-8-16-32-64-128-256-512 (все куски по одному), если требуется подобрать кусок 1023.
Первый вариант 1-1-1-..-1 найдется жадным алгоритмом очень быстро. Но, чтобы убедиться в том, что других вариантов нет, ваш алгоритм из (62) будет перебирать все (сколько?) вариантов, а мой нет.
Вот трассировка (начало, всего 1024 строки) вариантов, проверяемых в вашем цикле из (62):
1111111111
0111111111
1011111111
0011111111
1101111111
0101111111
1001111111
0001111111
1110111111
0110111111
1010111111
0010111111
1100111111
0100111111
1000111111
0000111111
1111011111
0111011111
1011011111
0011011111
1101011111
0101011111
1001011111
0001011111
1110011111
0110011111
1010011111
0010011111
1100011111
0100011111
1000011111
0000011111
1111101111
...
Показать
По какой системе идет перебор видно только из трассировки! - А много ли людей смогут увидеть это, глядя только на код? На мой взгляд, код в (62) только выглядит просто, но на самом деле вообще непонятен. Это классная головоломка. Можно даже эксперимент провести.

И давайте вот сюда
если на вход обоих функций подать неправильно упорядоченную таблицу элементов
уже не лезть. Проблем с пониманием хватает и с правильно упорядоченными таблицами.
Прикрепленные файлы:
РюкзакСравнение.erf
67. Ovrfox 14 18.07.16 10:23 Сейчас в теме
Действительно, когда я разбирал Ваш алгоритм, я ошибся , откат происходит неоптимально.
Но, к сожалению, главный посыл до Вас не дошел. Я ведь просто хотел показать, что цикл более читабельный и более эффективный.
Я пытался Ваш алгоритм преобразовать в цикл, стараясь внести как можно меньше изменений. К сожалению. у меня не получилось.
Как я теперь понял потому, что он просто не правильный
Просто попытайтесь побобрать 3 из массива 1,2,3 . Второй вариант алгоритм не находит ( в отличии от того, который я предложил на основе Вашего)
Вы уж извините меня, что я так небрежно подошел к анализу предложенных алгоритмов. Но я просто хотел указать на то, ИМХО, что рекурсия не самый оптимальный способ для расчетов. Особенно связанных с большими массивами данных.
68. bulpi 215 22.09.16 14:39 Сейчас в теме
Какая-то странная функция в запросе п.28 :
МАКСИМУМ(ВЫБОР Слева.Цена КОГДА Дано.Цена ТОГДА Слева.Дата КОНЕЦ)

Похоже, ошибка, или я что-то не знаю про синтаксис функции ВЫБОР.
69. ildarovich 7846 22.09.16 15:02 Сейчас в теме
(68) bulpi, ошибки нет, вот ссылка: Нестандартный синтаксис оператора "ВЫБОР" в запросе . Удобный прием, я часто его использую.
70. kng67 11.11.16 09:38 Сейчас в теме
Автору спасибо за 28. Движения периодического регистра сведений без повторов. Попробую применить на практике
72. tormozit 7133 18.11.16 16:53 Сейчас в теме
32. Определение длины строки в запросе методом половинного деления
На СУБД MSSQL попытка выполнить запрос выдает ошибку (слишком сложный запрос)
Microsoft SQL Server Native Client 11.0: Internal error: An expression services limit has been reached. Please look for potentially complex expressions in your query, and try to simplify them. HRESULT=80040E14, SQLSrvr: SQLSTATE=42000, state=2, Severity=11, native=8632, line=1
Надо подумать о решении с меньшей вложенностью запросов.
75. KlesAlex 3 09.01.17 11:01 Сейчас в теме
(72) я переделал вложенные запросы в пакеты. Изящность конечно утеряно но работает:

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 511, 1) = "" ТОГДА Дано.Х - 512 
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ1 ИЗ Дано КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 255, 1) = "" ТОГДА Дано.Х - 256
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ2 ИЗ ВЗ1 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 127, 1) = "" ТОГДА Дано.Х - 128
ИНАЧЕ Дано.Х КОНЕЦ КАК Х 
ПОМЕСТИТЬ ВЗ3 ИЗ ВЗ2 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 63, 1) = "" ТОГДА Дано.Х - 64
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ4 ИЗ ВЗ3 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 31, 1) = "" ТОГДА Дано.Х - 32
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ5 ИЗ ВЗ4 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 15, 1) = "" ТОГДА Дано.Х - 16
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ6 ИЗ ВЗ5 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 7, 1) = "" ТОГДА Дано.Х - 8
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ7 ИЗ ВЗ6 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 3, 1) = ""	ТОГДА Дано.Х - 4
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ8 ИЗ ВЗ7 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 1, 1) = "" ТОГДА Дано.Х - 2
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ9 ИЗ ВЗ8 КАК Дано;

ВЫБРАТЬ Дано.Стр КАК Стр,
ВЫБОР КОГДА ПОДСТРОКА(Дано.Стр, Дано.Х - 0, 1) = "" ТОГДА Дано.Х - 1
ИНАЧЕ Дано.Х КОНЕЦ КАК Х
ПОМЕСТИТЬ ВЗ10 ИЗ ВЗ9 КАК Дано;

ВЫБРАТЬ Стр,Х
ИЗ ВЗ10 КАК ВЗ10
Показать
76. KlesAlex 3 09.01.17 11:04 Сейчас в теме
В методе минимализма 32 есть ошибка.
Длинна строки : "АБВГ Д" определяется как 4. "АБВГДЕЖЗ И" как 8 и так далее.
Проблема в том, что ПОДСТРОКА("АБВГ Д", 5, 1) = "", хотя на самом деле там " ".
77. ildarovich 7846 14.10.17 00:06 Сейчас в теме
(76) К сожалению, пропустил ваше замечание. Теперь, когда на эту ошибку мне еще раз указали в исходной статье, нашел и исправил. Использую проверку
ПОДСТРОКА("АБВГ Д", 5, 1) + "!" <> "!"
Либо
ПОДСТРОКА("АБВГ Д", 5, 512) <> ""
Разница есть, поэтому приведены оба варианта.
78. пользователь 14.10.17 02:18
Сообщение было скрыто модератором.
...
79. Gesperid 2 08.02.18 11:52 Сейчас в теме
В минимализме №25 в первой временной таблице не хватает условий во внутреннем соедининии, а именно
"Дано.Гостиница = ДаноСлева.Гостиница И
Дано.ФизическоеЛицо = ДаноСлева.ФизическоеЛицо"
80. ildarovich 7846 22.02.18 11:00 Сейчас в теме
(79) Поправил, спасибо за внимательность.
84. headMade 144 13.10.20 00:39 Сейчас в теме
(80) только
"Дано.Гостиница = Дано.Гостиница И
Дано.ФизическоеЛицо = Дано.ФизическоеЛицо"

ДаноСлева - не определена таблица
85. headMade 144 13.10.20 01:11 Сейчас в теме
(84)
sorry
И Дано.Гостиница = Слева.Гостиница
И Дано.ФизическоеЛицо = Слева.ФизическоеЛицо
81. ildarovich 7846 22.02.18 11:02 Сейчас в теме
Опубликована очередная серия "минимализмов" - Минимализмы - 3 [https://infostart.ru/public/788007/].
82. bulpi 215 28.01.20 18:07 Сейчас в теме
Увы, в решении задачи 29 есть ошибка (в последнем запросе, который самый простой и считает дни наличия, а не секунды).
РАЗНОСТЬДАТ(Было.Период, МИНИМУМ(Стало.Период), ДЕНЬ)

Если товар просто лежал на складе с 1 по 31 число, то получится 30 дней наличия, а надо 31. Там где секунды, неучет последней секунды - это мелочь, а вот последний день нельзя не учитывать. И я не вижу простого способа исправить эту ошибку, т.к. последний день нужно прибавлять только в случае, если остаток последнего дня >0 .
86. Alxby 1134 08.07.22 22:46 Сейчас в теме
27. Округление в большую сторону

Для округления числа Ч в бОльшую сторону можно применять выражение:

М - Цел(М - Ч)
где М = 999999999 или больше, при необходимости.

Как-то не хочется подбирать подходящее М :)
Цел(Ч)+1-Цел(1-(Ч-Цел(Ч)))
Оставьте свое сообщение