Необходим алгоритм разбиения натурального числа 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
Необходим алгоритм разбиения натурального числа 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
Генерация композиций натурального числа 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
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Вариант решения задачи:
Обнуляем массив b[q].Устанавливаем значение m-1 первых бит равными 1.Для каждой битовой последовательности:Выводим последовательность b[q-1], ..., b[0].Находим первый справа налево нулевой элемент b[i] и заменяем его на единицу, а все элементы правее него стираем до нуля.Продолжаем шаг 3 до тех пор, пока b[q] не станет равным 1.
Таким образом, перед нами алгоритм, который позволяет разбить натуральное число n на m частей с использованием двоичных последовательностей длины q.