Transcript Summary
CS1101: Programming Methodology
http://www.comp.nus.edu.sg/~cs1101x/
Aaron Tan
This is Week 4
Last week:
Selection constructs
First part of Chapter 4 Control Statements
‘if’, ‘switch’, logical operators
This week:
Repetition constructs
‘while’, ‘do … while’, ‘for’
Testing and Debugging
2
Testing and Debugging
Show me your CheckNRIC program!
Next two slides show the question.
How did you test your program?
How did you debug your program?
3
Last week’s Exercise #4
Algorithm for NRIC check code
NRIC consists of 7 digits.
Eg: 8730215
Step 1: Multiply the digits with corresponding
weights 2,7,6,5,4,3,2 and add them up.
Eg: 82 + 77 + 36 + 05 + 24 + 13 + 52 =
16+49+18+0+8+3+10 = 104
Step 2: Divide step 1 result by 11 to obtain
the remainder.
Eg: 104 % 11 = 5
4
Last week’s Exercise #4
Algorithm for NRIC check code (cont…)
Step 3: Subtract step 2 result from 11
Eg: 11 – 5 = 6
Step 4: Match step 3 result in this table for the check
code
1 2 3 4 5 6 7 8 9 10 11
A
B
C
D
E
F
G
H
I
Z
J
Eg: The check code corresponding to 6 is ‘F’.
Therefore, the check code for 8730215 is ‘F’.
5
Writing good programs
Selection and repetition statements are
easy to learn.
But it may not be easy to write good
programs with them.
Logic should be clear
Boolean variables should be descriptive
Don’t use ‘b’, ‘f’, ‘flag’.
Use ‘isValid’, ‘isOdd’, ‘toContinue’
6
Using real numbers (1/2)
Arithmetic operations of real numbers may
yield inaccurate results.
Download RealNumbers.java
double realNum = 0.1;
double sum = 0.0;
for (int i=1; i<=10; i++)
sum += realNum;
System.out.println("sum = " + sum);
if (sum == 1.0)
System.out.println("sum is 1.0");
else
System.out.println("sum is not 1.0");
7
Using real numbers (2/2)
Accept some inaccurancy with tolerance.
final double EPSILON = 0.0000001;
double realNum = 0.1;
double sum = 0.0;
for (int i=1; i<=10; i++)
sum += realNum;
System.out.println("sum = " + sum);
if (Math.abs(sum - 1.0) < EPSILON)
System.out.println("sum is 1.0");
else
System.out.println("sum is not 1.0");
8
Exercise #1 (Simple loop)
Write a program OddIntegers.java to print
odd integers between 1 and 39 inclusive.
Output: 1 3 5 7 9 11 13 15 17 19 … 37 39
Include 3 versions in your program: using
‘while’ loop, ‘do … while’ loop, and ‘for’ loop.
The ‘for’ loop version is already given in the
book!
9
Exercise #2 (Nested loops)
Download the programs LoopsEx1.java,
LoopsEx2.java and LoopsEx3.java from
the Lectures page in the course website.
Hand trace the programs and write out
the outputs without running them.
Verify your answers by running the
programs.
10
Exercise #3 (GCD)
The GCD (greatest common divisor) of two
non-negative integers a and b, not both zero, is
the largest integer that divides both numbers a
and b.
Examples: GCD(0,12) = 12; GCD(3,8) = 1;
GCD(18,12) = 6; GCD(100,300) = 100.
Download BadGCD.java.
Can you improve on this program?
See next slide for the Euclidean algorithm that
computes GCD.
11
Euclidean algorithm
First documented algorithm by Greek mathematician
Euclid in 300 B.C.
To compute the GCD (greatest common divisor) of two
integers.
1. Let A and B be integers with A > B ≥ 0.
2. If B = 0, then the GCD is A and algorithm ends.
3. Otherwise, find q and r such that
A = q.B + r
where 0 ≤ r < B
Note that we have 0 ≤ r < B < A and GCD(A,B) = GCD(B,r).
Replace A by B, and B by r. Go to step 2.
12
Exercise #4 (Coin Change)
Write a program CoinChange.java to
implement the Coin Change problem we
discussed before.
See next slide for problem statement.
Do not use array yet.
13
Coin Change
Given this list of coin denominations: $1, 50 cents, 20
cents, 10 cents, 5 cents, 1 cent, find the smallest
number of coins needed for a given amount. You do
not need to list out what coins are used.
Example 1: For $3.75, 6 coins are needed.
Example 2: For $5.43, 10 coins are needed.
You may assume that the input value is in cents.
Enter amount in cents: 375
Number of coins: 6
14
Exercise #5 (Prime Number; Take-home)
Primality test is a classic programming problem.
Given a positive integer, determine whether it is a
prime number or not.
A prime number has two distinct factors (divisors): 1
and itself. Examples: 2, 3, 5, 7, 11, …
Write a program PrimeTest.java. Some sample runs
shown below:
Enter integer: 131
131 is a prime.
Enter integer: 713
713 is not a prime.
Bring your program to class next week. We will discuss
it.
15
Announcement
Lab #1
Release: 2 September (Tuesday), 2359hr.
Deadline: 10 September (Wednesday),
2359hr.
16
This is Week 4
Next week?
A mini programming test! (argh!)
Chapter 5: Using Pre-Built Methods
The API library
Math class
Wrapper classes
Character class
String methods
Random numbers
17
End of file
18