Transcript CS100A Fall 1997 Lecture 1

CS100A, Fall 1997
Lecture, 6 November:
More on two-dimensional arrays
Declare and allocate two-dimensional array:
int [ ] [ ] b;
b= new int [3] [2];
Note: b.length is 3 and b[0].length is 2.
Assigning to array elements could yield:
b[0]
b[1]
b[2]
b[0][0]
b[0][1]
b[1][0]
b[1][1]
b[2][0]
b[2][1]
5
3
8
-1
7
-5
CS100A, Fall 1997.
Lecture, 6 Nov.
1
Declare and allocate two-dimensional array:
OthelloSquare [ ] [ ] b;
b= new OthelloSquare [3] [2];
Note that each array element contains null.
b[0][0]= new OthelloSquare(5,6);
b[0]
b[1]
b[2]
b[0][0]
b[0][1] null
b[1][0] null
b[1][1] null
b[2][0] null
b[2][1] null
CS100A, Fall 1997.
Lecture, 6 Nov.
2
Example of dealing with a
two-dimensional array: Magic Squares
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
each row sums to 65
each col sums to 65
each diagonal sums
to 65
In Albert Duerer’s
engraving
“Melancolia”, done
in 1514!
CS100A, Fall 1997.
Lecture, 6 Nov.
3
// Assign 0 to all elements of b
static void zeroOut(int b[][]) {
for (int r= 0; r != b.length; r= r+1)
for (int c= 0; c != b[r].length; c= c+1)
b[r][c]= 0;
}
The for loop
for (i= 0; i != n; i= i+1)
S;
equivalent to:
i= 0;
while (i != n) {
S; i= i+1;
}
CS100A, Fall 1997.
Lecture, 6 Nov.
4
Two-dimensional array: array of rows or array of
columns? Entirely up to the interpretation.
Java doesn’t care.
Othelloboard [ ] [ ] board;
board[0] is a column,
board[1] is a column, etc.
Because that is how the GUI interprets things.
In mathematics,
int [ ] [ ] b = {{1,3,5}, {2,5,4}};
usually a “matrix” of rows and columns:
1 3 5
2 5 4
Use index names r,c to help the reader:
board[c][r],
b[r][c]
CS100A, Fall 1997.
Lecture, 6 Nov.
5
17
23
4
10
11
24
5
6
12
18
1
7
13
19
25
8
14
20
21
2
15
16
22
3
9
each row sums to 65
each col sums to 65
each diagonal sums
to 65
Encyclopedia Britannica: The smallest possible
square of odd order has, of course, side-length 3!
To construct n x n magic square n x n ( n odd):
0. Put 1 in b[0][n%2]
1. If i is in b[r][c], then i+1 goes in b[r’][c’],
where r’,c’ determined as follows:
(a) try r’= r-1, if -1, then use r’=n-1.
(b) try c’= c+1, if n, then use c’= 0.
(c) if b[r’][c’] is already filled, use
r’=r+1, c’= c
CS100A, Fall 1997.
Lecture, 6 Nov.
6
// Store a magic square in b
static public void magicSquare(int b[][]) {
int r= 0; int c= 0; int i; int size= b.length;
zeroOut(b);
// Make up the magic square
r= 0; c= size/2; i= 1;
// invariant: Array elements have already been filled
with 1, ..., i-1, and b[r][c] is supposed to get i.
while (b[r][c] == 0) {
b[r][c]= i; i= i+1;
if (b[mod(r-1, size)][mod(c+1, size)]
== 0) {
r= mod(r-1, size);
c= mod(c+1, size);
}
else r= mod(r+1,size);
}
}
CS100A, Fall 1997.
Lecture, 6 Nov.
7
Pascal’s Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
int [] [] p;
p= new int[7][];
p[0]= new int[1];
p[1]= new int[2];
p[2]= new int[3];
// p.length is 7
// p[0].length is 1
// p[1].length is 2
// p]2].length is 3
Elements of an array can be
arrays of different lengths!
CS100A, Fall 1997.
Lecture, 6 Nov.
8
Blaise Pascal (1623-1662).
• Age 20, constructed arithmetical calculator to
help his father in his calculations.
• Elements of Geometry.
• One of creators of probability and statistics.
• Deeply religious (Catholic)
Expected value of an event
(value if the event happens) *
(probability that it will happen)
Lottery:
$1,000,000 * 10**(-9) = $.001
Get to heaven (liberation, self-realization,
moksha) because of leading spiritual life:
(infinity * ? ) =
CS100A, Fall 1997.
Lecture, 6 Nov.
9
// Yield Pascal's triangle with size rows
static public int[][] calculatePascal(int size) {
int[][]p= new int[size][]; //the triangle
// Invariant: rows 0..r-1 have been
//
allocated and calculated
for (int r= 0; r != size; r= r+1) {
// Allocate row i of triangle --its r+1 values
p[r]= new int[r + 1];
// Calculate row r of Pascal's triangle
p[r][0]= 1;
for (int c= 1; c < r; c= c+1)
p[r][c]= p[r-1][c-1] + p[r-1][c];
p[r][r]= 1;
}
return p;
}
CS100A, Fall 1997.
Lecture, 6 Nov.
10
// Print Pascal's triangle p, assuming that its
values are less than 1000
static public void printPascal(int p[][]) {
int size= pascal.length;
for (int r= 0; r != size; r= r+1) {
// Add ((size-r)/2)4 + ((r+1) % 2)*2
// blanks to s
String s= "";
int num;
if (size%2 == 1) num= (size-r)/2;
else
num= (size-r-1)/2;
for (int c= 0; c< num; c= c+1)
s= s + " ";
if (r%2 == 0) s= s + " ";
// Add the numbers in row r to s
for (int c= 0; c <= r; c= c+1)
s= s + printbrc(p, r,c,1000);
System.out.println(s);
}
}
CS100A, Fall 1997.
Lecture, 6 Nov.
11
// Return element b[r][c] of array b as a String,
// with a blank before it.
// Use as many columns as is required to print x.
// So, if x = 325, use 4 characters in total (one
// for the initial blank).
// Precondition, x < 1000
static public String printbrc(
int[][] b, int r, int c, int x)
The program used to demonstrate in this lecture
will be placed on the CS100A web page.
CS100A, Fall 1997.
Lecture, 6 Nov.
12