编程辅导 CS61B: Lecture #5 1

Recreation
What is the sum of the coefficients of
(1 − 3x + 3×2)743(1 + 3x − 3×2)744 after expanding and collecting terms?
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 1

Copyright By PowCoder代写 加微信 powcoder

CS61B Lecture #5: Arrays
• An array is a structured container whose components are
– length, a fixed integer.
– a sequence of length simple containers of the same type, num- bered from 0.
– (.length field usually implicit in diagrams.)
• Arrays are anonymous, like other structured containers. • Always referred to with pointers.
• For array pointed to by A,
– Length is A.length
– Numbered component i is A[i] (i is the index )
– Important feature: index can be any integer expression.
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 2

int[] x, y, z;
String[] a;
x = new int[3];
a = new String[3];
a[1] = “Hello”;
A Few Samples
q=newint[] { 1,2,3 };
// Short form for declarations: int[]r= { 7,8,9 };
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 3

Example: Accumulate Values Problem: Sum up the elements of array A.
static int sum(int[] A) { int N;
for (int i = 0; i < A.length; i += 1) N += A[i]; // For the hard-core: could have written for (i=0, N=0; i k; i -= 1) // Why backwards?
arr[i] = arr[i-1];
/* Alternative to this loop:
System.arraycopy(arr, k, arr, k+1, arr.length-k-1);*/
􏰏 􏰎􏰍 􏰐 􏰏 􏰎􏰍 􏰐
arr[k] = x;
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 5

(Aside) Java Shortcut
• Useful tip: Can write just ‘arraycopy’ by including at the top of the
source file:
import static java.lang.System.arraycopy;
• This means “define the simple name arraycopy to be the equivalent
of java.lang.System.arraycopy in the current source file.”
• Can do the same for out so that you can write
out.println(…);
in place of
System.out.println(…);
• Finally, a declaration like
import static java.lang.Math.*;
means “take all the (public) static definitions in java.lang.Math and make them available in this source file by their simple names (the name after the last dot).”
• Useful for functions like sin, sqrt, etc.
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 6

gazelle into
hartebeest
A: bear gazelle
hartebeest
Growing an Array
Problem: Suppose that we want to change the description above, so that A = insert2 (A, 2, “gnu”) does not shove “skunk” off the end, but instead “grows” the array.
/** Return array, r, where r.length = ARR.length+1; r[0..K-1]
* the same as ARR[0..K-1], r[k] = x, r[K+1..] same as ARR[K..]. */
static String[] insert2(String[] arr, int k, String x) { String[] result = new String[arr.length + 1]; arraycopy(arr, 0, result, 0, k);
arraycopy(arr, k, result, k+1, arr.length-k); result[k] = x;
return result; }
Why do we need a different return type from insert2?? Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 7

Example: Merging
Problem: Given two sorted arrays of ints, A and B, produce their
merge: a sorted array containing all items from A and B. A: 0 2 3 6 9 11 B: 1 4 5 7 8
result: 0 1 2 3 4 5 6 7 8 9 11
Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 8

Example: Merging Program
Problem: Given two sorted arrays of ints, A and B, produce their merge: a sorted array containing all from A and B.
Remark: In order to solve this recursively, it is useful to generalize the original function to allow merging portions of the arrays.
/** Assuming A and B are sorted, returns their merge. */
public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0);
/** The merge of A[L0..] and B[L1..] assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1) {
int N = A.length – L0 + B.length – L1; int[] C = new int[N];
if (L0 >= A.length) arraycopy(B, L1, C, 0, N); else if (L1 >= B.length) arraycopy(A, L0, C, 0, N); else if (A[L0] <= B[L1]) { What is wrong with this implementation? } else { C[0] = A[L0]; arraycopy(mergeTo(A, L0+1, B, L1), 0, C, 1, N-1); B[L1]; arraycopy(mergeTo(A, L0, B, L1+1), 0, C, 1, N-1); Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 9 A Tail-Recursive Strategy public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0); /** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */ static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ ... This last method merges part of A with part of B into part of C. For example, consider a possible call mergeTo(A, 3, B, 1, C, 2) A: -1 0 2 3 6 9 B: 1 4 5 7 8 Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 10 C: ? ? 3 4 5 6 7 8 9 ? ? k A Tail-Recursive Solution public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0); /** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */ static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (??) { } else if (??) { C[k] = A[L0]; return mergeTo(A, ??, B, ??, C, ??) } else { C[k] = B[L1]; return mergeTo(A, ??, B, ??, C, ??) } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 11 A Tail-Recursive Solution public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0); /** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */ static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (??) { C[k] = A[L0];
return mergeTo(A, ??, B, ??, C, ??) } else {
C[k] = B[L1];
return mergeTo(A, ??, B, ??, C, ??) }
Last modified: Mon Feb 3 16:40:24 2020
CS61B: Lecture #5 12

A Tail-Recursive Solution
public static int[] merge(int[] A, int[] B) {
return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0);
/** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */
static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; return mergeTo(A, ??, B, ??, C, ??) } else { C[k] = B[L1]; return mergeTo(A, ??, B, ??, C, ??) } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 13 A Tail-Recursive Solution public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0); /** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */ static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; return mergeTo(A, L0 + 1, B, L1, C, k + 1); } else { C[k] = B[L1]; return mergeTo(A, ??, B, ??, C, ??) } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 14 A Tail-Recursive Solution public static int[] merge(int[] A, int[] B) { return mergeTo(A, 0, B, 0, new int[A.length+B.length], 0); /** Merge A[L0..] and B[L1..] into C[K..], assuming A and B sorted. */ static int[] mergeTo(int[] A, int L0, int[] B, int L1, int[] C, int k){ if (L0 >= A.length && L1 >= B.length) {
} else if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; return mergeTo(A, L0 + 1, B, L1, C, k + 1); } else { C[k] = B[L1]; return mergeTo(A, L0, B, L1 + 1, C, k + 1); } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 15 Iterative Solution In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative: public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0) int L0, L1, k; L0 = L1 = k = 0; while (??) { if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; C[k] = B[L1]; return C; } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 16 Iterative Solution In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative: public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0) int L0, L1, k; L0 = L1 = k = 0; while (L0 < A.length || L1 < B.length) { if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; C[k] = B[L1]; return C; } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 17 Iterative Solution In general, we don’t use either of the previous approaches in languages like C and Java. Array manipulation is most often iterative: public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; // mergeTo(A, 0, B, 0, C, 0) int L0, L1, k; L0 = L1 = k = 0; while (L0 < A.length || L1 < B.length) { if (L1 >= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; L0 += 1; k += 1; C[k] = B[L1]; L1 += 1; k += 1; return C; } Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 18 Iterative Solution II The same, with a for loop: public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; int L0, L1; L0 = L1 = 0; for(intk=0;k= B.length || (L0 < A.length && A[L0] <= B[L1])) { C[k] = A[L0]; L0 += 1; C[k] = B[L1]; L1 += 1; return C; } Invariant (true after int k = 0): 0≤L0≤A.length ∧ 0≤L1≤B.length∧ C.length=A.length+B.length ∧ k=L0+L1 ∧ C[0 : k] is a permutation of A[0:L0] + B[0:L1] ∧ C[0 : k],A,B are sorted. Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 19 Alternative Solution: Removing k Using previous invariant that k=L0+L1 simplifies things: public static int[] merge(int[] A, int[] B) { int[] C = new int[A.length + B.length]; intL0,L1; L0=L1=0; while (L0 + L1 < C.length) { if (L1 >= B.length || (L0 < A.length && A[L0] < B[L1])) { C[L0 + L1] = A[L0]; L0 += 1; return C; } C[L0 + L1] = B[L1]; L1 += 1; 0 L0+L1 Last modified: Mon Feb 3 16:40:24 2020 A.length+B.length CS61B: Lecture #5 20 sorted permutation of α + β Multidimensional Arrays What about two- or higher-dimensional layouts, such as Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 21 Multidimensional Arrays in Java These are not primitive in Java, but we can build them as arrays of arrays: int[][] A = new int[3][]; A[0] = new int[] {2, 3, 4, 5}; A[1] = new int[] {4, 9, 16, 25}; A[2] = new int[] {8, 27, 64, 125}; int[][] A; A=newint[][] { int[][] A = { {2, {4, {8, {2,3,4,5}, {4, 9, 16, 25}, { 8, 27, 64, 125} }; 9, 16, 25}, 27, 64, 125} }; 2345 4 9 16 25 8 2764125 int[][] A = new A[3][4]; for (int i = 0; i < 3; i += 1) for (int j = 0; j < 4; j += 1) A[i][j] = (int) Math.pow(j + 2, i + 1); Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 22 Exotic Multidimensional Arrays • Since every element of an array is independent, there is no single “width” in gen- eral: int[][] A = new int[5][]; A[0] = new int[] A[1] = new int[] A[2] = new int[] A[3] = new int[] A[4] = new int[] • What does this print? {2, 3, 4, 5}; {6, 7, 8}; {9}; 01 2345 678 29 int[][] ZERO = new int[3][]; ZERO[0] = ZERO[1] = ZERO[2] = new int[] {0, 0, 0}; ZERO[0][1] = 1; System.out.println(ZERO[2][1]); Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 23 Exotic Multidimensional Arrays • Since every element of an array is independent, there is no single “width” in gen- eral: int[][] A = new int[5][]; A[0] = new int[] A[1] = new int[] A[2] = new int[] A[3] = new int[] A[4] = new int[] • What does this print? {2, 3, 4, 5}; {6, 7, 8}; {9}; 01 2345 678 29 int[][] ZERO = new int[3][]; ZERO[0] = ZERO[1] = ZERO[2] = new int[] {0, 0, 0}; ZERO[0][1] = 1; System.out.println(ZERO[2][1]); Last modified: Mon Feb 3 16:40:24 2020 CS61B: Lecture #5 24 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com