交通大學資訊工程學系

ProgramminginJavaMoreexamples,…蔡文能交通大學資訊工程學系tsaiwn@.twAgendaComputingfactorialLoopmethodRecursivemethodOtherRecursiveexamplesComputingprimesSievemethodSortinganarraySelectionSortInsertionSortBubbleSortQuickSortMergeSortList,ArrayList,GenerictypeComputingFactorialThefactorialofanintegeristheproductofthatnumberandallofthepositiveintegerssmallerthanit. - 0!=1 - 1!=1... - 5!=5*4*3*2*1=120- 6!=6*5*4*3*2*1=720... - 50!=

30414093201713378043612608166064768844377641568960512000000000000BigDecimal,BigIntegerFactorial--Iteration publicclassFactorial{ publicstaticlongfactorial(intn){ longfact=1; for(inti=2;i<=n;i++) //forLoop fact*=i; //shorthandforfact=fact*i; returnfact; } } publicclassComputingFactorial{ publicstaticvoidmain(Stringarg[]){ longa=Factorial.factorial(Integer.parseInt(arg[0])); System.out.println("Factorialof"+arg[0]+"="+a); }}InseparatefilesRecursion遞迴概念很久很久以前,這裡有一座山,山裡有一座廟,廟裡有個老和尚和小和尚,小和尚要老和尚說故事給他聽。老和尚就說:『很久很久以前,這裡有一座山,山裡友一座廟,廟裡有個老和尚和小和尚,小和尚要老和尚說故事給他聽。.....莊子與惠子游於濠梁之上。莊子曰：「鯈於出游從容，是魚之樂也。」惠子曰:『子非魚焉知魚之樂?』莊子曰:『子非我焉知我不知魚之樂?』惠子曰:『子非我焉知我不知你不知魚之樂?』莊子曰:『子非我焉知我不知你不知我知魚之樂?』惠子曰:『子非我焉知我不知你不知我不知你不知魚之樂?』莊子曰:『子非我焉知...!@#$%^&*?...Factorial–Recursion,inJava

/** *Thisclassshowsarecursivemethodtocomputefactorials.Thismethod *callsitselfrepeatedlybasedontheformula:n!=n*(n-1)! **/ publicclassFactorial2{ publicstaticlongfactorial(intn){ if(n==1)return1;

elsereturnn*factorial(n-1); } }

NFactorial(Recursive版)longfactorial(intn){if(n<0)return-factorial(-n);if(n==1||n==0)return1;returnn*factorial(n-1);}/*告訴我n-1階乘,我就給你n階乘*/#include<stdio.h>intmain(){printf("5!=%ld\n",factorial(5));}N階乘就是N乘以N-1階乘C語言版本歐幾里得的最大公約數(shù)輾轉相除法(recursive概念!)GCD(m,n)=GCD(n,m%n) 但如果n是0則答案為mlonggcd(longm,longn){if(n==0)returnm;returngcd(n,m%n);}如何寫成non-recursiveversion?最大公約數(shù)non-recursive版longgcd(longm,longn){intr;/*remainder*/while(n!=0){r=m%n;m=n;n=r;}returnm;}Recursive也可以很有趣(1/3)FibonacciSeries:(費氏數(shù)列)一開始有一對兔子小兔子隔一個月可以長大為成兔每對成兔每隔一個月可生出一對兔子假設兔子永遠不死,問第n個月時有幾對兔子？1,1,2,3,5,8,13,21,34,55,89,144,.fib(n)01234567891011=n

Recursive也可以很有趣(2/3)longfib(intn){if(n<0)return0;if(n==1||n==0)return1;returnfib(n-1)+fib(n-2);}/*給我n我就告訴你第n個月時有幾對兔子*//*第n個月兔子數(shù)=第n-1個月兔子+第n-2個月兔子*//*但是,最開始兩個月例外!*/Recursive也可以很有趣(3/3)FibonacciSeries(費氏數(shù)列):1,1,2,3,5,8,13,21,34,55,89,144,…34/55=55/89=89/144=0.618黃金分割比:)神奇的費氏數(shù)列:任何事物接近這些數(shù)字會有變化

請看..可怕的

巧合:!?三重魔力...民國34年臺灣光復,民國89年變天

國民黨從日本手上搶回臺灣執(zhí)政剛好

55年!問題與思考(Recursion)寫出non-recursive版的Fibonaccifunction?考慮小兔子隔兩個月可以長大為成兔?考慮成兔的懷孕期是兩個月?其他Recursive問題Recursive版的binarysearchQuicksortHanoitowerproblem…Factorial–cacheansinaTable publicclassFactorial3{ //createanarraytocachevalues0!Through20! staticlong[]table=newlong[21]; static{ans[0]=1;}//factorialof0is1 staticintlast=0; publicstaticlongfactorial(intn){ if(n<=last)returnans[n];longtmp=ans[last];intk=last;while(k<n){tmp=(k+1)*tmp;/*(k+1)!*/if(last<20){++last;ans[last]=tmp;}++k; }/*while*/returntmp; }} Cache唸作cashComputingPrimes(1/3)Findingthelargestprimenumbersmallerthanaspecifiedinteger:

Inputintegerm,findp

msuchthatpisaprimeandifthereisprimep’>pthenp’mustbelargerthanm.Findingallprimenumbersthatsmallerthanaspecifiedinteger?

1243576891214151618201011131719ComputingPrimes(2/3)Algorithm mainidea:findprimesbyeliminatingmultiplesoftheformkj,wherejisaprimesmallerthansquare-root(m)andkisanintegersuchthatkj

m.......prime2ijsquare-root(m)

234.........234234222iiijjjComputingPrimes(3/3)Findingallprimenumbersthatsmallerthanaspecifiedinteger?

1234567891011121314151617181920Example:FindPrimes(1/2)Importjava.lang.*;publicclassSieve{ publicstaticvoidmain(String[]args){ intmax=100;//Assignadefaultvalue try{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;Example: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--);//emptyloopbody System.out.println("Thelargestprimelessthanorequalto"+max+"is" +largest);}} SortingNumbersSorting:

Inputnnumbers,sortthemsuchthatthenumbersareorderedincreasingly. 39165482107 12345678910

Sel濱ect碑ion瓦So軌rt無(1/少4)As企imp鞭le涂sor元tin妻ga油lgo漆rit曬hmPur掠pos責e:Inpu藥t:a勿nar轟rayAcont歪aini婆ngninte頸gers演.Outp的ut:派sort稈eda灣rray知.1.i:=2習;2.淋Fin寧dt割he靈lea沈st使ele虜men齒tafro米mA(i)t卷oA(n);3. I川faisl艷ess皇thanA(i-1),清exch裙angeA(i-1)揉anda;4.i:=喪i+1;存if勝(i<=繪n)托got蓋os驢tep殿(2濱).Sele指ctio圾nSo扣rt(返2/4)1st角st括ep:徒3摘9外1拳6捧5德4希8務2槽1加0羊72nd脫st賽ep:融1沉9塑3緒6冊5轎4鋒8躬2當10寫71摘2遵3和6枝5延4崗8源9原10息7….單..swapswapSel尖ect爐ion忠So張rt案(3/探4)Sor恐tin炕gp旁rog劫ram春:publ賺icc機lass文Sel照Sort籠{pub糧lic勾st往ati衛(wèi)cv非oid序so矛rt(濁dou定ble炎[]智nu淺ms)乘{for(傍int僑i=企0;獵i<決nums茶.len屋gth;局i++嗚){int準mi忠n=鳥i慶+1;for捧(int侍j=冠i+2猾;j糧<nu盟ms.l齊engt棗h;j的++)執(zhí){if(晶nums掙[j]儉<nu弦ms[m駱in])片min樸=j壁;}if(突nums繞[i]育>nu班ms[m折in])體{doub運let惠mp;tmp水=墻num氏s[i江];怕num緊s[i捎]=認nu還ms[棄min稈];搶num催s[m拾in]盞=政tmp璃;}}}}Sele把ctio畢nSo敲rt(踏4/4)Ins仇epar華ate置file蔬:publ旺icc鍵lass寺Sor申tNum店ber涌{publ寸ics伏tati期cvo概idm仗ain呼(Str尾ing[板]a爆rgs)民{doub嘴le[證]nu膠ms=撓new恩dou辜ble[買10];鴉//照Crea違tea兆nar銹ray時toh假old括numb亭ersfor除(in走ti寶=植0;英i<巡壽nu撐ms.偽len疑gth永;i歪++)錦//G逗ene也rat沫er豈and披om立num鵝ber帖snums通[i]基=Math你.ran泰dom(恢)*1悉00;SelS畝ort.逗sort用(num洞s);敬//So單rtt劣hemfor泊(int夸j=饑0;待j<姨nums鋼.len虎gth;頭j++逐)//崇Prin挽tth紡emo懇utSys報tem劣.ou配t.p揪rin歲tln石(nu寄ms才[j]紡);}}Mat波h.r焰and鉤om(嘗)裁:蠢se符en延ext瘦sl移ideUniformrandom[0,1)NormalDistributionRandomnumberInse乳rtio樓nSo檢rtpub放lic牲cl聽ass嘉In設sSo堡rt女{pub俘lic允st憤ati似cv岔oid仗so憑rt(教dou恢ble梯[]貧nu敘ms)紛{for虜(in削ti賭=逃1;蓋i偶<n熊ums端.le孕ngt首h;吸i++君)滑{doub濁let凈mp=潛num共s[i]鉛;含/*we基wan藝tt牢op瘋ut旁thi畝si腦np屈rop誰er彩pos互iti烏on*/k=鑒i泛–1撤;whil挽e((社k>=0秧)&&徐num詞s[k]臂>t般mp)慌{末/*smal浪ler狡than荒me*/光n遷ums[班k+1]故=姿nums配[k])臘;灶/*胡move良it以down吐*/--k;}num剩s[k孟+1]淋=杠tmp淹;/講*copy借it局into丘cor炮rect統(tǒng)po稀siti末on*/}}}Test濫the告Ins驕erti貴onS候ortIns縫epar卷ate棚file姑as類prev靜ious頃exa傅mple伐(Se據(jù)lect蜓ion爛sort費):publ馳icc叫l(wèi)ass酒Sor殿tNum虎ber儀{publ輔ics怠tati筐cvo禮idm斤ain肺(Str墳ing[漏]a吃rgs)出{doub世le[濱]nu聚ms=護new溜dou木ble[貿10];姻//鞏Crea硬tea播nar趙ray比toh宋old想numb惜ersfor偏(in擱ti系=雹0;身i<展nu揀ms.險len鳴gth澡;i微++)礙//G胳ene行rat壺er形and睡om圓num獎ber竊snums簽[i]礦=Math梅.ran孝dom(毀)*1敲00;Ins員Sor犯t.s邪ort珠(nu夾ms)脹; /酒/So召rt集the席mu瓣sin令gi就nse叔rti悲on享sor擇tfor渴(i額nt躍j=產0;防j怠<n品ums煌.le調ngt包h;鉗j++障)/伴/Pr帶int務th假em萌outSyst戴em.o畫ut.p刃rint圍ln(n頌ums箱[j]駐);}}Bubb仔l(wèi)eS逃ortpub據(jù)lic蘆cl寺ass啊Bu穗bSo載rt篇{publ太ics亂tati班cvo認ids狡ort(代doub練le[燭]nu名ms)梁{for(振int唱i=此num膛s.le縫ngth擁-2;花i>=米0;--i){int職fl句ag手=0典;群/考*Assu兩men奮oex項chan悔ge*/for(豈k=0;碗k<抖=i;術++k舒){椅/*臺walk初thr透ough謝all僚eve歪ryp撐ass倍*/if(斜num純s[k]告>n晃ums[僻k+1]駝)腳{謀/*inc帶orr賄ect汗or鄙der*/doub看let定mp=n干ums[既k];職num停s[k]烘=num津s[k+崗1];難nums赴[k+1護]=tm鉤p;++fl隸ag;}}if(f灣lag滾==0森)br辮eak;京/*疼non年eed戶tod裹one氏xtp瓦ass定*/}}}Alg菜ori煉thmqui現(xiàn)ck_揭sor輛t(ar碼rayA,from短,to朝)Inp勿ut:蒼fr啞om退-p飼oin瓣ter絞to相th惜es戒tar腹tin康gp盯osi渠tio光no灰fa霉rra活yAto-刊poi鎖nter堆to烏the悶end厘posi很tion饑of晃arra替yAOutp截ut:書sort磨eda償rray華:A’1.睜Cho牛ose圈an棒yo臨ne頃ele謀men影ta伶st席he伙piv灘ot;2. F績ind泛the債firs洋tel睡emen途ta=孔A[i]津larg露ert技han姨ore檢qual倡topiv射otfromA[fro蛾m]t輩oA[to六];3. F肉ind冊the淋firs飲tel部emen槳tb=哨A[j]箱sm釀all嫌er互tha墓no嫩re輛qua丈lt內opivo掏tfromA[to]李toA[fr介om]抗;4.住If屈i<翼j軋the描ne跟xch況ang扔eaandb;5. R帥epea注tst亦epf林rom牢2to展4u旬ntil覆j<誼=i憂;6.蛋If這fro集m<竊j敲the塊nr傘ecu云rsi援ve豈cal汪lquic摧k_so咬rt(A,from峽,j)坐;7. I棒fi始<to枝the凍nre彩curs慰ive服callquic輕k_so楚rt(A,i,黨to);Qui忠ck繭Sor呼t(孔1/6涂)Quic抹kso停rtmai老ni遺dea淘:1st我step椅: 3很1侮654毛8裳10惹72nd跟st渠ep:恢3誘2身158欲9亦10淺73rd方step飾:3哭2曠1撓456逮8顆9等10替7Choose5aspivotfromto2964Smal揚ler御than亞any帆int尺egerrigh估tto駕5gre欣ate粗rt網han附an刊yi鉛nte否gerleft排to壓5ijQuic超kSo怪rt(靜2/6)Quic虹kso鄉(xiāng)豐rt4th伐st摧ep:象2嚴4湖5殊6桌1能0 95th糞st箭ep:述1魄2擺3翠4幼5pivotfro態(tài)mto31875高6設7酷8還1靠0但96th青st稠ep:piv不otfro方mto7爐8予1帳0理97th磨st膛ep:9霞108th荒step時:Quic團kSo棍rt(兄3/6)publ碎icc啦lass尿Qui釘ckSo沸rter悔{publ蹦ics賄tati參cvo雙ids踐ort笨(int澤[]炎a,i爛ntf肺rom,仍int攀to)摔{if波((a布==冊nu悄ll)現(xiàn)||令(a納.le館ngt附h<身2)墳)r霸etu核rn;int彎i=帆from唉,j英=to霸;int批pi孩vot箭=程a[(柄fro弊m+束to盾)/2是];do溫{whi狼le暫((i學<罩to)善&&紡(a得[i]速<掘piv禾ot)朋)亮i++筐;whil喬e((昂j>限from居)&&居(a[雁j]>器=pi俊vot)債)j跨--;if(聲i<覺j){勇int額tmp裹=a[鵝i];汪a[i鐮]=歇a[j]宴;a[進j]=翅t(yī)mp依;}i++;睬j--逗;}wh誘ile篇(i炮<=癢j)吐;if目(fr桌om缸<j炒)s肢ort江(a,業(yè)fr裙om,航j)牽;if(槳i<暗to)交sort諸(a,齊i,t侄o);塌}}Quic獎kSo葡rt(敬4/6)143,4泊,6,疲1,福10,攜9,5嬌,20,19續(xù),141,1新2,2替,15圾,21紡,13由,18直,17獨,8,1腹6,3,4踢,6,威1,鍵10,教9,5后,8,19,1,1販2,2誓,15屬,21艷,13,18疫,17及,,16,3,4贏,6,綁1,腔10,鎖9,5六,8,13,1,1嬌2,2仇,15,21贏,19,1欲8,莊17,中20洪,1鳥6,ij3,4溜,6,糾1,章10,游9,5滔,8,鍛13,1,窗12,倉2ijQui態(tài)ck駁Sor劑t(殿5/6請)3,殲4,刊6,肉1,視10,啦9,袖5,遠20余,1深9,14,12,夫2,1唐5,2陰1,1膊3,1扔8,1貌7,8大,16知,1ji20,14ij3,土4,孩6,閉1,軌10,新9,碧5,付8,沃13,1,受12,密2,14,備21梅,1峽9,較18,主17浮,2便0,俊16,1514publ架icc址lass蘋BQS挎orte堵r{publ制ics燙tati左cvo闖ids翅ort勉(int程[]臥a,i耐ntf娃rom,侵int再to)謙{if(周(a=問=nu沉ll)邊||(甲a.le籮ngth炎<2留)||系fro捐m>=逢to)賽ret估urn;int提k熟=(撞fro錢m+傳to英)/2電;i除nt報tmp富=a慨[to速];奴a[災to]同=忍a[k賄];摸a[k綱]=循tm劉p;int陶pi耕vot遣=偏a[t悉o];輪i耍nt邊i=征fr貍om,j=科to-1咬;whil高e(i浩<j鋼){whi營le師((i哨<府j)延&&福(a[迎i]錄<p慮ivo變t))趙i涂++;whil竊e((君i<逆j)&處&(a銜[j]婆>=p筋ivot暴))辯j--;if劫(i擴<j男){朝tm麗p=疑a[i國];躺a[志i]劣=a下[j]使;a腸[j]迅=睡tmp失;}};tmp克=a到[i]盯;a偵[i過]=恨a[掃to]缸;a培[to犁]=飯tm溪p;if(夾from踏<i作-1)奶sort系(a,村from樂,i-壯1);if(雄i<教to)略sort旱(a,蛋i+1,皆to)紀;

}}Quic菌kSo攪rt(駛6/6)Merg傷ing創(chuàng)mean探sth儲eco墊mbin暑atio嚷nof彼two謀or潮more窮ord避ered退seq遵uenc嘴ein撫t(yī)oas排ing挺le施seq爪uen棍ce.睜Fo祖re艱xam幫ple紅,c睡an夏mer寄ge邀two抖se爽que默nce蠅s:猛503痕,7峽03,趟76搏5and屑087,苗512馬,67生7to敗obt丑ain右ase撈quen芽ce:攪087,他503敢,51寧2,6關77,棉703,芹765夢.Asi孩mple祥way隔to丈acco腸mpli菌sht嘴his申ist臨oco辱mpar葬eth煎etw鍋osm嶄alle鍬sti并tems糖,outp錘utt計hes警mall色est,饅and肢the造nre倦peat項the積sam甲epr張oces樸s.503井703盜765087書51何2 6吊77087503饑70彩3 7黃65512正67若7087嫩503703分76科5512寺677Merg忙eSo盆rt(譯1/3)Alg糞ori顛thmMer濫ge(s1,梯s2)Inp擇ut:框tw濁os傘equ慘enc沾es:炕s1校-撲x1x2涉...赤xmand剝s2濟-寄y1y2支...騙ynOut治put故:a荒so俗rte墳ds稻equ系enc脖e:懶z1z口2.吩..鹽zm+n.1.[i鞋niti賺aliz舍e]i:=則1,j:=1異,k:=1侍;2.[殲fin女ds真mal籍ler退] i寫fxiyjgot著os眾tep咽3,型ot哪her諒wis尺eg鑄oto辱st接ep握5;3.[o矮utpu覽txi]zk.:=xi,k:=k+1,i:=i+1.攜Ifim,g竄oto播st梨ep徒2;4.[辨tra疑nsm絮ityj.戀..茶yn]zk,...,喇zm+n:=旦yj,...,停yn.T紋erm扮ina饑te近the孕al煩gor晝ith爬m(xù);5.[o園utpu身tyj]zk.:=成yj,k:=k+1,j:=j+1.山Ifjn,go膜tos鹿tep威2;6.[t突rans槳mitxi容...啄肺xm]zk,...,鑒zm+n:=xi,...,緊xm.T柜erm氣ina摔te獨the外al趟gor得ith蕩m;Merg歐eSo潮rt(腔2/3)Algo翻rith菌mMerg郊e-so詳rtin奪g(s)Inp唉ut:微a佩seq對uen悶ces本s劈燕=<兼x1,...,誤xm>Out船put垮:a耍so淡rte受ds撞equ巷enc勤e.1.侵If浩|s|戲=嶺1,板the爆nr援etu彈rn肯s;2.k:=m/2;3.流s1壘:=脆Mer光ge-夜sor奏tin暴g(x1,...,榮xk);4.s它2:=畜Mer寸ge-s饑orti姨ng(xk+1,...雜,xm);5.r擺etur塑n(Merg組e(s1,拳s2)鐘);Merg悠eSo痛rt(章3/3)Tim漁ec店omp致lex頌ity重of穗Me曬rge晉sor謀tTake妹sro用ughl派yn·log2ncom尚par賊iso么ns.Wit隔hou葉tt眼he絨sho伯rtc院ut,否th貝ere稀is混no魄be弦st置or末wor溫st甜cas受e.Wit臥ht譯he砍opt簡ion既al丑sho材rtc似ut,恰th堪eb似est踢ca富se癥is但whe楊nt殖he隙arr宣ay鄉(xiāng)豐is科alr服ead序ys那ort爭ed:鐘ta梢kes餓on互ly(n-1)com日par梨iso旦ns.Bina墨ryS襲earc柴h(1辟/5)Wor悟ks損for頃an瓣ar匹ray封of撇nu謊mbe鍋rs駕or露obj般ect嶄st概hat材ca沙nb建ec開omp襪are漸da振nd銹are尼ar倆ran縱ged舒in套as韻cen濁din鉆g(杯or耍des群cen遵din獎g)胞ord六er.Ave梢ryf慎ast帝meth馬od:息only銅20犬comp郊aris延ons胡are退need稅edf嗎ora傷nar始ray翼of1鳴,000牙,000犯ele槳ment多s;(窩30c判ompa活riso涂nsc牽anh鋤andl徒e1,或000,善000,陳000擺elem事ents熟;et葡c.)Bina須ryS伯earc滑h(2克/5)Mai臨ni榜dea劈燕:“熄div歌ide徑an釀dc婦onq獨uer藥”:com突par鳥et弟he嘉tar釀get芝va套lue囑to失th伸em翁idd姨le制ele壇men延t;ife克qual毯,al軟lse殿tif保sma軟lle圍r,惑app省ly財bin箏ary窗se啞arc寺ht榆ot隸he葛lef斬th雜alf借;ifl翅arge繳r,a植pply宋bin賴ary爺sear壤cht陶oth退eri麻ght古half臘....薯MI涉MN衡MO床MS交MT熟NC哈ND耽..坐....弱MI石MN市MO耐MS卡MT請NC恐ND柏..鋸.NJvNJBina桃ryS撓earc惠h(3浸/5)Rec籌urs定ive末im釋ple添men周tat略ion耀:pub趣lic歷in限tb稀ina牢ryS灰ear震ch睬(in廊ta躬rr狂[]等,i毫nt腦val宗ue,枕in受tl臟eft盞,i鳳nt止rig斑ht){int辣mi是ddl嚼e=負(l洪eft傍+祥rig祖ht)勺/茶2;if汗(va匪lue喚==杏ar怕r[樓mid求dle海])ret滲urn菜mi套ddl觀e;els熔ei值f(捉va茶lue役<垮arr拾[mi界ddl港e]鐘&&籃lef趣t<滔mi劣ddl餓e)ret悶urn洽bi襖nar陰ySe付arc伐h(立arr窩,v臥alu叛e,槳lef稍t,結mid奸dle-1);els椅ei距f(手va斬lue渾>謊arr獸[mi高ddl乘e]磨&&辨m森idd逝le貸<r階igh宵t)retu是rnb極inar種ySea哪rch福(arr訂,va襪lue,棕mid搖dle摧+1,任rig打ht)金;elseretu捎rn-川1;戚//N瞧otf擊ound}Bin寇ary艷Se召arc率h(蹄4/5棍)Ite庫rat巾ive齒im市ple摘men液tat嫩ion役:publ史ici職ntb谷inar亮ySea擊rch豬(int聾arr傲[]獅,in攻tva皆lue,糠int堡lef貼t,i公ntr月ight億){whi慎le主(le鉆ft恒<=俯rig律ht){int剩midd蘇le=猾(le甘ft+唉rig植ht)眼/2;if崗(v膽alu獨e=袋=a朗rr沉[mi鑒ddl蛇e]軋)ret途urn花mi鐮ddl年e;els堡ei舊f(罰va密lue左<霜arr受[mi址ddl固e]望)rig艦ht賠=m紅idd福le-1;els限e/捏*i避f(恢va焦lue栽>住arr隆[mi過ddl萬e]咱)羞*/left冠=m鼻iddl貍e+藍1;}ret醒urn輔-1外;帆//冤Not弱fo嗚und}Bin聾ary氧Se倚arc強h(術5/5依)The扒aver造age色numb送ero上fco撈mpar蜜ison砍sis訪rou祥ghlylog2nThe本wors牛t-ca隔sei符slog2(n+1)roun殊ded孫upt染oan企int教eger急(e.媽g.2榜forn=3向,3罷fo賣rn=7,本4f槍orn=1可5,檢etc痛.)jav死a.u氏til針.Ar即ray待sProv鳴idesstat珠icmeth體ods姐for定deal喪ing置with澆arr已ays.Work麻sfo摸rar攀rays局of載numb拿ers,Str梁ing瘡s,(昂and籌“c妄omp分ara破ble這”O(jiān)bje前cts).Met掉hod茄s:int恐po考s=掉Ar啟ray蠢s.bina問rySe掃arch(ar廟r,熔ta贈rge蛇t);Arra凳ys.sor鴉t(arr韻);Arra科ys.sort(arr穗,fr年om,唱to);Arra蹈ys.fil專l(ar麥r,val梢ue);比//袍fil笨ls彎arr景wi頃th訓ag茶ive壁nv濟alu辱eArra妻ys.fil護l(arr療,fr蜓om,病to,val泳ue);jav吉a.u朱til價.Ra沾ndo揚m(瞎1/2留)Benc沃hmar應ksuse流st暑hejav處a.u儀til貴.Ra政ndo蠢m(xù)cla街ss意—a籍mo科re玻con凈tro明lle傲dw墨ay拴to蓄gen淺era璃te賤ran付dom喜nu兵mbe氣rs.Cons狼truc沙tors曉:If販we粱set節(jié)th蘆es宜ame層“s餡eed證,”容we聚getthe眼same“ran調dom”色seq余uenc絹e.Ran馬dom弊ge微ner療ato頓r=面ne連wR織and侮om(招);Rand明omg響ener代ator刷2=嶺new晚Rand致om(s柴eed)岔;Defa程ult街“see浸d”:Sys植tem旁.cu框rre拜ntT怨ime助Mil匹lis()long滴see星d;java滿.uti姿l.Ra辨ndom田(2/鋒2)Meth濕ods:int硬k=嗚gene枯rato塊r.next全Int莫();int班k=咽gene質rato女r.next骨Int瘡(n);dou找ble駕x輝=g跑ene蜓rat友or.next勢Doub橫le(儲);All紹232poss融ibleintvalu怖esa振rep遍rodu建ced打with堅(ap斃prox欺imat胸ely)矩equ悲alp重roba晶bili辣ty0k<n0x<1jav碼a.u娛til記.Li機stInt待erf慈aceTheListlibr院ary板inte濱rfac含ede沒scri柴bes侍ali側sto毅fob擔ject居sin桑abs闊trac低tte方rmsIna幻玉lis打t,o度bjec霉tsa鍛rea搬rran煉ged速ins詠eque舒nceobj0,ob搞j1,..暖.,o替bjn-1InJ斷ava,突al見ist領hold憶srefe喂renc寬estoo膀bjec煌tsAl糖ist捐ca海nc悔ont壯ain感du扁pli葡cat凳eo傾bje陜cts(bo趁thobj1脂.equ促als(扯obj2)andobj慮1=僚=o坊bj2)ListMeth內ods步(aS驅ubse球t)intsize();boo下lea耍nisE月mpt蘇y();boo師lea辣nadd(Obj輩ect緒obj)減;voi兇dadd(in拆ti丹,O預bje販ct風obj優(yōu));Obj堅ectset(in噴ti河,O蜘bje掠ct府obj婆);Obje懲ctget(in丘ti提);Obje趙ctrem纖ove(int講i);boo頑lea紀ncont參ains(Obj負ect始obj)森;intind碰exO注f(Obj犁ect拿obj)信;ret鋼urn然strueinse全rtsobjast拆hei-th識va塘lue閘;imus救tb繩ef踢rom舉0色tosize鞭()imust準be治from悟0t牲osiz如e()-1useequa的lsto份com駁par宿eo產bje謊ctsjava滾.uti算l.Ar陷rayL壤ist挖(1/6舒)Impl垮emen姻tsLis侮tusin漁gan送arr臟ayKeep個str毛ack全oft作hel歲istcapa診city(th炕el瓜eng掩th納of恭the近al時loc戚ate扯da剪rra顏y)芬and知li科stsize(th葉en固umb捷er強of轉ele屬men炒ts勺cur虹ren鴨tly源in簽th惰el負ist透)"Cat添""Hat決""Ba侵t"capa懇citysizeArra馳yLis癥t(2像/6)Aut墓oma孕tic柜all析yi移ncr繡eas聰es鄭(do獄ubl技es)煤th休ec巨apa雷cit誼yw莫hen震th功el轉ist壞ru威ns米out續(xù)of身sp算ace沾;a取llo鞏cat頓es閑ab點igg變er蘋arr揚ay額and盾co遺pie烏sa禍ll懶the嗽va眾lue便si叔nto歐itget鬧(i)andset鴨(i,益ob梢j)are趴effi越cien遭tbe背caus注ean鋤arr山ayp享rovi謎des蠶rand校oma悅cces床sto濤its浙ele勢ment芽sThr雷owsInd扮exO安utO悟fBo垮und坡sEx懲cep絮tio須nwhe旦ni<燥0orisiz咽e()Arr錯ayL它ist血(3啄/6)Arr冶ayL忠isthol胳dsobje透cts(of邪an突yt條ype雙)If左you箱ne炮ed帖to氧putintsordoub軟lesin啊toa晴lis雄t,u拜sea雞sta銅ndar鬧dJa適vaa材rray難or戚conv漆ert蝦them龜int禁oInte韻gerorDou初bleobje丸ctsYou顫have夫to伶reme出mber接wha原tty舞pes炸ofo誰bjec短tsy穴our稻put胖into漢the斥lis廣tan穴dma被yne仿edt嚷oca糾sta宰