Transcript NotesWeek16.Dec 6-10..

CS 180 Problem Solving and Object Oriented
Programming
Fall 2010
http://www.cs.purdue.edu/homes/apm/courses/CS180Fall2010/
This Week:
Notes for Week 16:
Dec 6-10, 2010
Aditya Mathur
Department of Computer Science
Purdue University
West Lafayette, IN, USA
12/6
1.
2.
Exceptions
Recursion
Readings and Exercises for Week 16
Readings:
Chapter: 7.4, 11.2, 11.3
Exercises:
7.6, 7.8, 11.1, 11.2, 11.3
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
2
Revised Project Schedule
Additional office hours:
Tuesday Dec 7:
2-4pm. LWSN 1177
Saturday Dec 11: 2-4pm. LWSN 1177
Special class:
Sunday Dec 12, 2010. 4-7pm. LWSN 3102
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
3
Announcements
•
Final exam: Monday Dec 13, 2010. 1:00pm. EE 129.
•
Please attend the class on Wednesday Dec 8.
•
Programming competition. Chief Guest Dr. Tim Korb.
•
Cash prizes to winner and runner up teams. Thanks to
Lockheed Martin.
•
I will announce the format of the final exam.
•
Please complete course evaluation. Thanks.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
4
Exceptions
An abnormal or unexpected condition during execution.
When such a condition occurs, Java run time
system does not always know how best to proceed
and hence raises an exception.
Some exceptions must be explicitly handled by the
programmer.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
5
Exception: Example 1
public class ExceptionExampleDiv0{
public static void main(String [] args){
int y=1, z=0;
int x=y/z;
}
}
java.lang.ArithmeticException: / by zero
at ExceptionExampleDiv0.main(ExceptionExampleDiv0.java:8)
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
6
Exception: Example 2
public class ExceptionExampleDiv0{
public static void main(String [] args){
int y=1, z=0;
try{
int x=y/z;
Try-catch not required
}catch(ArithmeticException e){
System.out.println(“Divide by zero:”+e); }
}
Divide by zero java.lang.ArithmeticException: / by zero
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
7
Exception: Unchecked (or Error)
• Arise during runtime due to some programming error.
• Not flagged by the compiler. Programmer may choose to
handle these.
• Not subject to Catch requirement.
Examples:
ArithmeticException
ArrayIndexOutOfBounds
NullPOinterException
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
8
Exception: Example 3
public class ExceptionExampleFile{
public static void main(String [] args){
File f=new File("test.txt");
Scanner source=new Scanner(f);
}
}
1 error found:
File:
/Users/apm/www/courses/CS180Fall2010/Notes/Programs/Exc
eptions/ExceptionExampleFile.java [line: 8]
Error:
©Aditya Mathur. CS 180. Fall 2010. Week
/Users/apm/www/courses/CS180Fall2010/Notes/Programs/Exc
6/12/2010
9
16
Exception: Example 4
public class ExceptionExampleFile{
public static void main(String [] args){
File f=new File("test.txt");
try{
Scanner source=new Scanner(f);
}catch(FileNotFoundException e){
System.out.println("File not found "+e);
}
}
}
6/12/2010
File not found
java.io.FileNotFoundExce
ption: test.txt (No such
file or directory)
©Aditya Mathur. CS 180. Fall 2010. Week
16
10
Exception: Checked exceptions
These are subject to the catch requirement.
Programmer is expected to write code to recover from
these exceptions.
Example:
FileNotFoundException
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
11
Exception: try-catch
try{
code where exception might occur;
try-block
}catch(exception object){
code to handle exception
catch-block
}
A catch-block serves as an exception handler.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
12
Exception: try-catch: multiple catch blocks
try{
code where exception might occur;
try-block
}catch(exception object){
code to handle exception;
catch-block
}catch(another exception object{
code to handle exception;
}
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
Another catchblock
13
Exception: try-catch-finally
try{
Code where exception might occur;
try-block
}catch(exception object){
code to handle exception;
catch-block
}finally{
code to handle exception;
finally-block
}
Finally-block always executes after the try-block.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
14
Recursion
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
15
What is recursion?
Recursion is a technique to code functions (or methods) in Java.
We say that a method is recursive, when it calls itself. This
is known as direct recursion.
Indirect recursion occurs when a method is called, before it
completes, by another method.
Recursion is complementary to iteration. While solving a
problem, you may choose to use either.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
16
Example: Factorial
Definition: Iterative [n>=0]
!n= 1, if n=0 or 1
= 1*2*3*…*n;
Definition: Recursive [n>=0]
!n= 1, if n=0 or 1
= n*!(n-1), if n>1
6/12/2010
Basis
Recursion
©Aditya Mathur. CS 180. Fall 2010. Week
16
17
Example: Factorial: Iterative method
Definition: Iterative [n>=0]
!n= 1, if n=0 or 1
= 1*2*3*…*n;
public int factIter(int n){
if(n==0 || n==1)
return 1;
int prod=1;
for (int i=2; i<=n; i++){
prod=prod*i;
}
return (prod);
}
!5=prod=1*2*3*4*5
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
18
Example: Factorial: Recursive method
Definition: Recursive [n>=0]
!n= 1, if n=0 or 1
= n*!(n-1), if n>1
public int factRecur(int n){
if(n==0 || n==1){
return 1;
}else{
return (n*factRecur(n-1));
}
}
factRecur(5)=5*factRecur(4)*factRecur(3)*factRecur(2)*factRecur(1)
=5*factRecur(4)*factRecur(3)*factRecur(2)*1
=5*factRecur(4)*factRecur(3)*2*1
=5*factRecur(4)*3*2*1
=5*4*3*2*1 ©Aditya Mathur. CS 180. Fall 2010. Week
6/12/2010
19
16
Recursion versus Iteration
Iteration suffices for most problems that arise in
practice.
However, in some cases recursion allows compact and
quick solution. An example follows.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
20
Towers of Hanoi: The problem
Given: Three towers A, B, and C. A contains n discs arranged
from bottom to top as shown below.
Problem: Find a sequence of moves such that at the end of
these moves all discs are in C. No larger disc should ever be on
top of a smaller disk. Only one disk can be moved at a time
from one tower to another. Only the top disc can be moved
from a tower.
A
6/12/2010
B
©Aditya Mathur. CS 180. Fall 2010. Week
16
C
21
Towers of Hanoi: Initial and final configurations
Initial configuration
A
B
C
A
B
C
Final configuration
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
22
Towers of Hanoi: Iterative solution
Try this! This will be difficult but certainly worth a try.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
23
Towers of Hanoi: Recursive solution
What is a move?
Only one disc can be moved from one tower to
another. Hence we will write a move as:
move x, y;
x is the tower from where the top disc is moved
and placed on top in tower y.
For example:
move A, B; will move the top disc on A to tower B
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
24
Towers of Hanoi: Recursive solution: Visualization
Start
1
3
A
B
C
2
A
B
C
A
B
C
4
A
6/12/2010
B
C
©Aditya Mathur. CS 180. Fall 2010. Week
16
25
Towers of Hanoi: Recursive program: Live
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
26
Towers of Hanoi: Challenge!
How many moves are required to move n discs from
tower A to tower C?
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
27
Week 16: December 6-10, 2010
Hope you enjoyed this week!
Questions?
Contact your recitation instructor. Make
full use of our office hours.
6/12/2010
©Aditya Mathur. CS 180. Fall 2010. Week
16
28