Difference between revisions of "TADM2E 3.28"
From Algorithm Wiki
m (Sort the left side and right side of array separately using iteration) |
|||
| Line 33: | Line 33: | ||
int[] M=new int[x.length]; | int[] M=new int[x.length]; | ||
for (int i=0;i<x.length;i++){ | for (int i=0;i<x.length;i++){ | ||
| − | M[i]=product(x, M, i+1, x.length); | + | M[i]=product(x, M, i+1, x.length); |
} | } | ||
return M; | return M; | ||
} | } | ||
} | } | ||
| + | |||
| + | --[[User:Tnoumessi|Tnoumessi]] ([[User talk:Tnoumessi|talk]]) 00:21, 8 April 2015 (EDT) | ||
Revision as of 04:21, 8 April 2015
Insert non-formatted text hereInsert non-formatted text here</nowiki>We need two pass over X:
1. Calculate cumulative production P and Q:
$ P_0 = 1, P_k=X_k P_{k-1}=\prod_{i=1}^kx_i $
$ Q_n = 1, Q_k=X_k Q_{k+1}=\prod_{i=k}^nx_i $
2. Calculate M:
$ M_k=P_{k-1}Q_{k+1}, k\in[1,n] $
Using Iteration
public class Multiplication {
private static int productLeft(int[] x,int i,int j){
if(i<0) return 1; return x[i]*productLeft(x, i-1, j); }
private static int productRight(int[] x,int i,int j){
if(i>=j) return 1; return x[i]*productRight(x, i+1, j); }
private static int product(int[] x,int[] y,int i,int j){
if(i==j){ return productLeft(x, i-2, j);
}
return x[i]*productLeft(x, i-2, j)*productRight(x, i+1, j);
}
public static int[] product(int[] x){
int[] M=new int[x.length]; for (int i=0;i<x.length;i++){ M[i]=product(x, M, i+1, x.length); } return M;
}
}
