




已阅读5页,还剩1页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
常见算法的MATLAB实现八 1.数论算法 求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a< b then swa(a,b); lcm:=a; while lcm mod b >0 do inc(lcm,a); end; 素数的求法 A.小范围内判断一个数是否为质数: function rime (n: integer): Boolean; var I: integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then begin rime:=false; exit; end; rime:=true; end; B.判断longint范围内的数是否为素数(包含求50000以内的素数表): rocedure getrime; var i,j:longint; :array1.50000 of boolean; begin fillchar(,sizeof(),true); 1:=false; i:=2; while i< 50000 do begin if then begin j:=i*2; while j< 50000 do begin j:=false; inc(j,i); end; end; inc(i); end; l:=0; for i:=1 to 50000 do if then begin inc(l);rl:=i; end; end;getrime function rime(x:longint):integer; var i:integer; begin rime:=false; for i:=1 to l do if r >=x then break else if x mod r=0 then exit; rime:=true; end;rime 2 3 4.求最小生成树 A.rim算法: rocedure rim(v0:integer); var lowcost,closest:array1.maxn of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcost:=costv0,i; closest:=v0; end; for i:=1 to n-1 do begin 寻找离生成树最近的未加入顶点k min:=maxlongint; for j:=1 to n do if (lowcostj< min) and (lowcostj< >0) then begin min:=lowcostj; k:=j; end; lowcostk:=0; 将顶点k加入生成树 生成树中增加一条新的边k到closestk 修正各点的lowcost和closest值 for j:=1 to n do if costk,j< lwocostj then begin lowcostj:=costk,j; closestj:=k; end; end; end;rim B.Kruskal算法:(贪心) 按权值递增 顺序删去图中的边若不形成回则将此边加入最小生成树。 function find(v:integer):integer; 返回顶点v所在的集合 var i:integer; begin i:=1; while (i< =n) and (not v in vset) do inc(i); if i< =n then find:=i else find:=0; end; rocedure kruskal; var tot,i,j:integer; begin for i:=1 to n do vset:=;初始化定义n个集合第I个集合包含一个素I :=n-1; q:=1; tot:=0; 为尚待加入的边数q为边集指针 sort; 对所有边按权值递增排序存于eI中eI.v1与eI.v2为边I所连接的两个顶点的序号eI.len为第I条边的长度 while >0 do begin i:=find(eq.v1);j:=find(eq.v2); if i< >j then begin inc(tot,eq.len); vset:=vset+vsetj;vsetj:=; dec(); end; inc(q); end; writeln(tot); end; 5.最短径 A.标号法求解单源点最短径: var a:array1.maxn,1.maxn of integer; b:array1.maxn of integer; b指顶点i到源点的最短径 mark:array1.maxn of boolean; rocedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark1:=true; b1:=0;1为源点 reeat best:=0; for i:=1 to n do If mark then 对每一个已计算出最短径的点 for j:=1 to n do if (not markj) and (ai,j >0) then if (best=0) or (b+ai,j< best) then begin best:=b+ai,j; best_j:=j; end; if best >0 then begin bbest_j:=best;markbest_j:=true; end; until best=0; end;bhf B.Floyed算法求解所有顶点对之间的最短径: rocedure floyed; begin for I:=1 to n do for j:=1 to n do if aI,j >0 then I,j:=I else I,j:=0; I,j表示I到j的最短径上j的前驱结点 for k:=1 to n do 枚举中间结点 for i:=1 to n do for j:=1 to n do if ai,k+aj,k< ai,j then begin ai,j:=ai,k+ak,j; I,j:=k,j; end; end; C. Dijkstra 算法: 类似标号法本质为贪心算法。 var a:array1.maxn,1.maxn of integer; b,re:array1.maxn of integer; re指最短径上I的前驱结点 mark:array1.maxn of boolean; rocedure dijkstra(v0:integer); begin fillch ar(mark,sizeof(mark),false); for i:=1 to n do begin d:=av0,i; if d< >0 then re:=v0 else re:=0; end; markv0:=true; reeat 每循环一次加入一个离1集合最近的结点并调整其他结点的参数 min:=maxint; u:=0; u记录离1集合最近的结点 for i:=1 to n do if (not mark) and (d< min) then begin u:=i; min:=d; end; if u< >0 then begin mark:=true; for i:=1 to n do if (not mark) and (au,i+d< d) then begin d:=au,i+d; re:=u; end; end; until u=0; end; D.计算图的传递闭包
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 执行信访工管理办法
- 发动机生产管理办法
- 吸烟点垃圾管理办法
- 江干区地名管理办法
- 升压站缺陷管理办法
- 新主播薪资管理办法
- 机场施工与管理办法
- 村小额资金管理办法
- 易损件工装管理办法
- 村池塘保护管理办法
- 卒中中心应知应会
- 山西省代县金升铁矿有限公司铁矿资源开发利用、地质环境保护与土地复垦方案
- 2021年新高考全国Ⅱ卷语文真题(含答案)
- 《天黑前的夏天》中水意象解析
- 院感知识PPT完整版
- JJF 1910-2021电化学工作站校准规范
- ks-s3002腔全自动刻蚀机规格书
- DB37-T 2401-2022危险化学品岗位安全生产操作规程编写导则
- 2023年小学科学教师招聘考试真题练习试题卷及参考答案
- 劳资专管员任命文件(样本)
- 电子教案与课件:制药过程安全与环保-第5章-制药过程“三废”防治技术
评论
0/150
提交评论