Разложение числа
 

Хочу узнать из скольких 3, 2 и 1 состоит число 23. Как это делается? Наверное даже существует какая-нибудь теорема или что-то типа этого?

Поясни что имеется ввиду под разложением? Например деление 23 нацело на 3 дает 7 и в остатке 2. Ты это имеешь ввиду - 7 троек и 1 двойка, или там, например, 23 единицы?

Да.

Ну так алгоритм то понятен? На паскале, например, это будут операции div и mod: 23 div 3 будет 7, 23 mod 3 будет 2.

Нет. Точнее - только для конкретного случая.

Язык программирования то какой?

Для разложения на два числа можно использовать расширенный алгоритм Эвклида.
Для большего числа сомножителей... см. Д. Кнут "Исскуство программирования" т. 2.

C++

Доступ к Кнуту смогу получить только через неделю. :-(
Если описание решения проблемы не занимает у него много места, то может быть процитируешь?

Что-то не совсем понятно как данный алгоритм подходит для решения поставленной задачи. IMHO, не то.

Можно это делать алгоритмом разложения на простые множители, однако если я понял правильно, тут ряд множителей дан заранее. Тогда вот за пару минут набросал на С:

#include <stdio.h>

void main() {
int dividers[] = {1,2,3};
int currentDivider, arrayPosition, divisionResult, residue;

int X = 23, tempX;

tempX = X;

printf("\n%d is:\n", X);

for (arrayPosition = 2; arrayPosition >= 0 ; arrayPosition--) {
currentDivider = dividers[arrayPosition];
if (tempX < currentDivider)
continue;
else if (tempX == currentDivider) {
printf("1 occurence of divider %d\n", currentDivider);
break;
}
else {
divisionResult = (int) (X/currentDivider);
residue = X % currentDivider;
printf("%d occurences of divider %d\n", divisionResult, currentDivider);
tempX = residue;
}
}
}

Вывод:

23 is:
7 occurences of divider 3
1 occurence of divider 2

Спасибо, но это не то. Сам подумай (условие почитай).

Программировать влом, лучше подсчитать математически. :) Попробую обрисовать свой ход мыслей.

Выпишем возможные варианты для первых чисел: (по три строчки для каждого числа)

-
-
1

-
2
1+1

3
2+1
1+1+1

3+1
2+2 2+1+1
1+1+1+1

3+2 3+1+1
2+2+1 2+1+1+1
1+1+1+1+1

3+3 3+2+1 3+1+1+1
2+2+2 2+2+1+1 2+1+1+1+1
1+1+1+1+1+1

3+3+1 3+2+2 3+2+1+1 3+1+1+1+1
2+2+2+1 2+2+1+1+1 2+1+1+1+1+1
1+1+1+1+1+1+1

3+3+2 3+3+1+1 3+2+2+1 3+2+1+1+1 3+1+1+1+1+1
2+2+2+2 2+2+2+1+1 2+2+1+1+1+1 2+1+1+1+1+1
1+1+1+1+1+1+1+1

3+3+3 3+3+2+1 3+3+1+1+1 3+2+2+2 3+2+2+1+1 3+2+1+1+1+1 3+1+1+1+1+1
2+2+2+2+1 2+2+2+1+1+1 2+2+1+1+1+1+1 2+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1

Первая строчка - в слагаемых есть хоть одна тройка,
Вторая строчка - в слагаемых есть хоть одна двойка, но нет тройки
Третья - единичное представление.

Это все разложение в сумму, со слагаемыми не выше трех. Число вариантов для каждой строки:
s(1,1)=1 s(1,2)=0 s(1,3)=0
s(2,1)=1 s(2,2)=1 s(2,3)=0
s(3,1)=1 s(3,2)=1 s(3,3)=1
s(4,1)=1 s(4,2)=2 s(4,3)=1
s(5,1)=1 s(5,2)=2 s(5,3)=2
s(6,1)=1 s(6,2)=3 s(6,3)=3
s(7,1)=1 s(7,2)=3 s(7,3)=4
s(8,1)=1 s(8,2)=4 s(8,3)=5
s(9,1)=1 s(9,2)=4 s(9,3)=7

Всего способов разложить число n будет равно S(n)=s(n,1)+s(n,2)+s(n,3);

s(n,1)=1 (очевидно)

s(n,2)=s(n-2,2)+s(n-2,1)=s(n-2,2)+1;
=> s(n,2)=n/2, округленное снизу

s(n,3)=s(n-3,3)+s(n-3,2)+s(n-3,1)=s(n-3,3)+(n-3)/2 (округл.)+1= ... 3*k^2+ поправка
n=6k+остаток, поправка зависит от остатка:
s(6k,3)=3k^2;
s(6k+1,3)=3k^2+k;
s(6k+2,3)=3k^2+2k;
s(6k+3,3)=3k^2+3k+1;
s(6k+4,3)=3k^2+4k+1;
s(6k+5,3)=3k^2+5k+2;

Или это выразить через n: s(n,3)=(n^2)/12, с округлением вниз до целого.

Пример: s(9.3)=s(6*1+3,3)=3*1^2+3*1+1=7 (совпадает!) (или =81/12=7 + 7/12 -> 7 )

Для заданного n=23:
S(23)=s(26,3)=3*4^2+2*k=56;

doro, предложенное решение согласуется с информацией, указанной в постах 1 и 3. Поскольку по твоим словам это не так, то более формализованное условие задачи в студию :biggrin:

А еще - для какой задачи потребовалось такое разложение? Может существует более простое решение?

Не заметил пост Trotil - это то, что необходимо, или все же нужно что-то другое?

Как я понял это количество вариантов?

Задача о планировании работ.
В месяце необходимо выполнить определённое количество работ. Каждый вид работ имеет свой весовой коэффициент (первая последовательность).
Одни виды работ выполняются ежедневно. Другие - не ежедневно (через день, раз в месяц, и т.п.).
В одном виде работ может быть задействовано много людей, в другом - только один человек.
Не все исполнители имеют право выполнять все работы (Вася - может думать, но не думать не может, Петя - может и думать и не думать).
Необходимо раскидать имеющееся количество людей по видам работ и получить сумму весовых. При этом получаем сумму весовых коэффициентов для каждого человека, которую он получает при выполнении того или иного вида работ.
После этого необходимо привести суммы коэффициентов каждого человека максимально близко к какому-то среднему (арифметическому, медиане, ...), используя только те значения весовых коэффициентов, которые были использованы при формировании каждой конкретной суммы весовых коэффициентов для каждого конкретного человека.
При этом, если человек снимается с какого-то вида работ (для выравнивания сумм весовых коэффициентов - вторая последовательность), то, значит, кто-то должен быть поставлен на его место. Т.е. количество работ в месяц и людей задействованных в проведении каждого вида работ в день - константа.

Спасибо за поддержку :)

Это пояснение о весовых коэффициентах?

Алгоритм разложения здесь не подойдет. Он предполагает что множители простые, а в данном случае вполне вероятен ряд коэффициентов 1,2,3,4,5,6.

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

Неясны также факторы, которые следует учитывать в отношении работ .

В общем, ИМХО, когда данные будут разъяснены, а задача построена, базируясь исключительно на алгебре предоставленных данных, то можно будет говорить о более конкретном алгоритме.

Что-то не понял вопроса. Конкретно это - нет.
Весовые коэффициенты назначаются субъективно. Кто как посчитает нужным при первом запуске программы.


Этот момент вообще не надо учитывать. Его учитывает для себя тот, кто будет работать с программой. Он решает кто и где.


Если можно - что конкретно?

Итак, давай попроще :) Пусть имеем на понедельник три планируемые работы с коэффициентами трудоемкости 20, 30 и 35. Есть пять работников с весовыми коэффициентами 10, 12, 15, 9 и 8. Необходимо максимально точно подобрать суммы весовых коеффициентов работников к требуемым задачам? Так?

У работников вообще не может быть весовых коэффициентов.
Применительно к твоему условию задача будет звучать так: необходимо так расставить по работам рабочих, чтобы суммы набранных ими весовых коэффициентов (по видам работ, которые они будут выполнять) были если не одинаковыми, то по крайней мере имели минимальную разницу. При этом, например, в этом месяце рабочий (тот, который у тебя с коэффициентом 10) будет принимать участие в работе с коэффициентом 35, остальные же могут быть привлечены к любой работе.

Начинает проясняться ;) Т.е. возьмем, для примера, ремонт дороги. У уборки мусора коеффициент трудоемкости, к примеру, 5, у работ по зачистке старого дорожного покрытия коеффициент 15, у асфальтоукладчиков - 30. Необходимо сделать так, чтобы все люди в бригаде выполняли примерно одинаковый объем работ, поскольку оплата их труда идентична, а распределение обязанностей в ручном режиме вызывает нарекания на субъективизм распределяющего. Так?

Добавлено через 2 минуты
Тогда еще сопутствующие вопросы:
- каково количество планируемых/работающих людей? Интересует порядок цифр - десятки, сотни?
- какова длительность планируемого периода?

Количество людей может варьироваться от единиц до сотен.
Период - от дня до месяца или даже года (вобщем то тоже величина неизвестная).

Оки, теперь резюмируем все, что стало известно о задаче.
1. Есть некий перечень работ с фиксированными весовыми коеффициентами.
2. Вероятно есть количество людей, требуемых для выполнения каждой из работ.
3. Вероятно есть среднее целевое количество баллов, которое необходимо набрать каждому из работников.
4. Есть некий список людей, которых необходимо расставить по местам.
5. Есть длительность планируемого периода.
6. Возможно есть личные преференции отдельных людей, могущих выполнять только работы определенного вида.

Необходимо расставить людей по работам таким образом, дабы разница набраных ними баллов за выполнение конкретных работ была минимальна за планируемый период.

Если описание задачи верно, то необходимости в алгоритме разложения числа на сумму из коэффициентов сложности работ я не вижу. Очевидно, что такое разложение будет не единственным, количество вариантов таких разложений будет расти очень быстро по мере увеличения значения самого числа, а главное, построенный массив таких разложений никак не помогает в решении поставленной задачи. Окончательному алгоритму все равно придется заниматься перебором вариантов, а именно брать каждый элемент такого массива и проверять его на применимость в контексте уже принятых решений - запланированных людей на определенные работы.

IMHO, если бы передо мной стояла подобная задача я бы решал ее прямым перебором "в лоб". При реальных числах работников и длительности планируемых периодов число вариантов окажется совсем небольшим.

v_mirgorodsky

Третий пункт не нужен.

"…прямым перебором "в лоб" - это ими?

Нет, это все же не работниками :) Как я понял, они договориться между собой сами не могут ;)

Просто создается массив работ, потом массив работников. Далее прога пытается учесть преференции работника по поводу работ и другие объективные факторы, заполняя план работ для каждого из работников по календарным дням. Далее, останутся частично "недозаполненные" работники - вот эти остатки и будем заполнять перебором. По мере уменьшения количества доступных работ количество вариантов будет быстро уменьшаться. Для ограничения количества вариантов стоит ограничить планируемый период определенной длительностью, к примеру, неделей. Тогда планирование месяца будет состоять из планирования четырех недель и еще 3-х дней. Даже самый старый PIII будет перебирать в секунду пару десятков тысяч вариантов. Однако будет необходимо аккуратно подойти к критерию определения хорошего варианта, иначе работа программы может затянуться ;)

all
Чего-то не понял к чему пришли в итоге.
Я то, например, находил в последовательности медианное или среднее арифметическое значение. Потом к наименьшему значению прибавлял, а от наибольшего отнимал тот коэффициент, с которым в данный момент работаем (начинаю всегда с наибольшего коэффициента), при условии, что результат сложения/вычитания не больше/меньше значения наибольшего/наименьшего значения последовательности в данный момент.
Но часто программа на этом моменте зацикливалась. Да и тяжело и не красиво как-то. Чувствую есть какое-то более элегантное решение.

А вот это и есть решение задачи методом прямого перебора "в лоб". Начальное приближение, взятое как "медианное или среднее арифметическое значение" относится к стратегии ведения перебора вариантов. В зависимости от выбора стратегии можно получить более быструю или медленную сходимость к приемлемому результату.
Здесь, вероятнее всего есть алгоритмическая или логическая ошибка. Скорее логическая, поскольку алгоритмическая проявлялась бы более регулярно. Еще, возможно, недостаточно хорошо проработано условие выхода из циклов перебора и/или фиксации приемлемого варианта. BTW, необходимо очень аккуратно следить, чтобы следующая итерация перебора возможно меньше зависела от результатов предыдущей - иначе очень вероятны зацикливания на определенных наборах входных значений.
К сожалению, все переборы не отличаются красотой и имеют ограниченную область применения. Возможно и есть более элегантное решение вашей задачи, однако с моими познаниями в дискретной математике оно не просматривается.