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이므로 유한하다는 것을 압니다.
해결책
@Torlack, @Jason Cohen:"겹치는 하위 문제"가 있기 때문에 재귀는 나쁜 생각입니다. 즉, 선택한 경우 a ~처럼 1 그리고 b ~처럼 2, 그러면 최대 497이 되어야 하는 3개의 변수가 남습니다.다음을 선택하면 동일한 하위 문제에 도달합니다. a ~처럼 2 그리고 b ~처럼 1.(이러한 우연의 일치 횟수는 숫자가 늘어날수록 폭발합니다.)
이러한 문제를 공격하는 전통적인 방법은 다음과 같습니다. 동적 프로그래밍:하위 문제에 대한 솔루션의 상향식 테이블을 작성합니다("1개 변수의 조합 수는 0이 됩니까?"로 시작). 그런 다음 반복을 통해 구축합니다("변수의 조합 수는 몇 개입니까?"). N 변수가 추가됩니다. 케이?"는 "얼마나 많은 조합이 있는가?"에 대한 해의 합입니다. n-1 변수가 추가됩니다. 제이?" 0 <= 제이 <= 케이).
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 ...을 더한 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++
}
}
}
이것은 화이트보드에 적을 수 있을 만큼 간단하지만 충분히 신중하게 생각하지 않으면 누군가를 넘어지게 할 만큼 복잡하기 때문에 실제로 인터뷰에서 물어볼 수 있는 좋은 질문이 될 것입니다.또한 구현이 상당히 달라지는 두 가지 다른 답변을 얻을 수도 있습니다.
주문 사항
순서가 중요하다면 모든 솔루션은 모든 변수에 대해 0이 나타나는 것을 허용해야 합니다.따라서 가장 간단한 해결책은 다음과 같습니다.
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을 반환합니다.
순서는 중요하지 않습니다
순서가 중요하지 않은 경우 합계가 이미 발견되지 않은 한 0이 가능하지 않은지 확인하면 되므로 솔루션이 그다지 어렵지 않습니다.
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 사이의 값이 될 수 있습니다.그러면 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이며, 이는 실제로 원래 문제와 동일한 문제로 변수를 하나만 줄였습니다.
메모:Chris가 지적했듯이 이는 실제로 문제를 해결하려는 끔찍한 방법입니다.
실수라면 무한대죠..그렇지 않으면 조금 더 까다롭습니다.
(좋아요, 실수를 컴퓨터로 표현하는 경우 유한한 개수가 있을 것입니다...하지만 그것은 클 것이다!)
다음과 같은 경우 일반 공식이 있습니다.
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) 요소를 포함하는 집합의 조합입니다.
직관은 (n+k-1) 포인트에서 (k-1) 포인트를 선택하고 선택한 두 포인트 사이의 포인트 수를 사용하여 x1,..xk의 숫자를 나타내는 것입니다.
Stack Overflow에 처음으로 답변을 드려서 수학 버전이 좋지 않아서 죄송합니다.
Just a test for code block
Just a test for code block
Just a test for code block
네거티브도 포함되나요?무한.
긍정적인 것만 포함하는가?이 경우에는 "정수"라고 부르지 않고 대신 "자연수"라고 부릅니다.이 경우에는 ...저는 이 문제를 실제로 풀 수 없습니다. 풀 수 있으면 좋겠지만 제 수학은 너무 녹슬었습니다.아마도 이 문제를 해결하는 미친 통합적인 방법이 있을 것입니다.나는 주변에 능숙한 수학에 대한 몇 가지 조언을 드릴 수 있습니다.
최종 결과 인 경우 A의 범위는 0에서 x로, b의 범위는 0에서 (x -a), c의 범위는 0에서 (x -a -b), 그리고 e.
대답은 모든 가능성의 합입니다.
Google에서 좀 더 직접적인 공식을 찾으려고 노력하고 있지만 오늘 Google-Fu가 정말 부족합니다...
