通过在 Python 中执行一些操作来查找给定数组的子数组的预期总和的程序
通过执行一些操作来查找给定数组的子数组的预期总和的程序
假设我们有一个大小为 n 的数组 A 和两个值 p 和 q。我们可以在 A 上执行这些操作。
随机选择两个索引(l, r)，其中l < r，然后交换A[l]和A[r]
随机选择两个索引 (l, r) 其中 l < r，然后将 A 形式的子数组从索引 l 反转为 r。
在执行第一次操作 p 次和第二次操作 q 次后，我们随机选择两个索引 l & r，其中 l < r 并计算 S = 子数组 A[l..r] 的所有元素的总和，然后我们必须找到 S 的期望值。
因此，如果输入类似于 A = [1,2,3] p = 1 q = 1，那么输出将是 4.667，因为
第 1 步：我们有三个选择 -
swap(0, 1) 所以数组将是 2 1 3
swap(0, 2) 所以数组将是 3 2 1
swap(1, 2) 所以数组将是 1 3 2
第 2 步：对于每个结果，我们再次有三个选择 -
[2 1 3] 到 [1 2 3], [3 1 2], [2 3 1]
[3 2 1] 到 [2 3 1], [1 2 3], [3 1 2]
[1 3 2] 到 [3 1 2], [2 3 1], [1 2 3]
有 9 个可能的数组，所以概率是 1/9。所以这 9 个数组中的每一个都有 3 个可能的和，概率相等。例如，[1 2 3]，我们可以得到 1+2、2+3 和 1+2+3。此输入共有 27 个结果，可以通过求所有 27S 的总和除以 27 来计算期望值。
示例
让我们看看以下实现以获得更好的理解 -
def matmul(a, v, n):toret = [0]*n
for i in range(n):
for j in range(n):
toret[i] += a[i][j]*v[j]
return toret
def solve(A, p, q):
n = len(A)
temp = []
swp = (n - 3)/(n - 1)
swapvalp = (pow(swp, p)*(n - 1) + 1)/n
swapvalm = (1 - pow(swp, p))/n
rev = []
dotv = []
for i in range(n):
swaprow = []
revrow = []
for j in range(n):
swaprow.append(swapvalm)
revrow.append(2*(min(i, j, n - i - 1, n - j - 1) + 1)/(n*(n - 1)))
swaprow[i] = swapvalp
revrow[i] = 1.0 - 2*((i + 1)*(n - i) - min(i + 1, n - i))/(n*(n - 1))
temp.append(swaprow)
rev.append(revrow)
dotv.append(2*((i + 1)*(n - i) - 1)/(n*(n - 1)))
A = matmul(temp, A, n)
for _ in range(q):
A = matmul(rev, A, n)
tot = 0.0
for i in range(n):
tot += dotv[i]*A[i]
return tot
A = [1,2,3]
p = 1
q = 1
print(solve(A, p, q))
输入
[1,2,3], 1, 1输出结果
0.0
以上是 通过在 Python 中执行一些操作来查找给定数组的子数组的预期总和的程序 的全部内容， 来源链接： utcz.com/z/353536.html
