Difference between revisions of "TADM2E 3.28"

From Algorithm Wiki
Jump to: navigation, search
(Undo revision 1067 by FuckMatt (talk))
 
(11 intermediate revisions by 5 users not shown)
Line 1: Line 1:
<nowiki>Insert non-formatted text here</nowiki><nowiki>Insert non-formatted text here</nowiki></nowiki>We need two pass over X:
+
We need two passes over X:
  
 
1. Calculate cumulative production P and Q:<br>
 
1. Calculate cumulative production P and Q:<br>
Line 8: Line 8:
 
<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
+
Using Iteration:
-------------------------------------------------------------------------------------
+
 
 +
Java example:
 +
<source lang="java">
 
public class Multiplication {
 
public class Multiplication {
+
  public static int[] product(int[] x) {
+
    int[] M = new int[x.length];
+
 
      private static int productLeft(int[] x,int i,int j){
+
    for (int i = 0; i < x.length; i++) {
if(i<0)
+
      M[i] = product(x, M, i + 1, x.length);  
return 1;
+
    }
return x[i]*productLeft(x, i-1, j);
+
 
}
+
    return M;
      private static int productRight(int[] x,int i,int j){
+
  }
if(i>=j)
+
 
return 1;
+
  private static int product(int[] x, int[] y, int i, int length) {
return x[i]*productRight(x, i+1, j);
+
    if (i == length)
}
+
      return productLeft(x, i - 2, length);
        private static int product(int[] x,int[] y,int i,int j){
+
 
  if(i==j){
+
    return x[i] * productLeft(x, i - 2, length) * productRight(x, i + 1, length);
  return productLeft(x, i-2, j);
+
  }
        }
+
 
return x[i]*productLeft(x, i-2, j)*productRight(x, i+1, j);
+
  private static int productLeft(int[] x, int i, int length) {
            }
+
    if (i < 0)
  public static int[] product(int[] x){  
+
      return 1;
  int[] M=new int[x.length];
+
 
  for (int i=0;i<x.length;i++){
+
    return x[i] * productLeft(x, i - 1, length);
    M[i]=product(x, M, i+1, x.length);  
+
  }
  }
+
 
  return M;
+
  private static int productRight(int[] x, int i, int length) {
  }
+
    if (i >= length)
 +
      return 1;
 +
 
 +
    return x[i] * productRight(x, i + 1, length);
 +
  }
 
}
 
}
 +
</source>
  
 
--[[User:Tnoumessi|Tnoumessi]] ([[User talk:Tnoumessi|talk]]) 00:21, 8 April 2015 (EDT)
 
--[[User:Tnoumessi|Tnoumessi]] ([[User talk:Tnoumessi|talk]]) 00:21, 8 April 2015 (EDT)

Latest revision as of 00:59, 1 August 2020

We need two passes 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:

Java example:

public class Multiplication {
  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;
  }
 
  private static int product(int[] x, int[] y, int i, int length) {
    if (i == length)
      return productLeft(x, i - 2, length);
 
    return x[i] * productLeft(x, i - 2, length) * productRight(x, i + 1, length);
  }
 
  private static int productLeft(int[] x, int i, int length) {
    if (i < 0)
      return 1;
 
    return x[i] * productLeft(x, i - 1, length);
  }
 
  private static int productRight(int[] x, int i, int length) {
    if (i >= length)
      return 1;
 
    return x[i] * productRight(x, i + 1, length);
  }
}

--Tnoumessi (talk) 00:21, 8 April 2015 (EDT)