通过执行 Python 中的一些操作来查找给定数组的子数组的预期总和的程序

pythonserver side programmingprogramming更新于 2025/12/18 21:32:17

通过执行一些操作来查找给定数组的子数组的预期总和的程序

假设我们有一个大小为 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 个结果，可以通过求出所有 27 个结果的总和并除以 27 来计算预期值。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 matmul() 。这将需要 a、v、n
toret := 一个大小为 n 的数组并用 0 填充
对于范围在 0 到 n - 1 内的 i，执行
- 对于范围在 0 到 n - 1 内的 j，执行
  - toret[i] := toret[i] + a[i, j]*v[j]
返回 toret
从主方法中，执行以下操作:
n := A 的大小
temp := 一个新列表
swp := (n - 3) /(n - 1)
swapvalp := ((swp^p)*(n - 1) + 1) /n
swapvalm :=(1 - (swp^p)) /n
rev := 一个新的空列表
dotv := 一个新的空列表
对于范围在 0 到 n - 1 内的 i，执行
- swaprow := 一个新的空列表
- revrow := 一个新的空列表
- 对于范围在 0 到 n - 1 内的 j，执行
  - 在 swaprow 末尾插入 swapvalm
  - 在 revrow 末尾插入 2*(i、j、(n-i-1) 和 (n-j-1+1)/(n*(n - 1)) 中的最小值
- swaprow := 一个新的空列表列表
- revrow := 一个新的空列表
- 对于范围从 0 到 n - 1 的 j，执行
- swaprow[i] := swapvalp
- revrow[i] := 1.0 - 2*((i + 1)*(n - i) - (i+1) 和 (n - i))/(n*(n-1)) 中的最小值
- 在 temp 末尾插入 swaprow
- 在 rev 末尾插入 revrow
- 在 dotv 末尾插入 2*((i+1)*(n-i) - 1)/(n*(n-1))
A := matmul(temp, A, n)
对于范围从 0 到 q 的 i，执行
- A := matmul(rev, A, n)
tot := 0.0
对于 0 到 n 范围内的 i，执行
- tot := tot + dotv[i]*A[i]
返回 tot

示例

让我们看看下面的实现以便更好地理解 −

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))