TADM2E 3.28

From Algorithm Wiki
Revision as of 04:20, 8 April 2015 by Tnoumessi (Talk | contribs)

Jump to: navigation, search

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;