计科班算法设计与分析

算法：是若干条指令组成的有穷序列算法的三个要素1)数据:运算序列中作为运算对象和结果的数据.2)运算::运算算序列中中的各种种运算::赋值,,算术和和逻辑运运算3)控制和和转移::运算算序列中中的控制制和转移移.四条性质：：输入、输输出、确确定性、有有穷性四条性质：：1)输入：：有零个个或多个个由外部部提供的的量作为为算法的的输入2)输出：：算法产产生至少少一个量量作为输输出3)确定性性：组成成算法的的每条指指令是清清晰的，无无歧义的的。4)有限性性：算法法中每条条指令的的执行次次数是有有限的，执执行每条条指令的的时间也也是有限限的。程序：是算算法用某某种程序序设计语语言的具具体实现现算法的复杂杂性：算算法运行行所需要要的计算算机资源源的量时间复杂性性（算法法运行所所需要的的计算机机时间资资源的量量）空间复杂性性（算法法运行所所需空间间资源的的量）时间复杂性性的三种种情况：：最坏情情况（可可操作性性最好且且最优实实际价值值）、最最好情况况、平均均情况分治法的设设计思想想：将一一个难以以直接解解决的大大问题，分分割成一一些规模模较小的的相同问问题，以以便各个个击破，分分而治之之。递归：直接接或间接接地调用用自身的的算法。递归函数：用函数自身给出定义的函数。阶乘函数可可递归定定义为：：递归定义式式：intffacttoriial((inttn)){ if((n===00)rretuurn1; retuurnn**faactooriaal(nn-1));}Fibonnaccci数列列：无穷穷数列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个过过元素分分成大致致相同的的两半，取取a[nn/2]]与x作作比较。合并排序：：用分治治法策略略实现对对n个元元素进行行排序的的算法。基本思想是：将待排序元素分成大小大致相同的两个子集，分别对两个子集合进行排序，最终将排好序的子集合并成所要求的排好序的集合。动态规划算算法基本本思想（自底向上、全局最优）：讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不不同的是是：适用用于动态态规划法法求解的的问题，经经分解得得到的子子问题往往往不是是互相独独立的。最优子结构构性质（问问题的最最优解包包含了其其子问题题的最优优解）子问题重叠叠性质（在在用递归归算法自自顶向下下求解此此问题时时，每次次产生的的子问题题并不总总是新问问题，有有些子问问题被反反复计算算多次）备忘录方法法（动态规规划算法法变形）：：用表格格保存已已解决的的子问题题的答案案，在下下次需要要解此子子问题时时，只要要简单地地查看该该子问题题的解答答，而不不必重新新计算。最优二叉搜搜索树性性质：存存储于每每个结点点中的元元素x大大于其左左子树中中任一结结点所存存储的元元素，小小于其右右子树中中任一结结点所存存储的元元素。贪心算法（自顶向下、局部最优）：通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择。贪心选择性性质（所所求问题题的整体体最优解解可以通通过一系系列局部部最优的的选择来来达到，是是贪心算算法与动动态规划划算法的的主要区区别）最有子结构构性质（一一个问题题的最优优解包含含其子问问题的最最优解）哈夫曼编码码：是广广泛用于于数据文文件压缩缩的十分分有效的的编码方方法。最短路径：：给定一一个，其其中每条条边的权权是非负负实数。一个带权有向图一个带权有向图11111100601030105020最小生成树树性质：：用贪心心算法设设计策略略可以设设计出构构造最小小生成树树的有效效算法。回溯法（盲盲人爬山山、迷宫宫问题、nn后问题题）：在解解问题的的解空间间树中，按按深度优优先策略略，从根根节点出出发搜索索解空间间树。基本思想：：从开始始结点（根根节点）出出发，以以深度有有限方式式搜索整整个解空空间。分枝限界法法基本思思想：以以广度优优先或以以最小耗耗费（最最大效益益）优先先的方式式搜索问问题的解解空间树树。分枝限界法法求解目目标是找找出满足足约束条条件的一一个解，或或是满足足约束条条件的解解中找出出使某一一目标函函数值达达到极大大或极小小的解，即即在某种种意义下下的最优优解。回溯法求解解目标是是找出解解空间中中满足约约束条件件的所有有解。批处理作业业调度：：给定nn个作业业的集合合J==(JJ1,JJ2,……,Jnn)。每每个作业业Ji都都有两项项任务分分别在两两台机器器上完成成。每个个作业必必须先由由机器11处理，然然后再由由机器22处理。分支限界法法与回溯溯法：分支限限界法与与回溯法法的求解解目标不不同，回回溯法的的求解目目标是找找出求解解空间中中满足约约束条件件的所有有解，而而分支限限界法求求解的目目标则是是找出满满足约束束条件的的一个解解。回溯溯法以深深度优先先的方式式搜索解解空间，而而分支限限界法则则以广度度优先或或最小耗耗费优先先的方式式搜索空空间。随机化算法法基本特特征：对对所求解解问题的的同一实实例用同同一随机机化算法法求解两两次可能能得到完完全不同同的效果果。随机数在随随机化算算法设计计中扮演演着十分分重要的的角色。符号三角问问题：#inclludee<sstdiio.hh>#defiineM113#defiineN113Triannglee(chharA[MM][NN]){ intti,,j; prinntf(("\nn输入入第1行行的数据据：")); for(j==0;jj<N;;j+++) //输入第第1行的的数据 scaanf(("%cc",&&A[00][jj]);; for(i==1;ii<M;;i+++) //A数组组的第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]])///如如果上一一行的相相邻两符符号相同同 AA[i++1][[j+11]=''+';; //则下一一行的符符号为''+' ellse AA[i++1][[j+11]=''-';; //否则下下一行的的符号为为'-'' 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个整数数给矩阵阵A forr(jj=0;;j<NN;j+++) sccanff("%%d",,&A[[i][[j])); for(i==0;ii<N;;i+++) //输入66个整数数给矩阵阵B forr(jj=0;;j<MM;j+++) sccanff("%%d",,&B[[i][[j])); MatrrixMMulttiplly(AA,BB,CC); prinntf(("\nn两矩矩阵相乘乘的的结结果如下下：\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;//在右半半部继续续查找 elsse leeft==midddlee+1;;//在右半部继继续查找找 } 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++)) //对数组组进行排排序 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输入欲欲查找的的数据：：");; scannf(""%d"",&kkey)); i=biinarry_ssearrch((r,kkey)); if((i===-1)) priintff("\\n已已经查找找完，尚尚未找到到该数！！\n\\n")); elsee priintff("\\n\nn已找找到，其其序号是是：%dd\nn\n"",i));}

快速排序序：#inclludee<sstdiio.hh>#inclludee<sstdllib..h>#defiineMAXXLENN100intpparttitiion((inttr[[],iints,iintt) { intti,,j,rrp; i=s;; j=t;; //一一趟快速速排序，将将基准记记录移到到正确位位置 rp=rr[s]]; //基基准记录录暂存rp中 whille(ii<j)) //从从序列的的两端交交替向中中间扫描描 { whhilee(i<<j&&&rr[j]]>=rrp) //扫扫描比基基准记录录小的位位置 j---; r[ii]=rr[j]]; //将将比基准准记录小小的数据据移到低低端 whiile((i<jj&&&r[[i]<<=rpp) //扫扫描比基基准记录录大的位位置 i+++; r[jj]=rr[i]]; //将将比基准准记录大大的数据据移到高高端 } r[i]]=rpp; //基基准记录录到位 retuurni;}voidQuiickSSortt(inntrr[],,intts,,inttt)) //快快速排序序递归算算法{ inttk;; if((s<tt) //长长度达于于1 { k==parrtittionn(r,,s,tt); //调调用一趟趟快速排排序算法法将r[[s]...r[[t]一一分为二二 QuiickSSortt(r,,s,kk-1)); //对对低端子子序列递递归排序序，k是是支点位位置 QuiickSSortt(r,,k+11,t)); //对对高端子子序列递递归排序序 }}voidmaiin()){ intti;; intr[MMAXLLEN]]; prinntf(("\nn请输输入%dd个整数数：",,MAXXLENN); for(i==0;ii<MAAXLEEN;ii++)) scaanf(("%dd",&&r[ii]);; QuicckSoort((r,00,MAAXLEEN-11); prinntf(("\nn快速速排序的的结果如如下：\\n\nn");; for((i=00;i<<MAXXLENN;i+++) priintff("%%3d"",r[[i])); prinntf(("\nn\n"");}循环赛日程程表：#inclludee<sstdiio.hh>#defiineMAXXLENN8voidmaiin()){ intti,,j; intx[MMAXLLEN++1][[MAXXLENN+1]]={00}; //数组清清零 for(i==1;ii<=MMAXLLEN;;i+++) ///产产生第11列数据据 x[ii][11]=ii; for(i==1;ii<=MMAXLLEN;;i+++) ///产产生第22列数据据 if(i%22!==0) x[[i][[2]==x[ii+1]][1]]; ///产产生奇数数行的第第2列的的数据 elsse x[[i][[2]==x[ii-1]][1]]; ///产产生偶数数行的第第2列的的数据 for((i=11;i<<=8;;i+++) ///产产生左半半部表中中的右半半部分 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+++) //产生生右半部部表的数数据 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循环环赛日程程表如下下：\nn\n""); for(i==1;ii<=MMAXLLEN;;i+++) ///输出该该表 { foor((j=11;j<<=MAAXLEEN;jj++)) prrinttf(""%6dd",xx[i]][j]]); priintff("\\n\nn");; }}

最大公约数数：intggcd((inttm,,inttn)){ intr; whille(nn!=00){ r==m%nn; m==n;; n==r;; } retuurnm;}最小公倍数数：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的平方方根取整整数 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个个整数 for(i==1;ii<=LLENGGTH--1;ii++))//共共进行LENNGTHH-1趟排序序 { k==0; forr(jj=0;;j<LLENGGTH--i;jj++))//第第i趟排序序比较的的次数 iff(rr[j]]>r[[j+11])///若相相邻两记记录的关关键字逆逆序， { k+++; ///则则互相交交换 temmp=rr[j]]; r[jj]=rr[j++1];; r[jj+1]]=teemp;; } iff(kk==00) //说明该该趟没有有发生交交换 bbreaak; //跳出该该层循环环 } for((i=00;i<<LENNGTHH;i+++) priintff("%%3d"",r[[i]));///输输出排序序结果}

素数判断：：intnnumbber;; ///nnumbber为全局局变量boolpriime((inttx)){ intti,,k; k=sqqrt((x);; for(i==2;ii<=kk;i+++) ///如果果X能被被2-----ssqrtt(x))中的的任何一一个整数数整除， if(x%%i===0) // 则X不不是素数数，因此此应跳出出该层循循环 reeturrnffalsse; retrruntruue; //表示示X未被被2-----ssqrtt(x))中的的任何一一个整数数整除}素数因子分分解：#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); //输入一一个1000以内内的非负负整数 y=x; if(xx<0)) retturnn; //输入整整数是负负数 for((i=22;i<<=x;;i+++) //设置ssievve_AA筛中数数据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的的倍数处处 ssievve_AA[j]]=0;; // 筛去i的的倍数即即将其变变为00 j==j+ii; // 求出i的的下一个个倍数 } } j=0;; for(i==2;ii<=xx;i+++) // 将siievee_A筛筛中的素素数赋给给sieeve__B筛子子 if(siievee_A[[i]!!=0)) { ssievv