Количество возможных комбинаций
https://stackoverflow.com/questions/59743
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сколько возможных комбинаций переменных a, b, c, d, e возможно, если я знаю, что:
a+b+c+d+e = 500
и что все они являются целыми числами и > = 0, поэтому я знаю, что они конечны.
Решение
@Торлак, @Джейсон Коэн:Рекурсия здесь плохая идея, потому что существуют "перекрывающиеся подзадачи". Т.е., если вы выберете a как 1 и b как 2, тогда у вас останется 3 переменные , которые в сумме должны составить 497;вы приходите к той же подзадаче, выбирая a как 2 и b как 1.(Количество таких совпадений растет с каждым днем.)
Традиционным способом решения такой проблемы является динамическое программирование:постройте таблицу решений подзадач снизу вверх (начиная с "сколько комбинаций из 1 переменной в сумме равняются 0?"), затем наращивайте с помощью итерации (решение для "сколько комбинаций из n переменные в сумме составляют k?" - это сумма решений вопроса "сколько комбинаций n-1 переменные в сумме составляют j?" с 0 <= j <= k).
public static long getCombos( int n, int sum ) {
// tab[i][j] is how many combinations of (i+1) vars add up to j
long[][] tab = new long[n][sum+1];
// # of combos of 1 var for any sum is 1
for( int j=0; j < tab[0].length; ++j ) {
tab[0][j] = 1;
}
for( int i=1; i < tab.length; ++i ) {
for( int j=0; j < tab[i].length; ++j ) {
// # combos of (i+1) vars adding up to j is the sum of the #
// of combos of i vars adding up to k, for all 0 <= k <= j
// (choosing i vars forces the choice of the (i+1)st).
tab[i][j] = 0;
for( int k=0; k <= j; ++k ) {
tab[i][j] += tab[i-1][k];
}
}
}
return tab[n-1][sum];
}
$ time java Combos 2656615626 real 0m0.151s user 0m0.120s sys 0m0.012s
Другие советы
Ответ на ваш вопрос - 2656615626.
Вот код, который генерирует ответ:
public static long getNumCombinations( int summands, int sum )
{
if ( summands <= 1 )
return 1;
long combos = 0;
for ( int a = 0 ; a <= sum ; a++ )
combos += getNumCombinations( summands-1, sum-a );
return combos;
}
В вашем случае, summands равно 5 и sum составляет 500.
Обратите внимание, что этот код работает медленно.Если вам нужна скорость, кэшируйте результаты из summand,sum пары.
Я предполагаю, что вам нужны цифры >=0.Если ты хочешь >0, замените инициализацию цикла на a = 1 и условие цикла с a < sum.Я также предполагаю, что вам нужны перестановки (например 1+2+3+4+5 plus 2+1+3+4+5 и т.д.).Вы могли бы изменить цикл for, если бы захотели a >= b >= c >= d >= e.
Я решил эту проблему для своего отца пару месяцев назад ... Продлить для вашего использования.Как правило, это одноразовые проблемы, поэтому я не стал выбирать самые многоразовые...
a + b + c + d = сумма
i = количество комбинаций
for (a=0;a<=sum;a++)
{
for (b = 0; b <= (sum - a); b++)
{
for (c = 0; c <= (sum - a - b); c++)
{
//d = sum - a - b - c;
i++
}
}
}
На самом деле это был бы хороший вопрос для собеседования, поскольку он достаточно прост, чтобы его можно было записать на белой доске, но достаточно сложен, чтобы кого-то сбить с толку, если он недостаточно тщательно обдумает его.Кроме того, вы также можете использовать два разных ответа, которые приводят к тому, что реализация будет совершенно разной.
Порядок имеет значение
Если порядок имеет значение, то любое решение должно допускать появление нуля для любой из переменных;таким образом, наиболее простым решением было бы следующее:
public class Combos {
public static void main() {
long counter = 0;
for (int a = 0; a <= 500; a++) {
for (int b = 0; b <= (500 - a); b++) {
for (int c = 0; c <= (500 - a - b); c++) {
for (int d = 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
Который возвращает 2656615626.
Порядок Не имеет значения
Если порядок не имеет значения, то решение не намного сложнее, так как вам просто нужно убедиться, что ноль невозможен, если сумма уже не найдена.
public class Combos {
public static void main() {
long counter = 0;
for (int a = 1; a <= 500; a++) {
for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
Который возвращает 2573155876.
Один из способов взглянуть на проблему заключается в следующем:
Во-первых, a может быть любым значением от 0 до 500.Тогда if следует, что b+ c+ d+ e = 500-a.Это уменьшает проблему на одну переменную.Повторяйте до тех пор, пока не закончите.
Например, если a равно 500, то b + c + d + e=0, что означает, что для случая a = 500 существует только одна комбинация значений для b, c, d и e.
Если a равно 300, то b + c + d + e = 200, что фактически является той же проблемой, что и исходная, только уменьшенной на одну переменную.
Примечание:Как указывает Крис, это ужасный способ на самом деле попытаться решить проблему.
Если это действительные числа , то бесконечные ...в противном случае это немного сложнее.
(Хорошо, для любого компьютерного представления действительного числа было бы конечное число...но это было бы грандиозно!)
Он имеет общие формулы, если
a + b + c + d = N
Тогда число неотрицательных интегральных решений будет равно C(N + number_of_variable - 1, N)
@Chris Conway ответ правильный.Я тестировал с помощью простого кода, который подходит для небольших сумм.
long counter = 0;
int sum=25;
for (int a = 0; a <= sum; a++) {
for (int b = 0; b <= sum ; b++) {
for (int c = 0; c <= sum; c++) {
for (int d = 0; d <= sum; d++) {
for (int e = 0; e <= sum; e++) {
if ((a+b+c+d+e)==sum) counter=counter+1L;
}
}
}
}
}
System.out.println("counter e "+counter);
Ответ по математике равен 504!/(500!* 4!).
Формально, для x1+x2+...xk=n, номер комбинации неотрицательного числа x1,...xk является биномиальным коэффициентом:(k-1) - комбинация из набора, содержащего (n+k-1) элементов.
Интуиция заключается в том, чтобы выбрать (k-1) точек из (n + k-1) точек и использовать количество точек между двумя выбранными точками для представления числа в x1, .. xk.
Извините за плохое издание math за то, что я впервые отвечал на Stack Overflow.
Just a test for code block
Just a test for code block
Just a test for code block
Включая негативы?Бесконечный.
Включая только положительные моменты?В этом случае они назывались бы не "целыми числами", а "натуральными".В данном случае...Я действительно не могу решить эту проблему, хотел бы я этого, но моя математика слишком заржавела.Вероятно, есть какой-то безумный интегральный способ решить эту проблему.Я могу дать несколько советов для тех, кто разбирается в математике.
поскольку x является конечным результатом, диапазон значений a будет от 0 до x, диапазон значений b будет от 0 до (x - a), диапазон значений c будет составлять от 0 до (x - a - b), и так далее до e.
Ответ - это сумма всех этих возможностей.
Я пытаюсь найти какую-нибудь более прямую формулу в Google, но сегодня у меня действительно не хватает Google-Fu...
