CSC 416 Lecture Notes Week 1 -- part 1
Introduction
Review of Math and Java Background
XAXB = XA+B
XA / XB = XA-B
(XA)B = XAB
XN + XN = 2XN != X2N
2N + 2N = 2N+1
XA = B iff logX B = A
log 2N = N
logA B = logC B / logC A , for A > 1, B,C > 0
log AB = log A + log B , for A,B > 0
log(AB) = B log A , for A,B > 0
log X < X < e X, for all X > 0
N
S 2i = 2N+1 - 1
i=0
N
S Ai = (AN+1 - 1) / (A - 1)
i=0
N
S i = N (N+1) / 2
i=1
A mod N = the remainder after division of A by N.
Question : Is the following statement also true ?
Assume the statement is not true, that is,the number of primes is finite,say, N of them .
We can list them out as P1,P2 ... PN. Then we claim
that we can construct another ,the (N+1)-th, prime number as follows :
PN+1 = P1*P2*..PN + 1 .
Clearly PN+1 is prime since it is not divisible by any prime P1
through PN . This contradict to the the assumption that there are only finite primes.
/**
* Return the sum of the elements in the given numbers array, starting at
* the given index position. If the position is past the end of the array,
* return 0.
*/
public int sumArray(int[] numbers, int position) {
/*
* Base case: Return 0 if the position is past the end of the array.
*/
if (position >= numbers.length)
return 0;
/*
* Recursive step: Add the element at the current position to the
* recursive sum of the elements at position+1 to the end.
*/
else
return numbers[position] + sumArray(numbers, position+1);
}
int Fibonacci(int n) {
if ( n==0 || n==1 ) return 1 ; // F(0) = F(1) = 1
return Fibonacci(n-1) + Fibonacci(n-2) ; // F(n) = F(n-1) + F(n-2)
}
int Fibonacci(int n ) {
int F0 = 1 , F1 = 1 ;
int F2 ;
if ( n == 0 || n == 1 ) return 1 ;
for ( int i = 2 ; i <= n ; i ++ ) {
F2 = F1 + F0 ;
F0 = F1 ;
F1 = F2 ;
}
return F1 ;
}
/**
* Return the largest element in the given array of integers. Return
* Integer.MIN_VALUE if the array is null or empty.
*/
public int findLargest(int[] numbers) {
int largestValue; // Largest value so far
int i; // Array index
/*
* Return Integer.MIN_VALUE if the array is null or empty.
*/
if ((numbers == null) || (numbers.length == 0)) {
return Integer.MIN_VALUE;
}
/*
* Initialize the largest value to the zeroth array element, then loop
* through the remaining elements, reassigning the largest value
* whenever one of the elements is greater than the largest so far.
*/
for (largestValue = numbers[0], i = 1; i < numbers.length; i++) {
if (largestValue < numbers[i]) {
largestValue = numbers[i];
}
}
return largestValue;
}
/**
* Return the largest element in the given array of comparable objects.
* Return null if the array is null or empty.
*/
public Object findLargest(Comparable[] objects) {
Comparable largestValue; // Largest value so far
int i; // Array index
/*
* Return null if the array is null or empty.
*/
if ((objects == null) || (objects.length == 0)) {
return null;
}
/*
* Initialize the largest value to the zeroth array element, then loop
* through the remaining elements, reassigning the largest value
* whenever one of the elements is greater than the largest so far.
*/
for (largestValue = objects[0], i = 1; i < objects.length; i++) {
if (largestValue.compareTo(objects[i]) < 0) {
largestValue = objects[i];
}
}
return largestValue;
}
import java.io.*;
import java.util.*;
/****
*
* Class BasicRecursionTest illustrates the use of a very basic recursive
* function to sum the elements in an array. The elements are read from stdin
* and stored in the array. The resulting sum is printed to stdout.
*
*/
public class BasicRecursionTest {
/**
* Call the recursiveSum method and print the result to stdout.
*/
public static void main(String args[]) throws IOException {
BasicRecursion basic; // The class with the method
BufferedReader reader; // Input stream reader
StringTokenizer toker; // Input stream tokenizer
final int NUM_ELEMENTS = 10; // Number of inputs allowed
int[] numbers // Input array
= new int[NUM_ELEMENTS];
int i; // Working array index
/*
* Instantiate a BasicRecursion class object.
*/
basic = new BasicRecursion();
/*
* Prompt for the input.
*/
System.out.print("0utput up to " +
Integer.toString(NUM_ELEMENTS) + " numbers: ");
/*
* Initialize the input reader and tokenizer.
*/
reader = new BufferedReader(new InputStreamReader(System.in));
toker = new StringTokenizer(reader.readLine());
/*
* Read each input from the terminal.
*/
for (i = 0; toker.hasMoreElements() && i < 10; ) {
/*
* Store the next input in the array, ignoring any non-numeric
* input.
*/
try {
numbers[i] = Integer.parseInt(toker.nextToken());
}
catch (NumberFormatException e) {
continue;
}
/*
* Increment the input index if the read was a legal number.
*/
i++;
}
/*
* Output the array sum to stdout.
*/
System.out.print("The sum is: ");
System.out.println(basic.sumArray(numbers, 0));
System.out.println();
}
}
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
public class ListFiles
{
public static void main( String [ ] args )
{
if( args.length == 0 )
System.out.println( "No files specified" );
for( int i = 0; i < args.length; i++ )
listFile( args[ i ] );
}
public static void listFile( String fileName )
{
FileReader theFile;
BufferedReader fileIn = null;
String oneLine;
System.out.println( "FILE: " + fileName );
try
{
theFile = new FileReader( fileName );
fileIn = new BufferedReader( theFile );
while( ( oneLine = fileIn.readLine( ) ) != null )
System.out.println( oneLine );
}
catch( IOException e )
{ System.out.println( e ); }
finally
{
// Close the stream
try
{
if(fileIn != null )
fileIn.close( );
}
catch( IOException e )
{ }
}
}
}
import java.io.*;
import java.util.*;
public class UsingStringTokenizer
{
public static void main(String[] args) throws Exception
{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter a few integers");
String oneLine = br.readLine();
StringTokenizer str = new StringTokenizer(oneLine);
while(str.hasMoreTokens())
System.out.println(str.nextToken());
// another way to use StringTokenizer
StringTokenizer str2= new StringTokenizer(br.readLine( ));
int numTokens = str2.countTokens( );
int x = Integer.parseInt(str2.nextToken()); // if you know the next token will be an integer
} // end main
}//end class UsingStringTokenizer
import java.io.*;
public class NumberLines
{
public static void main( String [ ] args )
{
PrintWriter fileOut = null;
BufferedReader fileIn = null;
try
{
if( args.length == 1 )
fileOut = new PrintWriter( System.out );
else if( args.length == 0 || args.length > 2 )
throw new Exception( "Usage: java NumberLines sourceFile destFile" );
else if( args[ 0 ].equals( args[ 1 ] ) )
throw new Exception( "Cannot copy to self" );
else
fileOut = new PrintWriter( new BufferedWriter(
new FileWriter( args[ 1 ] ) ) );
fileIn = new BufferedReader( new FileReader( args[ 0 ] ) );
String oneLine;
int lineNum = 0;
while( ( oneLine = fileIn.readLine( ) ) != null )
{
fileOut.print( ++lineNum + "\t");
fileOut.println( oneLine );
}
}
catch( Exception e )
{ System.out.println( e ); }
try
{
if( fileIn != null )
fileIn.close( );
if( fileOut != null )
fileOut.close( );
}
catch( IOException e )
{ }
}
}
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class MaxTest
{
public static void main( String [ ] args )
{
BufferedReader in = new BufferedReader( new
InputStreamReader( System.in ) );
String oneLine;
StringTokenizer str;
int x;
int y;
System.out.println( "Enter 2 ints on one line: " );
try
{
oneLine = in.readLine( );
if( oneLine == null )
return;
str = new StringTokenizer( oneLine );
if( str.countTokens( ) != 2 )
{
System.out.println( "Error: need two ints" );
return;
}
x = Integer.parseInt( str.nextToken( ) );
y = Integer.parseInt( str.nextToken( ) );
System.out.println( "Max: " + Math.max( x, y ) );
}
catch( IOException e )
{ System.err.println( "Unexpected IO error" ); }
catch( NumberFormatException e )
{ System.err.println( "Error: need two ints" ); }
}
}