@Nikolol

Необходим алгоритм разбиения натурального числа 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
  • Вопрос задан
  • 223 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы