일부 연산을 수행하여 주어진 배열의 하위 배열의 예상 합을 찾는 프로그램
크기가 n이고 두 개의 값 p와 q인 배열 A가 있다고 가정합니다. A에서 이러한 작업을 수행할 수 있습니다.
- l
- l
첫 번째 작업을 p번 수행하고 두 번째 작업을 q번 수행한 후 l
따라서 입력이 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로 나누어 계산할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- matmul() 함수를 정의합니다. 이것은, v, n 이 걸립니다.
- toret :=크기가 n이고 0으로 채워진 배열
- 0 ~ n - 1 범위의 i에 대해
- 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
- toret[i] :=toret[i] + a[i, j]*v[j]
- 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
- 리턴 토렛
- 기본 방법에서 다음을 수행합니다.
- 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 삽입
- 재생 끝에 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]
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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