पायथन में कुछ ऑपरेशन करके दी गई सरणी के सबएरे के अपेक्षित योग का पता लगाने का प्रोग्राम
मान लीजिए हमारे पास एक सरणी A है जिसका आकार n है और दो मान p और q हैं। हम A पर ये ऑपरेशन कर सकते हैं।
- यादृच्छिक रूप से दो इंडेक्स (l, r) चुनें जहां l < r, फिर A[l] और A[r] को एक्सचेंज करें
- यादृच्छिक रूप से दो इंडेक्स (l, r) चुनें जहां l < r, फिर इंडेक्स l से r तक A के सबएरे को रिवर्स करें
पहला ऑपरेशन p बार और दूसरा ऑपरेशन q बार करने के बाद, हम यादृच्छिक रूप से दो इंडेक्स l और r चुनते हैं जहां l < r और S = सबएरे A[l..r] के सभी तत्वों का योग गणना करते हैं, फिर हमें S का अपेक्षित मान ढूंढना है।
उदाहरण के लिए, यदि इनपुट A = [1,2,3] p = 1 q = 1 है, तो आउटपुट 4.667 होगा क्योंकि...
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- matmul() नामक एक फंक्शन परिभाषित करें। यह a, v, n लेगा
- toret := आकार n की एक सरणी जिसे 0 से भरें
- i के लिए 0 से n - 1 तक की रेंज में, करें
- j के लिए 0 से n - 1 तक की रेंज में, करें
- toret[i] := toret[i] + a[i, j]*v[j]
- j के लिए 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 के लिए 0 से n - 1 तक की रेंज में, करें
- swaprow := एक नई खाली सूची
- revrow := एक नई खाली सूची
- j के लिए 0 से n - 1 तक की रेंज में, करें
- swapvalm को swaprow के अंत में डालें
- 2*(i, j, (n-i-1) और (n-j-1+1) के न्यूनतम)/(n*(n - 1)) को revrow के अंत में डालें
- swaprow[i] := swapvalp
- revrow[i] := 1.0 - 2*((i + 1)*(n - i) - (i+1) और (n - i) के न्यूनतम)/(n*(n-1))
- swaprow को temp के अंत में डालें
- revrow को rev के अंत में डालें
- 2*((i+1)*(n-i) - 1)/(n*(n-1)) को dotv के अंत में डालें
- A := matmul(temp, A, n)
- i के लिए 0 से q तक की रेंज में, करें
- A := matmul(rev, A, n)
- tot := 0.0
- i के लिए 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