計(jì)科班算法設(shè)計(jì)與分析

算法：是若干條指令組成的有窮序列算法的三個(gè)要素1)數(shù)據(jù):運(yùn)算序列中作為運(yùn)算對(duì)象和結(jié)果的數(shù)據(jù).2)運(yùn)算::運(yùn)算算序列中中的各種種運(yùn)算::賦值,,算術(shù)和和邏輯運(yùn)運(yùn)算3)控制和和轉(zhuǎn)移::運(yùn)算算序列中中的控制制和轉(zhuǎn)移移.四條性質(zhì)：：輸入、輸輸出、確確定性、有有窮性四條性質(zhì)：：1)輸入：：有零個(gè)個(gè)或多個(gè)個(gè)由外部部提供的的量作為為算法的的輸入2)輸出：：算法產(chǎn)產(chǎn)生至少少一個(gè)量量作為輸輸出3)確定性性：組成成算法的的每條指指令是清清晰的，無無歧義的的。4)有限性性：算法法中每條條指令的的執(zhí)行次次數(shù)是有有限的，執(zhí)執(zhí)行每條條指令的的時(shí)間也也是有限限的。程序：是算算法用某某種程序序設(shè)計(jì)語語言的具具體實(shí)現(xiàn)現(xiàn)算法的復(fù)雜雜性：算算法運(yùn)行行所需要要的計(jì)算算機(jī)資源源的量時(shí)間復(fù)雜性性（算法法運(yùn)行所所需要的的計(jì)算機(jī)機(jī)時(shí)間資資源的量量）空間復(fù)雜性性（算法法運(yùn)行所所需空間間資源的的量）時(shí)間復(fù)雜性性的三種種情況：：最壞情情況（可可操作性性最好且且最優(yōu)實(shí)實(shí)際價(jià)值值）、最最好情況況、平均均情況分治法的設(shè)設(shè)計(jì)思想想：將一一個(gè)難以以直接解解決的大大問題，分分割成一一些規(guī)模模較小的的相同問問題，以以便各個(gè)個(gè)擊破，分分而治之之。遞歸：直接接或間接接地調(diào)用用自身的的算法。遞歸函數(shù)：用函數(shù)自身給出定義的函數(shù)。階乘函數(shù)可可遞歸定定義為：：遞歸定義式式：intffacttoriial((inttn)){ if((n===00)rretuurn1; retuurnn**faactooriaal(nn-1));}Fibonnaccci數(shù)列列：無窮窮數(shù)列11，1，22，3，55，8，113，221，334，55，…，可遞遞歸定義義為遞歸定義式式：intffiboonaccci((inttn)){ if((n<<=11)reeturrn11; retuurnfibbonaaccii(n--1)++fibbonaaccii(n--2);;}Hanoii塔定義義式：voidhannoi((inttn,,inntaa,iintb,inttc)){if(nn<0){hanoii(nn-1,a,c,b);;move(a,,b));hanoii(nn-1,c,b,a);;}}二分搜索算算法的基基本思想想：是將將n個(gè)過過元素分分成大致致相同的的兩半，取取a[nn/2]]與x作作比較。合并排序：：用分治治法策略略實(shí)現(xiàn)對(duì)對(duì)n個(gè)元元素進(jìn)行行排序的的算法?；舅枷胧牵簩⒋判蛟胤殖纱笮〈笾孪嗤膬蓚€(gè)子集，分別對(duì)兩個(gè)子集合進(jìn)行排序，最終將排好序的子集合并成所要求的排好序的集合。動(dòng)態(tài)規(guī)劃算算法基本本思想（自底向上、全局最優(yōu)）：講帶求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不不同的是是：適用用于動(dòng)態(tài)態(tài)規(guī)劃法法求解的的問題，經(jīng)經(jīng)分解得得到的子子問題往往往不是是互相獨(dú)獨(dú)立的。最優(yōu)子結(jié)構(gòu)構(gòu)性質(zhì)（問問題的最最優(yōu)解包包含了其其子問題題的最優(yōu)優(yōu)解）子問題重疊疊性質(zhì)（在在用遞歸歸算法自自頂向下下求解此此問題時(shí)時(shí)，每次次產(chǎn)生的的子問題題并不總總是新問問題，有有些子問問題被反反復(fù)計(jì)算算多次）備忘錄方法法（動(dòng)態(tài)規(guī)規(guī)劃算法法變形）：：用表格格保存已已解決的的子問題題的答案案，在下下次需要要解此子子問題時(shí)時(shí)，只要要簡(jiǎn)單地地查看該該子問題題的解答答，而不不必重新新計(jì)算。最優(yōu)二叉搜搜索樹性性質(zhì)：存存儲(chǔ)于每每個(gè)結(jié)點(diǎn)點(diǎn)中的元元素x大大于其左左子樹中中任一結(jié)結(jié)點(diǎn)所存存儲(chǔ)的元元素，小小于其右右子樹中中任一結(jié)結(jié)點(diǎn)所存存儲(chǔ)的元元素。貪心算法（自頂向下、局部最優(yōu)）：通過一系列的選擇來得到問題的解。它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下局部最好選擇。貪心選擇性性質(zhì)（所所求問題題的整體體最優(yōu)解解可以通通過一系系列局部部最優(yōu)的的選擇來來達(dá)到，是是貪心算算法與動(dòng)動(dòng)態(tài)規(guī)劃劃算法的的主要區(qū)區(qū)別）最有子結(jié)構(gòu)構(gòu)性質(zhì)（一一個(gè)問題題的最優(yōu)優(yōu)解包含含其子問問題的最最優(yōu)解）哈夫曼編碼碼：是廣廣泛用于于數(shù)據(jù)文文件壓縮縮的十分分有效的的編碼方方法。最短路徑：：給定一一個(gè)，其其中每條條邊的權(quán)權(quán)是非負(fù)負(fù)實(shí)數(shù)。一個(gè)帶權(quán)有向圖一個(gè)帶權(quán)有向圖11111100601030105020最小生成樹樹性質(zhì)：：用貪心心算法設(shè)設(shè)計(jì)策略略可以設(shè)設(shè)計(jì)出構(gòu)構(gòu)造最小小生成樹樹的有效效算法?；厮莘ǎっと伺郎缴健⒚詫m宮問題、nn后問題題）：在解解問題的的解空間間樹中，按按深度優(yōu)優(yōu)先策略略，從根根節(jié)點(diǎn)出出發(fā)搜索索解空間間樹?；舅枷耄海簭拈_始始結(jié)點(diǎn)（根根節(jié)點(diǎn)）出出發(fā)，以以深度有有限方式式搜索整整個(gè)解空空間。分枝限界法法基本思思想：以以廣度優(yōu)優(yōu)先或以以最小耗耗費(fèi)（最最大效益益）優(yōu)先先的方式式搜索問問題的解解空間樹樹。分枝限界法法求解目目標(biāo)是找找出滿足足約束條條件的一一個(gè)解，或或是滿足足約束條條件的解解中找出出使某一一目標(biāo)函函數(shù)值達(dá)達(dá)到極大大或極小小的解，即即在某種種意義下下的最優(yōu)優(yōu)解?；厮莘ㄇ蠼饨饽繕?biāo)是是找出解解空間中中滿足約約束條件件的所有有解。批處理作業(yè)業(yè)調(diào)度：：給定nn個(gè)作業(yè)業(yè)的集合合J==(JJ1,JJ2,……,Jnn)。每每個(gè)作業(yè)業(yè)Ji都都有兩項(xiàng)項(xiàng)任務(wù)分分別在兩兩臺(tái)機(jī)器器上完成成。每個(gè)個(gè)作業(yè)必必須先由由機(jī)器11處理，然然后再由由機(jī)器22處理。分支限界法法與回溯溯法：分支限限界法與與回溯法法的求解解目標(biāo)不不同，回回溯法的的求解目目標(biāo)是找找出求解解空間中中滿足約約束條件件的所有有解，而而分支限限界法求求解的目目標(biāo)則是是找出滿滿足約束束條件的的一個(gè)解解?；厮菟莘ㄒ陨钌疃葍?yōu)先先的方式式搜索解解空間，而而分支限限界法則則以廣度度優(yōu)先或或最小耗耗費(fèi)優(yōu)先先的方式式搜索空空間。隨機(jī)化算法法基本特特征：對(duì)對(duì)所求解解問題的的同一實(shí)實(shí)例用同同一隨機(jī)機(jī)化算法法求解兩兩次可能能得到完完全不同同的效果果。隨機(jī)數(shù)在隨隨機(jī)化算算法設(shè)計(jì)計(jì)中扮演演著十分分重要的的角色。符號(hào)三角問問題：#inclludee<sstdiio.hh>#defiineM113#defiineN113Triannglee(chharA[MM][NN]){ intti,,j; prinntf(("\nn輸入入第1行行的數(shù)據(jù)據(jù)：")); for(j==0;jj<N;;j+++) //輸入第第1行的的數(shù)據(jù) scaanf(("%cc",&&A[00][jj]);; for(i==1;ii<M;;i+++) //A數(shù)組組的第22行以下下清空 forr(jj=0;;j<NN;j+++) A[[i][[j]=='''; i=0;; j=00; whille(ii<M--1) { whhilee(j<<N-11) { iif((A[ii][jj]===A[ii][jj+2]])///如如果上一一行的相相鄰兩符符號(hào)相同同 AA[i++1][[j+11]=''+';; //則下一一行的符符號(hào)為''+' ellse AA[i++1][[j+11]=''-';; //否則下下一行的的符號(hào)為為'-'' j==j+22; } i+++; j=ii; }}voidmaiin()){ intti,,j; charrA[[M][[N];; Triaanglle(AA); for(i==0;ii<M//2+11;i+++) { foor((j=00;j<<N-ii;j+++) prrinttf(""%4cc",AA[i]][j]]); priintff("\\n\nn");; }}

矩陣相乘乘：//兩矩矩陣相乘乘#inclludee<sstdiio.hh>#defiineM22#defiineN33MatriixMuultiiplyy(inntAA[M]][N]],inntBB[N]][M]],inntCC[M]][M]]){ intti,,j,kk,suum; for(i==0;ii<M;;i+++) forr(jj=0;;j<MM;j+++) { summ=0;; foor((k=00;k<<N;kk++)) ssum==summ+A[[i][[k]**B[kk][jj]; C[[i][[j]==summ; }}voidmaiin()){ inttA[[M][[N],,B[NN][MM],CC[M]][M]],i,,j,kk; for(i==0;ii<M;;i+++) //輸入66個(gè)整數(shù)數(shù)給矩陣陣A forr(jj=0;;j<NN;j+++) sccanff("%%d",,&A[[i][[j])); for(i==0;ii<N;;i+++) //輸入66個(gè)整數(shù)數(shù)給矩陣陣B forr(jj=0;;j<MM;j+++) sccanff("%%d",,&B[[i][[j])); MatrrixMMulttiplly(AA,BB,CC); prinntf(("\nn兩矩矩陣相乘乘的的結(jié)結(jié)果如下下：\nn\n""); for(i==0;ii<M;;i+++) { foor((j=00;j<<M;jj++)) prrinttf(""%4dd",CC[i]][j]]); priintff("\\n\nn");; }}二分搜索算算法：是是用分支支策略的的典型例例子，需需要先排排序。#inccludde<<stddio..h>#deffineeMAAXLEEN111typeddefstrructt{ inttkeey;} typpe_eelemmentt;intbbinaary__seaarchh(tyype__eleemenntrr[],,inttkeey){ inttleeft==1,rrighht=MMAXLLEN,,midddlee; whille((lefft<==rigght)) { miiddlle=((lefft+rrighht)//2; if(r[[midddlee].kkey===keey) reeturrnmmidddle;; if(r[[midddlee].kkey>>keyy) riightt=miiddlle-11;//在右半半部繼續(xù)續(xù)查找 elsse leeft==midddlee+1;;//在右半部繼繼續(xù)查找找 } retuurn-1;;}voidmaiin()){ intti,,j,kkey;; typee_ellemeenttemmp,rr[MAAXLEEN+11]={{0,99,133,155,300,377,555,600,755,800,900,922}; for(i==1;ii<MAAXLEEN;ii++)) //對(duì)數(shù)組組進(jìn)行排排序 forr(jj=i++1;jj<=MMAXLLEN;;j+++) iff(rr[i]].keey>rr[j]].keey) { temmp=rr[i]]; rr[i]]=r[[j];; rr[j]]=teemp;; } for(i==1;ii<=MMAXLLEN;;i+++) priintff("%%3d"",r[[i]..keyy); prinntf(("\nn\n輸入欲欲查找的的數(shù)據(jù)：：");; scannf(""%d"",&kkey)); i=biinarry_ssearrch((r,kkey)); if((i===-1)) priintff("\\n已已經(jīng)查找找完，尚尚未找到到該數(shù)??！\n\\n")); elsee priintff("\\n\nn已找找到，其其序號(hào)是是：%dd\nn\n"",i));}

快速排序序：#inclludee<sstdiio.hh>#inclludee<sstdllib..h>#defiineMAXXLENN100intpparttitiion((inttr[[],iints,iintt) { intti,,j,rrp; i=s;; j=t;; //一一趟快速速排序，將將基準(zhǔn)記記錄移到到正確位位置 rp=rr[s]]; //基基準(zhǔn)記錄錄暫存rp中 whille(ii<j)) //從從序列的的兩端交交替向中中間掃描描 { whhilee(i<<j&&&rr[j]]>=rrp) //掃掃描比基基準(zhǔn)記錄錄小的位位置 j---; r[ii]=rr[j]]; //將將比基準(zhǔn)準(zhǔn)記錄小小的數(shù)據(jù)據(jù)移到低低端 whiile((i<jj&&&r[[i]<<=rpp) //掃掃描比基基準(zhǔn)記錄錄大的位位置 i+++; r[jj]=rr[i]]; //將將比基準(zhǔn)準(zhǔn)記錄大大的數(shù)據(jù)據(jù)移到高高端 } r[i]]=rpp; //基基準(zhǔn)記錄錄到位 retuurni;}voidQuiickSSortt(inntrr[],,intts,,inttt)) //快快速排序序遞歸算算法{ inttk;; if((s<tt) //長(zhǎng)長(zhǎng)度達(dá)于于1 { k==parrtittionn(r,,s,tt); //調(diào)調(diào)用一趟趟快速排排序算法法將r[[s]...r[[t]一一分為二二 QuiickSSortt(r,,s,kk-1)); //對(duì)對(duì)低端子子序列遞遞歸排序序，k是是支點(diǎn)位位置 QuiickSSortt(r,,k+11,t)); //對(duì)對(duì)高端子子序列遞遞歸排序序 }}voidmaiin()){ intti;; intr[MMAXLLEN]]; prinntf(("\nn請(qǐng)輸輸入%dd個(gè)整數(shù)數(shù)：",,MAXXLENN); for(i==0;ii<MAAXLEEN;ii++)) scaanf(("%dd",&&r[ii]);; QuicckSoort((r,00,MAAXLEEN-11); prinntf(("\nn快速速排序的的結(jié)果如如下：\\n\nn");; for((i=00;i<<MAXXLENN;i+++) priintff("%%3d"",r[[i])); prinntf(("\nn\n"");}循環(huán)賽日程程表：#inclludee<sstdiio.hh>#defiineMAXXLENN8voidmaiin()){ intti,,j; intx[MMAXLLEN++1][[MAXXLENN+1]]={00}; //數(shù)組清清零 for(i==1;ii<=MMAXLLEN;;i+++) ///產(chǎn)產(chǎn)生第11列數(shù)據(jù)據(jù) x[ii][11]=ii; for(i==1;ii<=MMAXLLEN;;i+++) ///產(chǎn)產(chǎn)生第22列數(shù)據(jù)據(jù) if(i%22!==0) x[[i][[2]==x[ii+1]][1]]; ///產(chǎn)產(chǎn)生奇數(shù)數(shù)行的第第2列的的數(shù)據(jù) elsse x[[i][[2]==x[ii-1]][1]]; ///產(chǎn)產(chǎn)生偶數(shù)數(shù)行的第第2列的的數(shù)據(jù) for((i=11;i<<=8;;i+++) ///產(chǎn)產(chǎn)生左半半部表中中的右半半部分 forr(jj=1;;j<==2;jj++)) { iif((i===1|||ii==22|||i===5||i===6) xx[i++2][[j+22]=xx[i]][j]]; ellse xx[i--2][[j+22]=xx[i]][j]]; } for((i=11;i<<=8;;i+++) //產(chǎn)生生右半部部表的數(shù)數(shù)據(jù) forr(jj=1;;j<==4;jj++)) { if((i<==4) xx[i++4][[j+44]=xx[i]][j]]; ellse xx[i--4][[j+44]=xx[i]][j]]; } prinntf(("\nn循環(huán)環(huán)賽日程程表如下下：\nn\n""); for(i==1;ii<=MMAXLLEN;;i+++) ///輸出該該表 { foor((j=11;j<<=MAAXLEEN;jj++)) prrinttf(""%6dd",xx[i]][j]]); priintff("\\n\nn");; }}

最大公約數(shù)數(shù)：intggcd((inttm,,inttn)){ intr; whille(nn!=00){ r==m%nn; m==n;; n==r;; } retuurnm;}最小公倍數(shù)數(shù)：intggcm((inttm,,inttn)){ intti,,k,ff; if((m<nn)///交交換m與與n { i==m; m=nn; n=ii; } f=1;; if((m%nn==00) { f==f*mm; retturnnf;; } i=2;; k=(iint))(sqqrt((n)));///求nn的平方方根取整整數(shù) whille(ii<=kk) { iff(((m%ii==00)&&&(n%%i===0))) { ff=f**i; m==m/ii; n==n/ii; i==2; } elssei+++; } f=f**m*nn; retuurnf;}冒泡排序：：//交交換排序序中的冒冒泡排序序法#inccludde<<stddio..h>#deffineeLEENGTTH110voidmaiin()){ inntii,j,,k,ttempp; intr[LLENGGTH]]; for(i==0;ii<LEENGTTH;ii++)) scaanf(("%dd",&&r[ii]);; //輸入入10個(gè)個(gè)整數(shù) for(i==1;ii<=LLENGGTH--1;ii++))//共共進(jìn)行LENNGTHH-1趟排序序 { k==0; forr(jj=0;;j<LLENGGTH--i;jj++))//第第i趟排序序比較的的次數(shù) iff(rr[j]]>r[[j+11])///若相相鄰兩記記錄的關(guān)關(guān)鍵字逆逆序， { k+++; ///則則互相交交換 temmp=rr[j]]; r[jj]=rr[j++1];; r[jj+1]]=teemp;; } iff(kk==00) //說明該該趟沒有有發(fā)生交交換 bbreaak; //跳出該該層循環(huán)環(huán) } for((i=00;i<<LENNGTHH;i+++) priintff("%%3d"",r[[i]));///輸輸出排序序結(jié)果}

素?cái)?shù)判斷：：intnnumbber;; ///nnumbber為全局局變量boolpriime((inttx)){ intti,,k; k=sqqrt((x);; for(i==2;ii<=kk;i+++) ///如果果X能被被2-----ssqrtt(x))中的的任何一一個(gè)整數(shù)數(shù)整除， if(x%%i===0) // 則X不不是素?cái)?shù)數(shù)，因此此應(yīng)跳出出該層循循環(huán) reeturrnffalsse; retrruntruue; //表示示X未被被2-----ssqrtt(x))中的的任何一一個(gè)整數(shù)數(shù)整除}素?cái)?shù)因子分分解：#inclludee<sstdiio.hh>#inclludee<mmathh.h>>#defiineN1100voidmaiin()){ intti,,j,kk,x,,y,ssievve_AA[N++1],,sieeve__B[NN+1]],siievee_C[[N+11]; scannf(""%d"",&xx); //輸入一一個(gè)1000以內(nèi)內(nèi)的非負(fù)負(fù)整數(shù) y=x; if(xx<0)) retturnn; //輸入整整數(shù)是負(fù)負(fù)數(shù) for((i=22;i<<=x;;i+++) //設(shè)置ssievve_AA篩中數(shù)數(shù)據(jù)22~X sieeve__A[ii]=ii; k=(iint))sqrrt(xx); for((i=22;i<<=k;;i+++) { j==i*ii; whiile((j<==x) { iif((sieeve__A[jj]!==0) // 定位i的的倍數(shù)處處 ssievve_AA[j]]=0;; // 篩去i的的倍數(shù)即即將其變變?yōu)?0 j==j+ii; // 求出i的的下一個(gè)個(gè)倍數(shù) } } j=0;; for(i==2;ii<=xx;i+++) // 將siievee_A篩篩中的素素?cái)?shù)賦給給sieeve__B篩子子 if(siievee_A[[i]!!=0)) { ssievv