Transcript programming - The University of Winnipeg

Art of Programming
Yangjun Chen
Dept. Business Computing
University of Winnipeg
Jan. 2004
1
Outline: Art of programming
• Computing factorial
• Sorting numbers
• Computing primes
Jan. 2004
2
Computing Factorial
• The factorial of an integer is the product of that number and all
of the positive integers smaller than it.
- 5! = 5*4*3*2*1 = 120
- 50! =
30414093201713378043612608166064768844377641568960512000000000000
Jan. 2004
3
Computing Factorials
• A simple class to compute factorials:
public class Factorial {
public static int factorial(int x) {
int fact = 1;
for (int i =2; i <= x; i ++)
//loop
fact *= i;
//shorthand for: fact=fact*i;
return fact;
}
}
public class ComputingFactorial {
public static void main(String arg[]) {
int a = Factorial.factorial(Integer.parseInt(arg[0]));
System.out.println(a);
}}
Jan. 2004
4
Computing Factorials
• Recursive Factorials
/**
* This class shows a recursive method to compute factorials. This method
* calls itself repeatedly based on the formula: n! = n*(n-1)!
**/
public class Factorial2 {
public long factorial(long x) {
if (x == 1) return 1;
else return x*factorial(x - 1);
}
}
Jan. 2004
5
Computing Factorials
• Caching factorials
public class Factorial3 {
//create an array to cache values 0! Through 20!
Static long[] table = new long[21];
Static {table[0] = 1;}
//factorial of 0 is 1
//Remember the highest initialized value in the array
static int last = 0;
public static long factorial(int x) {
while (last < x) {
table [last + 1] = table[last]*(last + 1);
last++;
}}
Jan. 2004
6
Sorting Numbers
• Sorting:
Input n numbers, sort them such that the numbers are ordered increasingly.
3 9 1 6 5 4 8 2 10 7
1 2 3 4 5 6 7 8 9 10
Jan. 2004
7
Sorting Numbers
• A simple sorting algorithm
main idea:
Algorithm
Input: an array A containing n integers.
Output: sorted array.
1. i := 2;
2. Find the least element a from A(i) to A(n);
3. If a is less than A(i - 1), exchange A(i - 1) and a;
4. i := i + 1; goto step (2).
Jan. 2004
8
Sorting Numbers
• A simple sorting algorithm
main idea:
1st step:
swap
3 9 1 6 5 4 8 2 10 7
swap
2nd step:
1 9 3 6 5 4 8 2 10 7
1 2 3 6 5 4 8 9 10 7
… ...
Jan. 2004
9
Sorting Numbers
• Sorting program:
import java.lang.*;
public class SortNumber {
public static void sort(double[] nums) {
for(int i = 0; i < nums.length - 1; i++) {
int min = i +1;
for (int j = i+2; j < nums.length; j++) {
if (nums[j] < nums[min]) min = j;
}
if (nums[i] > nums[min]) {
double tmp;
tmp = nums[i]; nums[i] = nums[min]; nums[min] = tmp;}
}}
Jan. 2004
10
Sorting Numbers
public static void main (String[] args) {
double[] nums = new double[10]; //Create an array to hold numbers
for(int i = 0; i < nums.length; i++) //Generate random numbers
nums[i] = Math.random()*100;
sort(nums);
//Sort them
for (int j = 0; j < nums.length; j++) //Print them out
System.out.println(nums [j] );
}
}
Jan. 2004
11
Sorting Numbers
• Quick sort
main idea:
Algorithm quick_sort(from, center, to)
Input: from - pointer to the starting position of array A
center - pointer to the middle position of array A
to - pointer to the end position of array A
Output: sorted array: A’
1. Find the first element a = A(i) larger than or equal to A(center) from
A(from) to A(to);
2. Find the first element b = A(j) smaller than or equal to A(center) from
A(to) to A(from);
3. If i < j then exchange a and b;
4. Repeat step from 1 to 3 until j <= i;
5. If from < j then recursive call quick_sort(from,(from + j)/2, j);
6. If i < to then recursive call quick_sort(i, (i+ to)/2, to);
Jan. 2004
12
Sorting Numbers
• Quick sort
The center element is 5.
main idea: from
1st step: 3
center
9 1
6
to
5
4
8
2
10
j
i
2nd step: 3
2
1
6
5
4
8
9
10
7
3rd step: 3
2 1
4
5
6
8
9
10
7
Smaller than 5
Jan. 2004
7
i=j=5
greater than 5
13
Sorting Numbers
center
from
from center
4th step:
3
5th step:
1
to
2 41
2
3
to
5
6
8
9
10
7
4
i=2
j=2
Jan. 2004
14
6th step: 1
The sequence contains only one element, no sorting.
center from to
7th step:
The center element is 4.
3 4
i=j=1
8th step:
4
The sequence contains only one element, no sorting.
1
Jan. 2004
2
3
4
5
15
6
7
8
9
10
... ...
Jan. 2004
16
Sorting Numbers
-
quick sorting
3, 4, 6, 1, 10, 9, 5, 20, 19, 18, 17, 2, 1, 14, 13, 12, 11, 8, 16, 15
j
i
3, 4, 6, 1, 10, 9, 5, 15, 19, 18, 17, 2, 1, 14, 13, 12, 11, 8, 16, 20
3, 4, 6, 1, 10, 9, 5, 15,16, 18, 17, 2, 1, 14, 13, 12, 11, 8, 19, 20
3, 4, 6, 1, 10, 9, 5, 15, 16, 8, 17, 2, 1, 14, 13, 12, 11, 18, 19, 20
i=17
3, 4, 6, 1, 10, 9, 5, 15, 16, 8, 17, 2, 1, 14, 13, 12, 11
j=16
Jan. 2004
17
Sorting Numbers
• Another Java program for the quick sort:
public class Sorter {
public static void sort (int[] a, int from, int to) {
if ((a == null) || (a.length < 2)) return;
int i = from, j = to;
int center = a[(from + to)/2];
do {
while ((i < to) && (a[i] < center)) i++;
while ((j > from) && (a[j] > center)) j--;
if (i < j) { int tmp =a[i]; a [i] = a[j]; a[j] = tmp;}
i++; j--;
}while (i <= j);
Jan. 2004
18
Sorting Numbers
• Another Java program for the quick sort:
if (from < j) sort(a, from, j);
if (i < to) sort(a, i, to);
}
}
Jan. 2004
19
• Sorting by merging
Merging means the combination of two or more ordered sequence into
a single sequence. For example, can merge two sequences: 503, 703, 765
and 087, 512, 677 to obtain a sequence: 087, 503, 512, 677, 703, 765.
A simple way to accomplish this is to compare the two smallest items,
output the smallest, and then repeat the same process.
503
087
703
512
765
677
087
087
Jan. 2004
503
503
512
703
512
703
677
765
765
677
20
• Merging algorithm
Algorithm Merge(s1, s2)
Input: two sequences: s1 - x1  x2 ...  xm and s2 - y1  y2 ...  yn
Output: a sorted sequence: z1  z2 ...  zm+n.
1.[initialize]
i := 1, j := 1, k := 1;
2.[find smaller] if xi  yj goto step 3, otherwise goto step 5;
3.[output xi]
zk.:= xi, k := k+1, i := i+1. If i  m, goto step 2;
4.[transmit yj  ...  yn] zk, ..., zm+n := yj, ..., yn. Terminate the algorithm;
5.[output yj]
zk.:= yj, k := k+1, j := j+1. If j  n, goto step 2;
6.[transmit xi  ...  xm] zk, ..., zm+n := xi, ..., xm. Terminate the algorithm;
Jan. 2004
21
• Merge-sorting
Algorithm Merge-sorting(s)
Input: a sequences s = < x1, ..., xm>
Output: a sorted sequence.
1. If |s| = 1, then return s;
2. k := m/2;
3. s1 := Merge-sorting(x1, ..., xk);
4. s2 := Merge-sorting(xk+1, ..., xm);
5. return(Merge(s1, s2));
Jan. 2004
22
Computing Primes
• Finding the largest prime number smaller than a specified
integer:
Input integer m, find p  m such that p is a prime and if there is prime p’ >
p then p’ must be larger m.
than m.
1
2
Jan. 2004
3
4
5
6
7
8
9
10
11
12 13 14
15
16 17 18 19 20
23
Computing Primes
• Algorithm
main idea: find primes by eliminating multiples of the form k  j, where j is
a prime smaller than square-root(m) and k is an integer such that k  j  m.
2
prime
...
2 2
2 i
2 j
3 2
3 i
3 j
4 2
4 i
4 j
j
 square-root(m)
...
...
...
Jan. 2004
...
i
24
Computing Primes
Import java.lang.*;
public class Sieve {
public static void main(String[] args) {
int max = 100; //Assign a default value
try {max = Integer.parseInt(args[0]);}
catch (Exception e) {} //Silently ignore exceptions.
//Create an array that specifies whether each number is prime or not.
boolean[] isprime = new boolean[max+1];
//Assume that all numbers are primes, until proven otherwise.
for (int i = 0; i < max; i++) isprime[i] = true;
//We know that that 0 and 1 are not prime. Make a note of it.
isprime[0] = isprime[1] = false;
Jan. 2004
25
Computing Primes
//To compute all primes less than max, we need to rule out multiples of all
//integers less than the square root of max.
int n = (int) Math.ceil(Math.sqrt(max));
for (int i = 0; i <= n; i++) {
if (isprime[i]) { int k = 2;
for (int j = k*i; j < max; j = (k ++)*i)
isprime[j] = false; }
}
int largest;
for (largest = max - 1; !isprime[largest]; largest--); //empty loop body
System.out.println(“The largest prime less than or equal to “ + max + “is ”
+ largest); }}
Jan. 2004
26
Assignment #1
(Assignment due: Thu. Feb. 8, 2001)
1. What does the "plateform independence" mean? How is it implemented in Java?
2. Summarize the basic concepts used in Java, such as class, method, variable,
Constructor, ... (as many as possible)
3. Implement "Caching factorial" and compute 20! using your program.
Trace 10 steps of the computation.
4. Implement "quick sort" and sort a sequence containing 20 integers:
3, 4, 6, 1, 10, 9, 5, 20, 19, 18, 17, 2, 1, 14, 13, 12, 11, 8, 16, 15.
Trace 10 steps of the computation.
5. Implement "Sieve" and find all the primes smaller than 200 using your program.
Trace 10 steps of the computation.
Jan. 2004
27