Transcript Writing algorithms u..

Writing algorithms using the
while-statement
Previously discussed
• Syntax of while-statement:
Previously discussed (cont.)
• Statements discussed so far:
• Assignment statement:
variable = expression ;
Previously discussed (cont.)
• Conditional statements:
if ( condition )
statement
if ( condition )
statement1
else
statement2
Previously discussed (cont.)
• Loop (while) statements:
while ( condition )
{
statement1
statement2
...
}
Combining different types of statements
• Computer Science Fact:
• Every programming language (including Java) has 3
types of statements:
• Assignment statements
• Conditional statements
• Loop statements
Combining different types of statements
(cont.)
• The good news is: you have learned all of them now !
• However, you still need to learn how to use them
effectively
Combining different types of statements
(cont.)
• Rule of programming languages:
• Whenever you see a statement in a syntax construct,
you can use any type of statement !!!
Example:
while ( condition )
while ( condition )
{
{
statement
===>
if ( condition2 )
}
{
statement1
}
else
{
statement2
}
}
Combining different types of statements
(cont.)
• Here, we used an if-else (conditional) statement as the
statement in the while-body
•
In fact, the statement1 and statement2 in the then-part and
else-part of the if-else (conditional) statement can themselves
be a assignment statement, a conditional statement, or a loop
statement !!!
• Therefore, you can create very complex programs
Combining different types of statements
(cont.)
• Advice:
• The point of computer programming is not writing
complex programs... but write out an algorithm in simple
steps for a dumb machine (computer).
• There are many different ways to write the same
computer program, some ways can be very convoluted
than others.
• You should keep the structure of computer programs
simple
Combining different types of statements
(cont.)
• We will now learn how to use the power of a programming
language (Java) by combining (nesting) different
statements
Developing computer algorithms
• Pre-requisite to developing a computer algorithm:
• Before you can write a computer program to solve a
problem, you yourself must know what you need to do
Because:
• Programming a computer = tell a computer what to
do to solve a problem
• If you don't know what to do, you cannot tell
someone else (or something else like a computer) what
to do.... (A blind cannot lead a blind...)
Developing computer algorithms (cont.)
• Developing a computer algorithm:
• Develop a computer algorithm = Write down the steps
that a human must do to solve a problem in such a detail
than a dumb machine (computer) can do it !!!
Programming example 1: find all divisors
of a number
• Problem description:
• Write a Java program that reads in an integer n...
• and prints all its divisors
Programming example 1: find all divisors
of a number (cont.)
• A concrete example:
• Input: n = 12
• Output: 1, 2, 3, 4, 6, 12
Programming example 1: find all divisors
of a number (cont.)
• What would you do to solve this problem ?
• Suppose: n = 12
• Check if 12 is divisible by 1
• Check if 12 is divisible by 2
• ...
• Check if 12 is divisible by 12
Programming example 1: find all divisors
of a number (cont.)
• Note:
• We do not need to check numbers > 12 because only
number ≤ 12 can be divisors !
• When the remainder of the division is equal to 0, we print
out the divisor
Programming example 1: find all divisors
of a number (cont.)
• Algorithm:
The algorithm contains some abstract steps that need to be
fleshed out (work out the details)
Programming example 1: find all divisors
of a number (cont.)
• We have learned the programming technique (trick) to test
for divisibility previously:
if ( n % a == 0 )
n is divisible by a;
else
n is not divisible by a;
Programming example 1: find all divisors
of a number (cont.)
• Apply this programming technique to obtain a refined
algorithm:
Now the algorithm contain only (concrete) steps that can be
easily translated into a Java program !!!
Programming example 1: find all divisors
of a number (cont.)
• Java program:
import java.util.Scanner;
public class Divisors01
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n;
int a;
System.out.print("Enter a number n: ");
n = in.nextInt();
// Read in number
Programming example 1: find all divisors
of a number (cont.)
a = 1;
while ( a <= n )
// Run a = 1, 2, ..., n
{
if ( n % a == 0 )
{ // a is a divisor of n
System.out.println(a); // Print a (because it's a divisor)
}
a++;
// Make sure we more to the next number !!
// or else: infinite loop !!!
}
}
}
Programming example 1: find all divisors
of a number (cont.)
• Example Program: (Demo above code)
– Prog file:
http://mathcs.emory.edu/~cheung/Courses/170/Syllabus/07/Progs/
Divisors01.java
• How to run the program:
• Right click on link and save in a scratch directory
• To compile: javac Divisors01.java
• To run:
java Divisors01
The brute force search method: a commonly
used solution method in computer algorithms
• The previous algorithm is an example of the brute force
search method
• The general form of the Brute force search method:
for every possible value x do
{
if ( x is a solution )
print x;
}
The brute force search method: a commonly used
solution method in computer algorithms (cont.)
• Pre-conditions for using the brute force search method:
• The number of possible values that needs to be
searched must be finite
(I.e.: a finite search space)
• There is a method to determine if a value x is a
solution
Programming example 2: find all common
divisors of 2 numbers
• Problem description:
• Write a Java program that reads in 2 numbers x and y...
• and prints all numbers that are divisors of both x and y
Programming example 2: find all common
divisors of 2 numbers (cont.)
• A concrete example:
• Input: x = 24 and y = 16
• Output: 1, 2, 4, 8
Programming example 2: find all common
divisors of 2 numbers (cont.)
• What would you do to solve this problem ?
• Suppose: x = 24 and y = 16
• The lesser of the values is 16
• Therefore, all divisors are ≤ 16
Programming example 2: find all common
divisors of 2 numbers (cont.)
• Check if 16 and 24 are divisible by 1
• Check if 16 and 24 are divisible by 2
• ...
• Check if 16 and 24 are divisible by 16
• When the remainder of both divisions are equal to 0,
we print out the divisor
Programming example 2: find all common
divisors of 2 numbers (cont.)
• Rough algorithm:
input x, y;
min = min(x, y); // this is the range of the brute force
search
for every value a = {1, 2, ...., min} do
{
if (x and y are divisible by a)
{
print a;
}
}
Programming example 2: find all common
divisors of 2 numbers (cont.)
• Algorithm (structured diagram):
Programming example 2: find all common
divisors of 2 numbers (cont.)
• Java program:
import java.util.Scanner;
public class Divisors02
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int x, y, a, min = 0;
x = in.nextInt();
y = in.nextInt();
if ( x < y )
min = x;
else
min = y;
// Read in x
// Read in y
// Find min(x,y)
Programming example 2: find all common
divisors of 2 numbers (cont.)
a = 1;
while ( a <= min )
// Run a = 1, 2, ..., min(x,y)
{
if ( x % a == 0 && y % a == 0 )
{ // a is a divisor of x and y
System.out.println(a); // Print a (because it's a common divisor)
}
a++;
// Make sure we move to the next number !!
// or else: infinite loop !!!
}
}
}
Programming example 2: find all common
divisors of 2 numbers (cont.)
• Example Program: (Demo above code)
– Prog file:
http://mathcs.emory.edu/~cheung/Courses/170/Syllabus/07/Progs/
Divisors02.java
• How to run the program:
• Right click on link and save in a scratch directory
• To compile: javac Divisors02.java
• To run:
java Divisors02
Programming example 3: factor a number
(into prime factors)
• Problem description:
• Write a Java program that reads in an integer number
x....
• and prints the prime factorization of the number x
Programming example 3: factor a number
(into prime factors) (cont.)
• A concrete example:
• Input: x = 420
• Output: 2, 2, 3, 5, 7 (because 2 x 2 x 3 x 5 x 7 = 420
and all factors are prime numbers)
Programming example 3: factor a number
(into prime factors) (cont.)
• What would you do to solve this problem ?
• Suppose: x = 420
• Factorization algorithm taught in High Schools:
The number 420 is divisible by 2.
Factor out the number 2:
210
-----2 / 420
Programming example 3: factor a number
(into prime factors) (cont.)
The number 210 is divisible by 2.
Factor out the number 2:
105
-----2 / 210
Programming example 3: factor a number
(into prime factors) (cont.)
The number 105 is not divisible by 2 ==> try 3 !!!
The number 105 is divisible by 3.
Factor out the number 3:
35
-----3 / 105
Programming example 3: factor a number
(into prime factors) (cont.)
The number 35 is not divisible by 3 ==> try 4 !!!
The number 35 is not divisible by 4 ==> try 5 !!!
The number 35 is divisible by 5.
Factor out the number 5:
7
----5 / 35
Programming example 3: factor a number
(into prime factors) (cont.)
The number 7 is not divisible by 5 ==> try 6 !!!
The number 7 is not divisible by 6 ==> try 7 !!!
The number 7 is divisible by 7.
Factor out the number 7:
1
----7/ 7
Programming example 3: factor a number
(into prime factors) (cont.)
• Rough algorithm:
input x;
a = 2;
<---- Try use a = 2 as factor for x
as long as x is not equal to 1 do
{
if (x is divisible by a)
{ // a is a factor of x !!!
print a; (Because we have found another factor)
Remove factor a from the number x (and continue)
}
else
{
Try use a+1 as factor
}
}
Programming example 3: factor a number
(into prime factors) (cont.)
• Algorithm (structured diagram):
Programming example 3: factor a number
(into prime factors) (cont.)
• Check for correctness !!!
• This algorithm is complicated enough to warrant a
correctness check
• We do so using a small example: suppose x = 12
Programming example 3: factor a number
(into prime factors) (cont.)
• Execution of the algorithm:
• Iteration 1 through the while-loop:
It has printed the factor 2 and starts a new loop with x = 6
Programming example 3: factor a number
(into prime factors) (cont.)
• Iteration 2 through the while-loop: (notice that x = 6 in this
iteration !)
It has printed another factor 2 and starts a new loop with x = 3
Programming example 3: factor a number
(into prime factors) (cont.)
• Iteration 3 through the while-loop: (notice that x = 3 in this
iteration !)
Because a = 2 is not a factor of x = 3, the else-part is executed.
A new iteration is started with a = 3 (we are trying a new factor)
Programming example 3: factor a number
(into prime factors) (cont.)
• Iteration 4 through the while-loop: (notice that a = 3 in this
iteration !)
It has printed the factor 3 and starts a new loop with x = 1
Programming example 3: factor a number
(into prime factors) (cont.)
• Iteration 5 through the while-loop: (notice that x = 1 in this
iteration !)
The loop-continuation-condition is not true !!!
The while-loop terminates
Programming example 3: factor a number
(into prime factors) (cont.)
Result:
• The program has printed the factors 2, 2, 3
• (Which is correct !!!)
Programming example 3: factor a number
(into prime factors) (cont.)
• Java program:
import java.util.Scanner;
public class Factor01
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int x;
int a;
System.out.print("Enter a number x: ");
x = in.nextInt();
// Read in number
Programming example 3: factor a number
(into prime factors) (cont.)
a = 2;
while ( x > 1 )
{
if ( x % a == 0 )
{ // a is a factor of x
System.out.println(a); // Print a (because it's a divisor)
x = x / a;
}
else
{
a++;
}
}
}
}
// Remove factor a from x
// Use next number as factor
Programming example 3: factor a number
(into prime factors) (cont.)
• Example Program: (Demo above code)
– Prog file:
http://mathcs.emory.edu/~cheung/Courses/170/Syllabus/07/Progs/
Factor01.java
• How to run the program:
• Right click on link and save in a scratch directory
• To compile: javac Factor01.java
• To run:
java Factor01