Difference between revisions of "TADM2E 3.28"
From Algorithm Wiki
(Recovering wiki) |
m (Sort the left side and right side of array separately using iteration) |
||
| Line 1: | Line 1: | ||
| − | We need two pass over X: | + | <nowiki>Insert non-formatted text here</nowiki><nowiki>Insert non-formatted text here</nowiki></nowiki>We need two pass over X: |
1. Calculate cumulative production P and Q:<br> | 1. Calculate cumulative production P and Q:<br> | ||
| Line 7: | Line 7: | ||
2. Calculate M:<br> | 2. Calculate M:<br> | ||
<math>M_k=P_{k-1}Q_{k+1}, k\in[1,n]</math> | <math>M_k=P_{k-1}Q_{k+1}, k\in[1,n]</math> | ||
| + | ------------------------------------------------------------------------------------- | ||
| + | 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; | ||
| + | } | ||
| + | } | ||
Revision as of 04:20, 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;
}
}
