Difference between revisions of "TADM2E 3.28"
From Algorithm Wiki
m (Sort the left side and right side of array separately using iteration) |
|||
| (12 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | 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]; | |
| − | + | ||
| − | + | 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); | ||
| + | } | ||
} | } | ||
| + | </source> | ||
| + | |||
| + | --[[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); } }
