vb.net print barcode zebra RECURSION in Java

Generating DataMatrix in Java RECURSION

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class TestBinarySearch { public static void main(String[] args) { int[] a = {22, 33, 44, 55, 66, 77, 88, 99}; print(a); System.out.println("search(a, 44): " + search(a, 44)); System.out.println("search(a, 50): " + search(a, 50)); System.out.println("search(a, 77): " + search(a, 77)); System.out.println("search(a, 100): " + search(a, 100)); } public static void print(int[] a) { System.out.printf("{%d", a[0]); for (int i = 1; i < a.length; i++) { System.out.printf(", %d", a[i]); } System.out.println("}"); } public static int search(int[] a, int x) { return search(a, 0, a.length-1, x); } public static int search(int[] a, int lo, int hi, int x) { // PRECONDITION: a[0] <= a[1] <= ... <= a[a.length-1]; // POSTCONDITIONS: returns i; // if i >= 0, then a[i] == x; otherwise i == -1; if (lo > hi) { return -1; // basis } int i = (lo + hi)/2; if (a[i] == x) { return i; } else if (a[i] < x) { return search(a, i+1, hi, x); } else { return search(a, lo, i-1, x); } } }

The output is:

{22, 33, 44, 55, 66, 77, 88, 99} search(a, 44): 2 search(a, 50): -1 search(a, 77): 5 search(a, 100): -1 The search() method returns the index of the target x: search(a, 44) returns 2 because a[2] = 44 and search(a, 77) returns 5 because a[5] = 77. The method returns 1 when the target is not in the array: search(a, 50) returns 1 because 50 is not in the array.

BINOMIAL COEFFICIENTS The binomial coefficients are the coefficients that result from the expansion of a binomial expression of the form (x + 1)n. For example, (x + 1)6 = x 6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1 The seven coefficients generated here are 1, 6, 15, 20, 15, 6, and 1.

The French mathematician Blaise Pascal (1623 1662) discovered a recursive relationship among the binomial coefficients. By arranging them in a triangle, he found that each interior number is the sum of the two directly above it. (See Figure 9.3.) For example, 15 = 5 + 10. Let c(n,k) denote the coefficient in row number n and column number k (counting from 0). For example, c(6,2) = 15. Then Pascal s recurrence relation can be expressed as c(n, k) = c(n 1, k 1) + c(n 1, k), for 0 < k < n For example, when n = 6 and k = 2, c(6,2) = c(5,1) + c(5,2). EXAMPLE 9.11 Recursive Implementation of the Binomial Coefficient Function

1 2 3 4 5 6

public static int c(int n, int k) { if (k==0 || k==n) { return 1; // basis } return c(n-1,k-1) + c(n-1,k); // recursion }

The basis for the recursion covers the left and right sides of the triangle, where k = 0 and where k = n.

The binomial coefficients are the same as the combination numbers used in combinatorial mathematics and computed explicitly by the formula n 2 n k+1 -----------------------------3 k n In this context, the combination is often written c n k = and is pronounced n choose k. k 8 = (8/1)(7/2)(6/3) = 56. For example, 8 choose 3 is 3 EXAMPLE 9.12 Iterative Implementation of the Binomial Coefficient Function

This version implements the explicit formula given above. The expression on the right consists of k factors, so it is computed by a loop iterating k times:

1 2 3 4 5

n! n c n k = ---------------------- = -k! n k ! 1

n 1 ----------2

public static int c(int n, int k) { if (n < 2 || k == 0 || k == n) { return 1; } int c = 1;

CHAP. 9]