交通大学资讯工程学系

,*,按一下以編輯母片標題樣式,交通大學資訊工程學系 蔡文能,第,58,頁,Java,按一下以編輯母片本文樣式,第二層,第三層,第四層,第五層,More Java Examples,Programming in Java,More examples, ,交通大學資訊工程學系,Agenda,Computing factorial,Loop method,Recursive method,Other Recursive examples,Computing primes,Sieve method,Sorting an array,Selection Sort,Insertion Sort,Bubble Sort,Quick Sort,Merge Sort,List,ArrayList, Generic type,2,Computing Factorial,The factorial of an integer is the product of that number and all of the positive integers smaller than it.,-0! = 1,-1! = 1,. . .,-5! = 5*4*3*2*1 = 120,-6! = 6*5*4*3*2*1 = 720,. . .,-50! =,30414,09320,17133,78043,61260,81660,64768,84437,76415,68960,51200,00000,00000,BigDecimal, BigInteger,3,Factorial - Iteration,public class Factorial ,public static long factorial(int n) ,long fact = 1;,for (int i =2; i = n; i +)/for Loop,fact *= i;/shorthand for,fact=fact*i;,return fact;,public class ComputingFactorial ,public static void main(String arg ) ,long a = Factorial.factorial(Integer.parseInt(arg0);,System.out.println(Factorial of + arg0 + = + a);,In separate files,4,Recursion 遞迴概念,很久很久以前, 這裡有一座山, 山裡有一座廟, 廟裡有個老和尚和小和尚, 小和尚要老和尚說故事給他聽。老和尚就說:很久很久以前, 這裡有一座山, 山裡友一座廟, 廟裡有個老和尚和小和尚, 小和尚要老和尚說故事給他聽。.,莊子與惠子游於濠梁之上。莊子曰：鯈於出游從容，是魚之樂也。,惠子曰:子非魚焉知魚之樂?,莊子曰:子非我焉知我不知魚之樂?,惠子曰:子非我焉知我不知你不知魚之樂?,莊子曰:子非我焉知我不知你不知我知魚之樂?,惠子曰:子非我焉知我不知你不知我不知你不知魚之樂?,莊子曰:子非我焉知 . !#$%&*? .,5,Factorial Recursion, in Java,/*,* 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 static long factorial(int n) ,if (n = 1) return 1;,else,return n*factorial(n - 1);,6,N Factorial ( Recursive版 ),long factorial(int n) ,if( n 0) return,-,factorial(,-,n);,if( n =1 | n=0) return 1;,return n * factorial(n,-,1);, /*告訴我,n-1 階乘, 我就給你 n 階乘*/,#include ,int main( ),printf(5! = %ldn, factorial(5);,N階乘就是N乘以N-1階乘,C語言版本,7,歐幾里得的最大公約數,輾轉相除法 (recursive概念!),GCD(m, n) = GCD(n, m%n),但如果 n 是 0 則答案為 m,long,gcd(long m, long n) ,if(n=0) return m;,return gcd(n, m%n);,如何寫成non-recursive version ?,8,最大公約數,non-recursive,版,long,gcd(long m, long n) ,int r; /* remainder */,while(n != 0) ,r = m%n;,m = n;,n = r;,return m;,9,Recursive 也可以很有趣(1/3),Fibonacci Series: (費氏數列),一開始有一對兔子,小兔子隔一個月可以長大為成兔,每對成兔每隔一個月可生出一對兔子,假設兔子永遠不死,問第 n 個月時有幾對兔子 ？,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . fib(n),0 1 2 3 4 5 6 7 8 9 10 11 = n,10,Recursive 也可以很有趣(2/3),long fib(int n) ,if( n 0) return 0;,if( n =1 | n=0) return 1;,return fib(n-1)+fib(n-2);,/*,給我 n 我就告訴你第 n 個月時有幾對兔子,*/,/*,第n個月兔子數=第 n-1 個月兔子+第 n-2 個月兔子,*/,/*但是, 最開始兩個月例外 ! */,11,Recursive 也可以很有趣(3/3),Fibonacci Series(,費氏數列,):,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,34/55 = 55/89 = 89/144 = 0.618 黃金分割比:),神奇的費氏數列:,任何事物接近這些數字會有變化,請看 . .,可,怕,的,巧合: !?,三 重 魔 力 . . .,民國 34 年,台灣光復, 民國,89年,變天,國民黨從,日本手上,搶回,台灣,執政剛好,55 年!,12,問題與思考 (Recursion),寫出,non-recursive,版的Fibonacci function ?,考慮小兔子隔,兩,個月可以長大為成兔 ?,考慮成兔的懷孕期是,兩,個月 ?,其他 Recursive 問題,Recursive 版的 binary search,Quick sort,Hanoi tower problem,13,Factorial cache ans in a Table,public class Factorial3 ,/create an array to cache values 0! Through 20!,static long table = new long21;,static ans0 = 1; /factorial of 0 is 1,static int last = 0;,public static long factorial(int n) ,if(n = last) return ansn;,long tmp = anslast;,int k = last;,while (k n) ,tmp = (k+1) * tmp; /*,(k+1) !,*/,if(last ,p,then,p,must be larger than,m,.,Finding all prime numbers that smaller than a specified integer?,1,2,4,3,5,7,6,8,9,12,14,15,16,18,20,10,11,13,17,19,15,Computing Primes (2/3),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,.,.,.,prime,2,i,j,square-root(,m,),2,3,4,.,.,.,2,3,4,2,3,4,2,2,2,i,i,i,j,j,j,16,Computing Primes (3/3),Finding all prime numbers that smaller than a specified integer?,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20,17,Example: Find Primes (1/2),Import java.lang.*;,public class Sieve ,public static void main(String args) ,int max = 100; /Assign a default value,try max = Integer.parseInt(arg0);,catch (Exception e) /Silently ignore exceptions.,/Create an array that specifies whether each number is prime or not.,Boolean isprime = new booleanmax+1;,/Assume that all numbers are primes, until proven otherwise.,for (int i = 0; = max; i+) isprimei = true;,/We know that that 0 and 1 are not prime. Make a note of it.,isprime0 = isprime1 = false;,18,Example: Find Primes (2/2),/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 (isprimei) int k = 2;,for (int j = k*i; j = max; j = (k +)*i),isprimej = false; ,int largest;,for (largest = max; !sprimelargest; largest-); /empty loop body,System.out.println(The largest prime less than or equal to + max + is ,+ largest);,19,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,20,Selection Sort (1/4),A simple sorting algorithm,Purpose:,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; if (,i,= n) goto step (2).,21,Selection Sort (2/4),1st step:3 9 1 6 5 4 8 2 10 7,2nd step:1 9 3 6 5 4 8 2 10 7,1 2 3 6 5 4 8 9 10 7, .,swap,swap,22,Selection Sort (3/4),Sorting program:,public class,SelSort,public static void sort(double ,nums,) ,for(int,i = 0; i ,nums.length,; i+) ,int,min = i +1;,for (,int,j = i+2; j ,nums.length,; j+) ,if (,numsj, ,numsmin,) ,double,tmp,;,tmp,=,numsi,;,numsi, =,numsmin,;,numsmin, =,tmp,;,23,Selection Sort (4/4),In separate file:,public class,SortNumber,public static void main (String ,args,) ,double ,nums,= new double10; /Create an array to hold numbers,for(int,i = 0; i ,nums.length,; i+) /Generate random numbers,numsi, =,Math.random( )*100,;,SelSort.sort(nums,);/Sort them,for (,int,j = 0; j ,nums.length,; j+) /Print them out,System.out.println(nums,j );,Math.random( ) : see next slide,24,Uniform random 0, 1),25,Normal Distribution Random number,26,Insertion Sort,public class InsSort ,public static void sort(double nums) ,for(int i = 1; i =0) & numsk tmp ) /*,smaller than me,*/ numsk+1 = numsk); /* move it down */,-k,;,numsk+1 = tmp; /*,copy it into correct position,*/,27,Test the Insertion Sort,In separate previous example (Selection sort):,public class,SortNumber,public static void main (String ,args,) ,double ,nums,= new double10; /Create an array to hold numbers,for(int,i = 0; i ,nums.length,; i+) /Generate random numbers,numsi, =,Math.random( )*100,;,InsSort.sort(nums,);/Sort them using insertion sort,for (,int,j = 0; j =0;,-i,) ,int flag = 0; /*,Assume no exchange,*/,for(k=0; k numsk+1 ) /*,incorrect order,*/,double tmp=numsk; numsk=numsk+1; numsk+1=tmp;,+flag;,if(flag = 0) break; /* no need to do next pass */,29,Algorithm,quick_sort,(array,A,from, to),Input: from - pointer to the starting position of array,A,to - pointer to the end position of array,A,Output: sorted array:,A,1.Choose any one element as the pivot;,2.Find the first element,a = A,i larger than or equal to,pivot,from,A,from to,A,to;,3.Find the first element,b = A,j smaller than or equal to,pivot,from,A,to to,A,from;,4.If i j then exchange,a,and,b;,5.Repeat step from 2 to 4 until j = i;,6.If from j then recursive call,quick_sort,(,A,from, j);,7.If i to then recursive call,quick_sort,(,A,i, to);,Quick Sort (1/6),30,Quick sort,main idea:,1st step:3 1 6,5,4 8 10 7,2nd step: 3 2 1,5,8 9 10 7,3rd step: 3 2 1 4,5,6 8 9 10 7,Choose 5 as pivot,from,to,2,9,6,4,Smaller than any integer,right to 5,greater than any integer,left to 5,i,j,Quick Sort (2/6),31,Quick sort,4th step: 2 4 5 6 109,5th step: 1 2 3 4 5,pivot,from,to,3,1,8,7,5 6 7 8 10 9,6th step:,pivot,from,to,7 8 10 9,7th step:,9 10,8th step:,Quick Sort (3/6),32,public class QuickSorter ,public static void sort (int a, int from, int to) ,if (a = null) | (a.length 2) return;,int i = from, j = to;,int pivot = a(from + to)/2;,do ,while (i from) ,if (i j) int tmp =ai; a i = aj; aj = tmp;,i+; j-;,while (i = j);,if (from j) sort(a, from, j);,if (i to) sort(a, i, to);,Quick Sort (4/6),33,14,3, 4, 6, 1, 10, 9, 5,20, 19,14,1, 12, 2, 15, 21, 13, 18, 17,8, 16,3, 4, 6, 1, 10, 9, 5,8,19,1, 12, 2, 15, 21,13, 18, 17,16,3, 4, 6, 1, 10, 9, 5, 8,13,1, 12, 2,15, 21,19, 18, 17, 20, 16,i,j,3, 4, 6, 1, 10, 9, 5, 8, 13, 1, 12, 2,i,j,Quick Sort (5/6),3, 4, 6, 1, 10, 9, 5, 20, 19,14,12, 2, 15, 21, 13, 18, 17, 8, 16, 1,j,i,20,14,i,j,3, 4, 6, 1, 10, 9, 5, 8, 13,1, 12, 2,14, 21, 19, 18, 17, 20, 16,15,14,34,public class BQSorter ,public static void sort (int a, int from, int to) ,if (a = null) | (a.length = to) return;,int k = (from + to)/2; int tmp =ato; a to = ak; ak = tmp;,int pivot = ato; int i = from,j = to-1;,while(i j ) ,while (i j) ,while (i = pivot) j-;,if (i j) tmp =ai; a i = aj; aj = tmp;,;,tmp =ai; a i = ato; ato = tmp;,if (from i-1) sort(a, from, i-1);,if (i to) sort(a, i+1, to);,Quick Sort (6/6),35,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.,503703765,087512677,087,503703765,512677,087503,703765,512677,Merge Sort (1/3),36,Algorithm,Merge,(s1, s2),Input: two sequences: s1 - x1, x2 . x,m,and s2 - y1, y2 . y,n,Output: a sorted sequence: z1, z2 . z,m,+,n,.,1.initialize,i,:= 1,j,:= 1,k,:= 1;,2.find smallerif,x,i, y,j,goto step 3, otherwise goto step 5;,3.output,x,i,z,k,.:=,x,i,k,:=,k,+1,i,:=,i+,1. If,i,m, goto step 2;,4.transmit,y,j, . y,n, z,k,., z,m+n,:= y,j,., y,n,. Terminate the algorithm;,5.output,y,j,z,k,.:= y,j,k,:=,k,+1,j,:=,j+,1. If,j,n, goto step 2;,6.transmit,x,i, . x,m, z,k,., z,m+n,:= x,i,., x,m,. Terminate the algorithm;,Merge Sort (2/3),37,Algorithm,Merge-sorting,(s),Input: a sequences s = ,Output: a sorted sequence.,1. If |s| = 1, then return s;,2.,k,:=,m/,2;,3. s1 := Merge-sorting(,x,1,., x,k,);,4. s2 := Merge-sorting(,x,k,+1,., x,m,);,5. return(,Merge,(s1, s2);,Merge Sort (3/3),38,Time complexity of Mergesort,Takes roughly,n,log,2,n,comparisons.,Without the shortcut, there is no best or worst case.,With the optional shortcut, the best case is when the array is already sorted: takes only,(,n,-,1),comparisons.,39,Binary Search (1/5),Works for an array of numbers or objects that can be compared and are arranged in ascending (or descending) order.,A very fast method: only 20 comparisons are needed for an array of 1,000,000 elements; (30 comparisons can handle 1,000,000,000 elements; etc.),40,Binary Search (2/5),Main idea: “divide and conquer”:,compare the target value to the middle element;,if equal, all set,if smaller, apply binary search to the left half;,if larger, apply binary search to the right half.,. MI MN MO MS MT NC ND .,. MI MN MO MS MT NC ND .,NJ,v,NJ,41,Binary Search (3/5),Recursive implementation:,public int binarySearch (int arr , int value, int left, int right),int middle = (left + right) / 2;,if (value = arr middle ),return middle;,else if ( value arrmiddle & left arrmiddle & middle right ),return binarySearch (arr, value, middle + 1, right );,else,return -1; / Not found,42,Binary Search (4/5),Iterative implementation:,public int binarySearch (int arr , int value, int left, int right),while (left = right),int middle = (left + right) / 2;,if ( value = arr middle ),return middle;,else if ( value arrmiddle ) */,left = middle + 1;,return -1; / Not found,43,Binary Search (5/5),The average number of comparisons is roughly,log,2,n,The worst-case is,log,2,(,n,+ 1),rounded up to an integer (e.g. 2 for,n,= 3, 3 for,n,= 7, 4 for,n,= 15, etc.),44,java.util.Arrays,Provides,static,methods for dealing with arrays.,Works for arrays of numbers,Strings, (and “comparable”,Objects,).,Methods:,int pos = Arrays.,binarySearch,(arr, target);,Arrays.,sort,(arr);,Arrays.,sort,(arr, from, to);,Arrays.,fill,(arr,value,); / fills arr with a given value,Arrays.,fill,(arr, from, to,value,);,45,java.util.Random (1/2),Benchmarks,uses the,java.util.Random,class a more controlled way to generate random numbers.,Constructors:,If we set the same “seed,” we get,the same,“random” sequence.,Random generator = new Random( );,Random generator2 = new Random(seed);,Default “seed”:,System.currentTimeMillis,(),long seed;,46,java.util.Random (2/2),Methods:,int k = generator.,nextInt (),;,int k = generator.,nextInt (n),;,double x = generator.,nextDouble (),;,All 2,32,possible,int,values are produced with (approximately) equal probability,0,k,n,0,x,1,47,java.util.List,Interface,The,List,library interface describes a list of objects in abstract terms,In a list, objects are arranged in sequence,obj,0, obj,1, ., obj,n,-,1,In Java, a list holds,references,to objects,A list can contain duplicate objects,(both,obj1.equals(obj2,),and,obj1 = obj2,),48,List,Methods (a Subset),int,size,();,boolean,isEmpty,();,boolean,add,(Object obj);,void,add,(int i, Object obj);,Object,set,(int i, Object obj);,Object,get,(int i);,Object,remove,(int i);,boolean,contains,(Object obj);,int,indexOf,(Object obj);,returns,true,inserts,obj,as the,i,-th value;,i,must be from 0 to,size(),i,must be from 0 to,size(),-,1,use,equals,to compare objects,49,java.util.ArrayList (1/6),Implements,List,using an array,Keeps track of the list,capacity,(the length of the allocated array) and list,size,(the number of elements currently in the list),Cat,Hat,Bat,capacity,size,50,ArrayList (2/6),Automatically increases (doubles) the capacity when the list runs out of space; allocates a bigger array and copies all the values into it,get(i),and,set(i, obj),are efficient because an array provides random access to its elements,Throws,IndexOutOfBoundsException,when,i 0,or,i,size(),51,ArrayList (3/6),ArrayList,holds,objects,(of any type),If you need to put,int,s or,double,s into a list, use a standard Java array or convert them into,Integer,or,Double,objects,You have to remember what types of objects your put into the list and may need to cast a retrieved object back into its type,52,ArrayList (4/6),From Java API Docs:,JDK1.5:,ArrayList,(,Collection,c) Constructs a list containing the elements of the specified collection, in the order they are returned by the collections iterator.,53,ArrayList list = new ArrayList ();,list.add (new Integer(1);,list.add (new Integer(2);,list.add (new Integer(3);,int sum = 0;,for (int i = 0; i list.size(); i+),sum += (Integer) list.get(i) . intValue();,ArrayList (5/6),Example 1,Need a cast to,Integer,in order to call,intValue,54,ArrayList words = new ArrayList (4);,words,.,add (One);,words,.,add (Fish);,words,.,add (Two);,words,.,add (Fish);,int i = 0;,while (i words,.,size() ),if ( ”Fish,.,equals (words,.,get(i) ),words.remove(i);,else,i+;,ArrayList (6/6),Example 2,Shifts all the values after the,i,-th to the left and decrements the size,55,Generic type,56,Generic Programming,Define software components with type parameters,A sorting algorithm has the same structure, regardless of the types being sorted,Stack primitives have the same semantics, regardless of the,objects stored on the stack.,Compile time parameters,Implementation,Same code,used for different parameter values,Different code,generated for different values,C+ model,: template class,Java JDK1.5: type inference,57,More examples, ,謝謝捧場,蔡文能,58,