gifts2017

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

Опубликовал Дмитрий Ткачев (Ткачев) в раздел Программирование - Практика программирования

Навеяно темой с Мисты:
Имеем ряд чисел от одного до девяти, надо расставить знаки плюсы и минусы, чтобы получилось в сумме 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";//т.к. последнее число не вошло в цикл просто добавим его.

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

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

КонецЦикла;

 

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

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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

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