数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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：我们有三个选择：
交换(0, 1)，所以数组将变为2 1 3
交换(0, 2)，所以数组将变为3 2 1
交换(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个S的和并将其除以27来计算期望值。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数matmul()。这将接收a, v, n
- toret := 一个大小为n的数组，并用0填充
- 对于i in range 0 到 n - 1，执行
- 对于j in range 0 到 n - 1，执行
- toret[i] := toret[i] + a[i, j]*v[j]
- 对于j in range 0 到 n - 1，执行
- 返回toret
- 从主方法中，执行以下操作
- n := A的大小
- temp := 一个新的列表
- swp := (n - 3) /(n - 1)
- swapvalp := ((swp^p)*(n - 1) + 1) /n
- swapvalm :=(1 - (swp^p)) /n
- rev := 一个新的空列表
- dotv := 一个新的空列表
- 对于i in range 0 到 n - 1，执行
- swaprow := 一个新的空列表
- revrow := 一个新的空列表
- 对于j in range 0 到 n - 1，执行
- 在swaprow的末尾插入swapvalm
- 在revrow的末尾插入2*(min(i, j, (n-i-1) 和 (n-j-1+1))/(n*(n - 1))
- swaprow := 一个新的空列表
- revrow := 一个新的空列表
- 对于j in range 0 到 n - 1，执行
- swaprow[i] := swapvalp
- revrow[i] := 1.0 - 2*((i + 1)*(n - i) - min((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)
- 对于i in range 0 到 q，执行
- A := matmul(rev, A, n)
- tot := 0.0
- 对于i in range 0 到 n，执行
- 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))
输入
[1,2,3], 1, 1
输出
0.0
更新于：2021年10月11日
287 次浏览
广告