交通大学资讯工程学系

交通大學資訊工程學系ProgramminginJavaMoreexamples,…蔡文能交通大學資訊工程學系[e-mail]~tsaiwn/java/交通大學資訊工程學系蔡文能第2頁JavaMoreJavaExamplesAgendaComputingfactorialLoopmethodRecursivemethodOtherRecursiveexamplesComputingprimesSievemethodSortinganarraySelectionSortInsertionSortBubbleSortQuickSortMergeSortList,ArrayList,Generictype交通大學資訊工程學系蔡文能第3頁JavaMoreJavaExamplesComputingFactorial•Thefactorialofanintegeristheproductofthatnumberandallofthepositiveintegerssmallerthanit.-0!=1-1!=1...-5!=5*4*3*2*1=120-6!=6*5*4*3*2*1=720...-50!=30414093201713378043612608166064768844377641568960512000000000000BigDecimal,BigInteger交通大學資訊工程學系蔡文能第4頁JavaMoreJavaExamplesFactorial--IterationpublicclassFactorial{publicstaticlongfactorial(intn){longfact=1;for(inti=2;i=n;i++)//forLoopfact*=i;//shorthandforfact=fact*i;returnfact;}}publicclassComputingFactorial{publicstaticvoidmain(Stringarg[]){longa=Factorial.factorial(Integer.parseInt(arg[0]));System.out.println(Factorialof+arg[0]+=+a);}}Inseparatefiles交通大學資訊工程學系蔡文能第5頁JavaMoreJavaExamplesRecursion遞迴概念很久很久以前,這裡有一座山,山裡有一座廟,廟裡有個老和尚和小和尚,小和尚要老和尚說故事給他聽。老和尚就說:『很久很久以前,這裡有一座山,山裡友一座廟,廟裡有個老和尚和小和尚,小和尚要老和尚說故事給他聽。.....莊子與惠子游於濠梁之上。莊子曰：「鯈於出游從容，是魚之樂也。」惠子曰:『子非魚焉知魚之樂?』莊子曰:『子非我焉知我不知魚之樂?』惠子曰:『子非我焉知我不知你不知魚之樂?』莊子曰:『子非我焉知我不知你不知我知魚之樂?』惠子曰:『子非我焉知我不知你不知我不知你不知魚之樂?』莊子曰:『子非我焉知...!@#$%^&*?...交通大學資訊工程學系蔡文能第6頁JavaMoreJavaExamplesFactorial–Recursion,inJava/***Thisclassshowsarecursivemethodtocomputefactorials.Thismethod*callsitselfrepeatedlybasedontheformula:n!=n*(n-1)!**/publicclassFactorial2{publicstaticlongfactorial(intn){if(n==1)return1;elsereturnn*factorial(n-1);}}交通大學資訊工程學系蔡文能第7頁JavaMoreJavaExamplesNFactorial(Recursive版)longfactorial(intn){if(n0)return-factorial(-n);if(n==1||n==0)return1;returnn*factorial(n-1);}/*告訴我n-1階乘,我就給你n階乘*/#includestdio.hintmain(){printf(5!=%ld\n,factorial(5));}N階乘就是N乘以N-1階乘C語言版本交通大學資訊工程學系蔡文能第8頁JavaMoreJavaExamples歐幾里得的最大公約數輾轉相除法(recursive概念!)GCD(m,n)=GCD(n,m%n)但如果n是0則答案為mlonggcd(longm,longn){if(n==0)returnm;returngcd(n,m%n);}如何寫成non-recursiveversion?交通大學資訊工程學系蔡文能第9頁JavaMoreJavaExamples最大公約數non-recursive版longgcd(longm,longn){intr;/*remainder*/while(n!=0){r=m%n;m=n;n=r;}returnm;}交通大學資訊工程學系蔡文能第10頁JavaMoreJavaExamplesRecursive也可以很有趣(1/3)FibonacciSeries:(費氏數列)一開始有一對兔子小兔子隔一個月可以長大為成兔每對成兔每隔一個月可生出一對兔子假設兔子永遠不死,問第n個月時有幾對兔子？1,1,2,3,5,8,13,21,34,55,89,144,.fib(n)01234567891011=n交通大學資訊工程學系蔡文能第11頁JavaMoreJavaExamplesRecursive也可以很有趣(2/3)longfib(intn){if(n0)return0;if(n==1||n==0)return1;returnfib(n-1)+fib(n-2);}/*給我n我就告訴你第n個月時有幾對兔子*//*第n個月兔子數=第n-1個月兔子+第n-2個月兔子*//*但是,最開始兩個月例外!*/交通大學資訊工程學系蔡文能第12頁JavaMoreJavaExamplesRecursive也可以很有趣(3/3)FibonacciSeries(費氏數列):1,1,2,3,5,8,13,21,34,55,89,144,…34/55=55/89=89/144=0.618黃金分割比:)神奇的費氏數列:任何事物接近這些數字會有變化請看..可怕的巧合:!?三重魔力...民國34年台灣光復,民國89年變天國民黨從日本手上搶回台灣執政剛好55年!交通大學資訊工程學系蔡文能第13頁JavaMoreJavaExamples問題與思考(Recursion)寫出non-recursive版的Fibonaccifunction?考慮小兔子隔兩個月可以長大為成兔?考慮成兔的懷孕期是兩個月?其他Recursive問題Recursive版的binarysearchQuicksortHanoitowerproblem…交通大學資訊工程學系蔡文能第14頁JavaMoreJavaExamplesFactorial–cacheansinaTablepublicclassFactorial3{//createanarraytocachevalues0!Through20!staticlong[]table=newlong[21];static{ans[0]=1;}//factorialof0is1staticintlast=0;publicstaticlongfactorial(intn){if(n=last)returnans[n];longtmp=ans[last];intk=last;while(kn){tmp=(k+1)*tmp;/*(k+1)!*/if(last20){++last;ans[last]=tmp;}++k;}/*while*/returntmp;}}Cache唸作cash交通大學資訊工程學系蔡文能第15頁JavaMoreJavaExamplesComputingPrimes(1/3)•Findingthelargestprimenumbersmallerthanaspecifiedinteger:Inputintegerm,findpmsuchthatpisaprimeandifthereisprimep’pthenp’mustbelargerthanm.•Findingallprimenumbersthatsmallerthanaspecifiedinteger?1243576891214151618201011131719交通大學資訊工程學系蔡文能第16頁JavaMoreJavaExamplesComputingPrimes(2/3)•Algorithmmainidea:findprimesbyeliminatingmultiplesoftheformkj,wherejisaprimesmallerthansquare-root(m)andkisanintegersuchthatkjm.......prime2ijsquare-root(m)234.........234234222iiijjj交通大學資訊工程學系蔡文能第17頁JavaMoreJavaExamplesComputingPrimes(3/3)•Findingallprimenumbersthatsmallerthanaspecifiedinteger?1234567891011121314151617181920交通大學資訊工程學系蔡文能第18頁JavaMoreJavaExamplesExample:FindPrimes(1/2)Importjava.lang.*;publicclassSieve{publicstaticvoidmain(String[]args){intmax=100;//Assignadefaultvaluetry{max=Integer.parseInt(arg[0]);}catch(Exceptione){}//Silentlyignoreexceptions.//Createanarraythatspecifieswhethereachnumberisprimeornot.Boolean[]isprime=newboolean[max+1];//Assumethatallnumbersareprimes,untilprovenotherwise.for(inti=0;=max;i++)isprime[i]=true;//Weknowthatthat0and1arenotprime.Makeanoteofit.isprime[0]=isprime[1]=false;交通大學資訊工程學系蔡文能第19頁JavaMoreJavaExamplesExample:FindPrimes(2/2)//Tocomputeallprimeslessthanmax,weneedtoruleoutmultiplesofall//integerslessthanthesquarerootofmax.intn=(int)Math.ceil(Math.sqrt(max));for(inti=0;i=n;i++){if(isprime[i]){intk=2;for(intj=k*i;j=max;j=(k++)*i)isprime[j]=false;}}intlargest;for(largest=max;!sprime[largest];largest--);//emptyloopbodySystem.out.println(Thelargestprimelessthanorequalto+max+is+largest);}}交通大學資訊工程學系蔡文能第20頁JavaMoreJavaExamplesSort