Как перебрать все варианты чего-либо

25.10.11

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

Навеяно темой с Мисты:
Имеем ряд чисел от одного до девяти, надо расставить знаки плюсы и минусы, чтобы получилось в сумме 20
1(+/-)2(+/-)3(+/-)4(+/-)5(+/-)6(+/-)7(+/-)8(+/-)9 = 20 (20 не получиться, это просто пример!!!)

Вот как можно автоматизировать пример, что бы получить все варианты расчета?

Я раньше занимался программированием на Ассемблере, так что для меня двоичная и шестнадцатиричная система счисления ближе десятичной.

1 = 1000, 2 = 0100, 3 = 1100, 4 = 0010 и т.д. из этого для примера возьмем 0 = Минус, 1 = Плюс

В выше указаном примере нам надо перебрать 8 различных подстановок +- (8 = 11111111B = 255D)

КоличествоВариантов = 8;
КоличествоВариантовРасчета = POW(2, КоличествоВариантов) - 1; //Расчитываем количество вариантов
Для ВариантРасчета = 0 По КоличествоВариантовРасчета Цикл       //Перебираем варианты
   
ЗначениеВариантаРасчета = ВариантРасчета;                              //Берем текущий вариант

   
Пример = "";                                                                                      //Текст примера
   
Для ПереборВарианта = 1 По КоличествоВариантов Цикл            //Перебираем расчет варианта
       
Вариант = ЗначениеВариантаРасчета%2;                                 // Получаем значение варианта

        //Здесь выполняем действие со значением варианта, в нашем примере знак "+" или "-"

       
Знак = ?(Вариант = 1, "+", "-");

       
//Делаем текст примера

       
Пример = Пример + ПереборВарианта  + Знак;

       
//***


       
ЗначениеВариантаРасчета = Цел(ЗначениеВариантаРасчета / 2); //Сдвигаем на следующее значение варианта
   
КонецЦикла;

   
Пример = Пример + "9";//т.к. последнее число не вошло в цикл просто добавим его.

   
РасчетПримера = Вычислить(Пример);//Вычислим выражение

   
Сообщить(Пример + " = " + РасчетПримера);

КонецЦикла;

 

По этому принципу расчета сделана моя обработка "Рюкзак".

См. также

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

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

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

1 стартмани

30.01.2024    1757    stopa85    12    

33

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

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

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

19.10.2023    4432    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7473    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7859    7    kalyaka    11    

44

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

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

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

16.12.2021    4451    fishca    13    

36

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

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

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

12.10.2021    8847    John_d    73    

46

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

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

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

31.08.2021    7814    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. cool.vlad4 2 25.10.11 11:10 Сейчас в теме
Т.е. по сути это просто перебор всех возможных подстановок "+" и "-"? и неплохо бы, если есть упоминание на мисту, то хоть ссылку дать на исходную тему...
7. Ткачев 74 25.10.11 12:02 Сейчас в теме
(1)"+" и "-" Это для примера, допустим есть таблица товаров и из нее нам надо выбрать набор товаров который не ниже суммы в 100 руб. и не выше суммы 200 руб.
1) Отсеиваем товары у которых цена > 200 руб.
2) Создаем Временную таблицу куда по условиям сложим товары сумма которых не превышает 200 руб.
3) После 2-го цикла проверим на то что сумма у нас получилась > 100 руб. если "Истина" тогда добавим набор, если "Ложь" тогда очистим временную таблицу.
Вариантов использования много.
8. cool.vlad4 2 25.10.11 12:08 Сейчас в теме
(7) по моему неудачный пример
из нее нам надо выбрать набор товаров который не ниже суммы в 100 руб. и не выше суммы 200 руб.
- раз создается временная таблица, то и решается запросом
Да, я не спорю, полный перебор в любом случае где-нибудь используется.
9. Ткачев 74 25.10.11 12:14 Сейчас в теме
(8)Вот запросом было бы интересно посмотреть как это сделать, у меня не получилось, как я не пытался.
10. cool.vlad4 2 25.10.11 12:18 Сейчас в теме
(9) В смысле - набор товаров, а не товары, определенной суммой? Да, хрен, его знает, может можно, может нельзя, честно не знаю - не пытался. Да, вы поймите меня правильно ничего против вашей публикации не имею.
2. Ткачев 74 25.10.11 11:14 Сейчас в теме
3. Alraune 1502 25.10.11 11:20 Сейчас в теме
(2) Можно. Могли бы заодно и на свою обработку ссылку дать в тексте, раз ее упомянули.
4. Ткачев 74 25.10.11 11:33 Сейчас в теме
(3)А моем профиле разве не видно ссылок ?
http://infostart.ru/public/88022/
5. Alraune 1502 25.10.11 11:43 Сейчас в теме
(4) Видно. Но Вы переоцениваете любопытство читателей - в профиль искать полезет не каждый, а ткнуть в имеющуюся здесь же ссылку проще. Впрочем, дело Ваше
6. Ткачев 74 25.10.11 11:47 Сейчас в теме
(5)Да нее, я не спорю, зашугали просто мальчика банами за ссылки, пусть даже на текущий сайт.
11. vkr 26.10.11 09:37 Сейчас в теме
(0) Вспомнить молодость... Написать подобную фигню на 10 разных языках - от Ассемблера до Перла... :)
12. evn-zorin 32 26.10.11 10:10 Сейчас в теме
Прям задача с чемпионата по программированию, автору спасибо за публикацию интересных алгоритмов!
13. tdr1225 37 31.10.11 11:38 Сейчас в теме
(0) а как будешь поступать, если надо выбирать не +/-, а, например, +/-/* или еще больше арифметических действий?
14. Ткачев 74 31.10.11 11:51 Сейчас в теме
(13)см.(7), запросом у меня не получается так сделать, может кто поможет ?
15. tdr1225 37 31.10.11 13:05 Сейчас в теме
(14) я не о том, ты не понял
ты решал задачу: составить все слова длиной 8 символов из букв А и Б (0/1)
а я предлагаю такую задачу: составить все слова длиной 8 символов из букв А, Б, В, Г.
17. Ткачев 74 31.10.11 14:28 Сейчас в теме
(15)(16)Если рассчитывать как в (0), получилось очень заковыристо, я сделал по другому.

ВариантыБукв = "АБВГ";
КоличествоСимволов = СтрДлина(ВариантыБукв);
КоличествоВариантов = 8;
Массив = Новый Массив;
Для Аа = 1 по КоличествоВариантов Цикл
Массив.Добавить(1);
КонецЦикла;
Пока 1 Цикл
СтрокаТекста = "";
Для Аб = 1 по КоличествоВариантов Цикл
СтрокаТекста = СтрокаТекста + Сред(ВариантыБукв, Массив[Аб - 1], 1);
КонецЦикла;
Сообщить(СтрокаТекста);
Фл = 0;
Пока Массив[Фл] + 1 > КоличествоСимволов Цикл
Массив[Фл] = 1;
Фл = Фл + 1;
Если Фл = КоличествоВариантов Тогда
Возврат;
КонецЕсли;
КонецЦикла;
Массив[Фл] = Массив[Фл] + 1;
КонецЦикла;
16. tdr1225 37 31.10.11 13:07 Сейчас в теме
+
или еще интересней, если и длина слова и количество букв - переменные (параметры)
19. tdr1225 37 31.10.11 15:38 Сейчас в теме
(18)
не понял, а при чем здесь это?
(17)
на самом деле, это задача из комбинаторики о перестановках.
надо юзать рекурсию
20. Ткачев 74 31.10.11 15:45 Сейчас в теме
21. Арчибальд 2706 31.10.11 15:50 Сейчас в теме
Язык дан человеку, чтобы скрывать свои мысли ©

По тексту: Почему 2**8-1, а не 2**8?
Далее: чем двоичная система отличается (кроме основания) от троичной, четверичной и т.п.?
(19) Перестановки-то здесь при чем? Здесь задача: перебрать все слова длины L в алфавите из N букв. Слов таких, конечно, N**L.
23. tdr1225 37 31.10.11 16:04 Сейчас в теме
(21)
верно, я ошибся, перестановки ни при чем
24. Ткачев 74 31.10.11 18:26 Сейчас в теме
(21)Потому что 0 это тоже число и нам надо получить на выходе все включенные разряды. 256 = 000000001, 255 = 11111111
Я наверно в школе плохо учился, но я знаю только 4 системы счисления, 2, 8, 10, 16.
25. Арчибальд 2706 01.11.11 07:43 Сейчас в теме
22. see1c.ru 50 31.10.11 15:51 Сейчас в теме
(19) используя буквенный ряд А, Б, В, Г. Находим минимальное и максимальное числовое значение комбинаций.
Разница между максимальным и минимальным значением будет равна их количеству.
Циклом прогоняем от минимального до максимального и получаем все возможные комбинации этих букв. в виде 4-х буквенной строки.
26. Гость 20.12.11 12:49
очень интересная и полезная обработка,спасибо,очень кстати
Оставьте свое сообщение