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: 82 + 77 + 36 + 05 + 24 + 13 + 52 =
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