Необходим алгоритм разбиения натурального числа n на m частей( нули тоже входят) или хотя бы набросок? Есть алгоритм, но он не понятен и не доходчив:
Генерация композиций натурального числа n по заданному рангу m означает: всевозможными способами разбить n на m целых неотрицательных слагаемых.
Другими словами, разбить всевозможными способами n записанных подряд единиц на заданное число m частей (допускаются и пустые части).
Если в качестве символов-разделителей выбрать нули, то m частей порождаются m-1 разделителями, т.е. m-1 нулями. Таким образом, задача сводится к перебору битовых строк длины q=n+m-1, отсеивая те, в которых число нулей отлично от m-1.
В качестве вспомогательного алгоритма нам понадобится алгоритм порождения всех двоичных последовательностей длины q.
Используется битовый массив b[q], b[q-1], ..., b[0], который вначале обнуляется.
Для записи порожденной последовательности служат b[q-1], ..., b[0], b[q] – только для технических целей: порождающий цикл завершается, как только b[q] станет равно 1.
while b[q]=0 do
begin
1. вывод последовательности b[q-1], ..., b[0];
2. найти первый справа налево нулевой элемент b[i] и заменить его на единицу, а все элементы правее него стереть до нуля.
end

21 Авг 2019 в 06:04
160 +1
0
Ответы
1

Вариант решения задачи:

Обнуляем массив b[q].Устанавливаем значение m-1 первых бит равными 1.Для каждой битовой последовательности:
Выводим последовательность b[q-1], ..., b[0].Находим первый справа налево нулевой элемент b[i] и заменяем его на единицу, а все элементы правее него стираем до нуля.Продолжаем шаг 3 до тех пор, пока b[q] не станет равным 1.

Таким образом, перед нами алгоритм, который позволяет разбить натуральное число n на m частей с использованием двоичных последовательностей длины q.

20 Апр в 13:24
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Название заказа не должно быть пустым
Введите email
Бесплатные доработки
Гарантированные бесплатные доработки
Быстрое выполнение
Быстрое выполнение от 2 часов
Проверка работы
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Название заказа не должно быть пустым
Введите email
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 94 835 авторам
Первые отклики появятся уже в течение 10 минут
Прямой эфир