Задача про миллион

30.12.14

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

Не упусти свой шанс стать миллионером!
(сколькими способами можно разложить* на 6 целых множителей миллион?).com
* разложения, отличающиеся порядком множителей, считаются различными

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Процедура генерации сочетаний
.epf 7,94Kb
1
1 Скачать (1 SM) Купить за 1 850 руб.

Данное объявление однажды появилось на станциях минского метро. С его помощью разработчик программного обеспечения искал кандидатов на открывшуюся вакансию. Попробуем решить предложенную задачу. 
Разложение числа миллион на простые множители записывается в виде: 1 000 000 =(2^6)*(5^6)
Таким образом, для ответа на поставленный вопрос нам надо найти количество разложений числа 2^6 на шесть множителей, количество разложений числа 5^6 на шесть множителей (заметим, что  количества  для обоих случаев будут одинаковые) . Перемножить полученные числа и ... еще раз перечитать условие задачи, обратив внимание на выражение "... ЦЕЛЫХ множителей". И так, найдем количество разложений числа 2^6. Эта задача аналогична задаче определения числа размещений 6 одинаковых предметов в шести коробках. Одно из решений следующее. Возьмем 6+5=11 одинаковых предметов. Выберем из них 5. Предметы, которые находятся левее первого выбранного, поместим в первый ящик, предметы которые находятся между первым и вторым - во второй, между вторым и третьим - в третий и т.д. Предметы, которые находятся правее пятого выбранного будут относится к шестому ящику.  Количество таких размещений определяется формулой:

 

 

Таким образом, искомое количество разложений на натуральные (положительные) множители числа 1 000 000 равно 462². Теперь учтем условие, что возможны отрицательные коэффициенты разложения. Таких коэффициентов может быть либо  2, либо 4, либо 6. Количество подобных разложений равно  числу сочетаний из 6 по 2, по 4 и по 6, что равно 15,15 и 1, соответственно. То есть, на каждое найденное разложение будет приходится еще 31 разложение с отрицательными сомножителями. А общее число вариантов составит 462²*32.

Постараемся получить аналогичный результат средствами 1С. А именно, получим размещения 6 двоек по 6 ячейкам. Воспользуемся объектом типа Таблица значений, который содержит колонки с именами Кол0,Кол1,Кол2...Кол5. Для одной двойки и одной ячейки количество размещений равно единице. Это будет таблица с одной колонкой и одной строкой. Следующий шаг - добавить новую ячейку. Мы можем разместить её перед существующими ячейками или расположить за последней. В новую ячейку запишем значение 1.

 


Теперь добавим двойку в получившийся набор ячеек. Добавление (умножение содержимого ячейки) надо провести для каждой клетки в наборе. При этом исходная строка "расщепится" на N строк (где N - это количество ячеек  в строке).


 

Этот набор содержит повторяющиеся размещения, которые мы  уберем с помощью метода Свернуть() объекта ТаблицаЗначений. Повторив изложенную процедуру необходимое число раз, мы получим  искомую последовательность. Ниже приводится текст соответствующей процедуры.

Функция ПолучитьСочетания(вхТЗ) экспорт
тЧисло=новый ОписаниеТипов("Число",,,новый КвалификаторыЧисла(10,0));
буфер=вхТЗ.СкопироватьКолонки();
вхРазмер=вхТЗ.Колонки.Количество()-1;
выхРазмер=вхРазмер+1;
буфер.Колонки.Добавить("Кол"+строка(выхРазмер),тЧисло);
Измерение="Кол0";
для н=1 по выхРазмер цикл
        Измерение=Измерение+",Кол"+строка(н);
конеццикла;
для каждого стр из вхТЗ цикл
для н=0 по выхРазмер цикл
нСтр=буфер.Добавить();
нСтр[н]=1;
для кол=0 по вхРазмер цикл
если кол<н тогда
нСтр[кол]=стр[кол];
иначе
нСтр[кол+1]=стр[кол];
конецесли;
конеццикла;
конеццикла;
конеццикла;
буфер.Свернуть(Измерение);
выхТЗ=буфер.СкопироватьКолонки();
для каждого запись из буфер цикл
для кол=0 по выхРазмер цикл
нСтр=выхТЗ.Добавить();
ЗаполнитьЗначенияСвойств(нСтр,запись);
нСтр[кол]=нСтр[кол]*2;
конеццикла; 
конеццикла;
выхТЗ.Свернуть(Измерение);
возврат выхТЗ;
КонецФункции

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

 

Комбинаторика размещения динамическое программирование

См. также

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

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

1 стартмани

30.01.2024    2849    stopa85    12    

38

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

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

19.10.2023    7001    user1959478    50    

36

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

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

2 стартмани

29.09.2023    2789    maksa2005    8    

26

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

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

1 стартмани

09.06.2023    10579    7    SpaceOfMyHead    18    

61

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

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

03.04.2023    4058    RustIG    9    

25

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

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

23.11.2022    3191    gzharkoj    14    

25

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

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

1 стартмани

21.03.2022    8985    7    kalyaka    11    

44
Оставьте свое сообщение