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

[doro]

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

[ЕЖ]

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

[doro]

ЕЖ:
Ты это имеешь ввиду - 7 троек и 1 двойка

Да.

[ЕЖ]

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

[doro]

Сообщение от ЕЖ

Ну так алгоритм то понятен?

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

[ЕЖ]

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

[PinGUIWin]

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

[doro]

Сообщение от ЕЖ

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

C++

[doro]

Сообщение от PinGUIWin

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

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

[doro]

Сообщение от PinGUIWin;undefined

Для разложения на два числа можно использовать расширенный алгоритм Эвклида

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

[Voland25]

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

#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

[doro]

Сообщение от Voland25

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

#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

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

[Trotil]

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

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

-
-
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;

[v_mirgorodsky]

Сообщение от doro

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

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

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

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

[doro]

Сообщение от Trotil

S(23)=s(26,3)=3*4^2+2*k=56;

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

Сообщение от v_mirgorodsky

для какой задачи потребовалось такое разложение?

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

[Voland25]

Сообщение от v_mirgorodsky

doro, предложенное решение согласуется с информацией, указанной в постах 1 и 3.

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

Сообщение от doro

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

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

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

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

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

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

[doro]

Сообщение от Voland25

Цитата:
Сообщение от doro Посмотреть сообщение
Одни виды работ выполняются ежедневно. Другие - не ежедневно (через день, раз в месяц, и т.п.).
В одном виде работ может быть задействовано много людей, в другом - только один человек.
Это пояснение о весовых коэффициентах?

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

Сообщение от Voland25

составляющая компетентности, то есть кто может что делать

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

Сообщение от Voland25

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

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

[v_mirgorodsky]

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

[doro]

Сообщение от v_mirgorodsky

работников с весовыми коэффициентами 10, 12, 15, 9 и 8

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

[v_mirgorodsky]

Сообщение от doro

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

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

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