CSC152 2005F, Class 30: Arrays and Applications Thereof
Admin:
* No readings. Sorry.
* New homework strategy: Daily "small" assignments due before next
class.
Overview:
* Array basics.
* An example: Sum
* More about main
* Another example: Fibonacci
* Using arrays to improve Fibonacci
Arrays!
* Many problems involve computation with collections of data
* How do we represent collections?
* At least three ways in Scheme
* List
* Vector
* Pair structure (tree)
* Files
* We will consider many ways to collect data in Java
* Start with arrays
* Basic concepts:
* Philosophy: A way to organize a collection of data in
which you have "random" access (access by numeric index)
* Applications
* Methods
* Construct (giving length)
* Extract any item from the vector (vector-ref in Scheme)
* Change any item in the vector (set the value at a
particular index) (vector-set!)
* Get the length
* Implementation
* Allocate a contiguous area of memory and pretend to
divide it up for the cells of the vector/array
* If the area of memory starts at m and each item takes
w space, item i is at m+i*w
* Notes
* In most languages, it requires extra computation to extend
In Java:
* Syntax for declaring variables
* Each array has a base type (e.g., "an array of integers";
"an array of strings"; "an array of MadLibs")
* Arrays are homogeneous (although polymorphism works)
* Format
TYPE[] NAME;
* Examples
int[] grades; // Grades is an array of integers
TextBlock[] foo; // foo is an array of textblocks
* Syntax for for main operations
* Construct (giving length)
* Format
NAME = new TYPE[SIZE];
* Examples
grades = new int[5];
foo = new TextBlock[23];
* Default contents is 0/null
* grades contains 0,0,0,0,0
* foo contains null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null
* Construct and initialize
NAME = { VAL1, VAL2, VAL3, ..., VALN };
* Examples
grades = { 90+5, 80, 102, 31, 100 };
foo = { null, new TextLine("Hello"), null, null };
* You must specify all the elements
* AND THE SIZE CAN'T CHANGE
* Example, revised
TextBlock[] foo = { null, new TextLine("Hello"), null, null };
* Extract any item from the array (vector-ref in Scheme)
NAME[pos]
pen.println("The first grade is " + grades[0]);
for (int i = 0; i < grades.length; i++) {
pen.println("Grade number " + i + " is " + grades[i]);
} // for
* Change any item in the array (set the value at a
particular index) (vector-set!)
NAME[pos] = NEW_VALUE;
for (int i = 0; i < grades.length; i++) {
grades[i] = grades[i] + 5;
} // for
* Get the length
NAME.length
Problem: Given an array of doubles, vals, sum the values in vals
* Strategy one: Recursion
public static double sum(double[] vals, int pos)
{
}
* Most programmers use for loops for processing arrays
double total = 0.0;
for (int i = 0; i < vals.length; i++) {
total = total + vals[i];
} // for
return total;
To convert an array to a string, use
java.util.Arrays.toString(nameOfArray)
ASSIGNMENT: Update the sum program so that it ignores non-numbers
entered on the command line
If I type
ji username.arrays.Sum 12 hello 13 goodbye
the output should be
The sum of [12,13] is 25
---
Fibonacci numbers
Rules for computing Fibonacci numbers
0th Fibonacci number is 1
1st Fibonacci number is 1
ith Fibonacci numbers is i-1st Fibonacci number + i-2nd Fibonacci numbers
1,1,2,3,5,8,13,21...