5
Có bao nhiêu kết hợp có thể có của các biến a, b, c, d, e là có thể nếu tôi biết rằng:Số kết hợp có thể
a+b+c+d+e = 500
và rằng họ là tất cả các số nguyên và> = 0, vì vậy tôi biết họ là hữu hạn.
A
Trả lời
11
@ Torlack, @Jason Cohen: Đệ quy là một ý tưởng tồi ở đây, bởi vì có "các vấn đề con chồng lên nhau". Ví dụ: Nếu bạn chọn a là 1 và b là 2 thì bạn còn lại 3 biến sẽ thêm tối đa 497; bạn đến cùng một biểu mẫu con bằng cách chọn a làm 2 và b là 1. (Số lượng các sự trùng hợp như vậy phát nổ khi các con số tăng lên.)
Cách truyền thống để tấn công vấn đề như vậy là dynamic programming: xây dựng bảng dưới cùng của các giải pháp cho các vấn đề phụ (bắt đầu bằng "bao nhiêu kết hợp 1 biến thêm tối đa 0? ") Sau đó xây dựng thông qua lặp lại (giải pháp cho" bao nhiêu kết hợp của các biến số n thêm tối đa k? "Là tổng các giải pháp cho" số lượng kết hợp của n- 1 biến thêm tối đa j? "Với 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
+0
Bạn nói đúng, lập trình động là tốt nhất! Trong giải pháp mã của tôi ở trên, tôi đề nghị sử dụng một bảng bộ nhớ cache của cặp, nhưng có rất nhiều cặp, do đó, DP là tốt hơn. Tuy nhiên tôi đã cố gắng tìm ra giải pháp DP và nó quá khó đối với tôi. :-) –
+0
Thực ra chỉ là các cặp tổng hợp * tổng hợp, vì vậy không quá tệ ở mức 5 x 500. –
+0
@Chris Tôi gặp sự cố khi hiểu ý nghĩa của các giá trị trong mảng bạn xây dựng trong giải pháp của mình. Bạn có thể vui lòng cho tôi một số ví dụ? Trong mảng mảng [2] [1] = 3 và có nghĩa là "bao nhiêu kết hợp (2 + 1) vars thêm tối đa 1? Các kết hợp này là gì? (Tôi giả sử rằng vì chúng là các kết hợp, thứ tự không quan trọng) –
0
Nếu chúng là số thực thì vô hạn ... nếu không thì sẽ phức tạp hơn một chút.
(OK, cho bất kỳ đại diện máy tính của một số thực sẽ có một số hữu hạn ... nhưng nó sẽ lớn!)
+0
Chúng lớn hơn 0, do đó, không lớn như vậy – Turambar
+0
ông cũng đã nêu số nguyên –
1
Một cách nhìn nhận vấn đề như sau:
Đầu tiên, một giá trị có thể là từ 0 đến 500. Sau đó, nếu sau đó b + c + d + e = 500-a. Điều này làm giảm vấn đề của một biến. Chấp nhận cho đến khi hoàn thành.
Ví dụ: nếu a là 500, thì b + c + d + e = 0 có nghĩa là đối với trường hợp = 500, chỉ có một kết hợp các giá trị cho b, c, d và e.
Nếu a là 300, sau đó b + c + d + e = 200, thực tế là vấn đề tương tự như vấn đề ban đầu, chỉ bị giảm một biến.
Lưu ý: Như Chris đã chỉ ra, đây là một cách khủng khiếp thực sự cố gắng giải quyết vấn đề.
-1
Bao gồm từ khóa phủ định? Vô hạn.
Chỉ bao gồm các mặt tích cực? Trong trường hợp này, chúng sẽ không được gọi là "số nguyên", thay vào đó là "naturals". Trong trường hợp này ... Tôi không thể thực sự giải quyết vấn đề này, tôi ước mình có thể, nhưng toán học của tôi quá yếu. Có lẽ có một số cách không thể thiếu để giải quyết vấn đề này. Tôi có thể đưa ra một số gợi ý cho các kỹ năng toán học xung quanh.
là x kết quả cuối cùng, phạm vi của một sẽ là từ 0 đến x, phạm vi của b sẽ là từ 0 đến (x - a), phạm vi của c sẽ là từ 0 đến (x - a - b), và vv cho đến khi e.
Câu trả lời là tổng của tất cả các khả năng đó.
Tôi cố gắng để tìm thấy một số công thức trực tiếp hơn trên Google, nhưng tôi thực sự thấp trên Google-Fu của tôi ngày hôm nay ...
5
Câu trả lời cho câu hỏi của bạn là 2656615626.
Dưới đây là đoạn code mà tạo ra câu trả lời:
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;
}
Trong trường hợp của bạn, summands 5 và sum là 500.
Lưu ý rằng mã này là chậm. Nếu bạn cần tốc độ, hãy lưu trữ kết quả từ các cặp summand,sum.
Tôi giả sử bạn muốn số >=0. Nếu bạn muốn >0, hãy thay thế khởi tạo vòng lặp với a = 1 và điều kiện vòng lặp với a < sum. Tôi cũng giả sử bạn muốn hoán vị (ví dụ:1+2+3+4+5 cộng với 2+1+3+4+5 v.v.). Bạn có thể thay đổi vòng lặp nếu bạn muốn a >= b >= c >= d >= e.
2
Tôi đã giải quyết vấn đề này cho bố tôi vài tháng trước ... mở rộng để bạn sử dụng. Những xu hướng trở thành một vấn đề thời gian vì vậy tôi đã không đi cho tái sử dụng nhất ...
a + b + c + d = sum
i = số kết hợp
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++
}
}
}
3
Điều này sẽ thực sự là một câu hỏi hay để hỏi về một cuộc phỏng vấn vì nó là đủ đơn giản mà bạn có thể viết lên trên một bảng trắng, nhưng đủ phức tạp mà nó có thể vấp một ai đó lên nếu họ don' Tôi suy nghĩ cẩn thận về nó. Ngoài ra, bạn cũng có thể cho hai câu trả lời khác nhau gây ra việc thực hiện khá khác nhau.
Đặt hàng Các vấn đề
Nếu thứ tự quan trọng thì mọi giải pháp cần cho phép không xuất hiện cho bất kỳ biến nào; do đó, giải pháp thẳng nhất về phía trước sẽ như sau:
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);
}
}
nào trả 2656615626.
tự không quan trọng
Nếu thứ tự không quan trọng sau đó là giải pháp không phải là khó khăn hơn nhiều càng tốt bạn chỉ cần đảm bảo rằng số không là không thể trừ khi tổng số đã được tìm thấy.
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);
}
}
nào trả 2573155876.
0
Nó có công thức chung, nếu
a + b + c + d = N
Sau đó số giải pháp không thể thiếu không âm sẽ C(N + number_of_variable - 1, N)
0
@ Câu trả lời của Chris Conway là chính xác. Tôi đã thử nghiệm với một mã đơn giản phù hợp cho các khoản tiền nhỏ hơn.
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);
0
Câu trả lời trong môn toán là 504!/(500! * 4!).
Chính thức, đối với x1 + x2 + ... xk = n, số kết hợp của số không âm x1, ... xk là hệ số nhị thức: (k-1) -kết hợp trong tập hợp chứa (n + k-1) phần tử.
Trực giác là chọn (k-1) điểm từ (n + k-1) điểm và sử dụng số điểm giữa hai điểm được chọn để biểu thị một số trong x1, .. xk.
Xin lỗi về ấn bản toán học nghèo nàn cho lần đầu tiên tôi trả lời Stack Overflow.
Just a test for code block
Just a test for code block
Just a test for code block
Đó là một điều gọn gàng để suy nghĩ về. – jjnguy
Đây có phải là câu hỏi về bài tập về nhà không? –
Không, đồng nghiệp đã hỏi tôi về nó vì tôi đã nghiên cứu một số xác suất, nhưng tôi không thể giải quyết nó – Turambar