我很想知道以下内容:
给定一个包含 N 个元素的集合,我和我的朋友正在玩游戏。我总是先行动。我们只能以 50% 的几率移除第一个或最后一个元素。我们在游戏中交替轮流。如果只剩下一个元素,我们可以肯定地移除它。我能收集到的预期总和是多少?
For example:N=2 {10,20} Possible sets that I can collect are {10},{20}.
So expected sum is 0.5*10+0.5*20=15.
我的做法:
由于在所有情况下获得可能和的概率都是相等的,因此我们只需要计算所有可能和的总和,然后将其乘以 (0.5)^N/2。
我尝试使用递归来计算所需的总和:
f(i,j)-computes the sum between i and j recursively
f(i,j)=2*a[i]+func(i,j-2)+func(i+1,j-1)+func(i+1,j-1)+func(i+2,j)+2*a[j]);
Initial call f(1,N)
但这种方法似乎不起作用。我该怎么办?
完整功能如下:
class CandidateCode {
static long v[][] = new long[1003][1003];
public static long func(int a[], int i, int j) {
if (i == j)
return v[i][j] = a[i];
if (v[i][j] != 0)
return v[i][j];
else {
if (i > j - 2 && i + 1 > j - 1 && i + 2 > j)
return (v[i][j] += 2 * a[i] + 2 * a[j]);
else
return (v[i][j] += 2 * a[i] + func(a, i, j - 2) + func(a, i + 1, j - 1) + func(a, i + 1, j - 1)
+ func(a, i + 2, j) + 2 * a[j]);
}
}
public static void main(String args[]) {
int n;
int a[] = { 0, 6, 4, 2, 8 };
n = a.length - 1;
System.out.println(func(a, 1, 4) / Math.pow(2, n / 2));
}
}