算法分析与设计狼找兔子.ppt

算法分析与设计 狼吃兔子问题 算法演示 问题分析 我们先做一个假设，你围着400米的环形跑道跑步，分多次（整数次）跑，每次跑150米，如果你想回到原出发点，那么毫无疑问你跑的最短总路程为400米的整数倍同时也是150米的整数倍并且为最小公倍数1200米，需要经过1200/150=8次奔跑。 经过以上分析，我想你已经明白了狼找兔子经过的最小总山洞数目为n、m的最小公倍数，假设该公倍数为k，那么狼有哪些信誉好的足球投注网站过的山洞为k/m个。如果完成整个过程狼有哪些信誉好的足球投注网站过的山洞为n，那么兔子便无处藏身（即k/m=n亦即k=m*n）。在数学中我们已经知道(m*n)/（m，n的最大公约数）=k，由此可知当最大公约数为1时刚好满足兔子无藏身之地，同时我们也可以知道m、n的最大公约数不为1时兔子有藏身之地。 公约数法 search_rabbit流程 系统介绍 时间复杂度分析 时间复杂度分析 总体上讲，程序运行的时间随着山洞的数目（n）增大而增大,同时程序运行的总时间与每次跳过山洞的数目有关，如果山洞数目n可以整除每次跳过的数目m，那么程序相对来说会快一点结束，速度关系大致是这样： n整除m n和m公约数不为1 其他 时间复杂度分析 时间复杂度分析 程序运行时间T=执行（p=p-next）m,n的最小公倍数次的时间T1+执行（p-state=1）m/m，n的最大公约数次的时间T2。 因此时间复杂度为O（m,n的最小公倍数）+O（m/（m，n的最大公约数））。 时间复杂度分析 时间复杂度分析 空间复杂度分析 对于该程序，存储山洞信息的链表可以动态改变，其总长度于山洞的总数量有关。 空间复杂度为S(n)。 小组成员： 王尤峰、刘鹏飞、刘建华、梁建文、李绵梁、陈秀珠、杨弘、王祎 指导老师：付红 * 07级计算机科学与技术3班王尤峰 cave5 cave0 cave4 cave2 cave3 cave1 Wolf N=6 M=4 void main() { int n,m,result; scanf(%d,n); scanf(%d,m); result=check(n,m); if(result==1) printf(“该兔子死定了！\n); else printf(“有安全山洞！\n); } #include stdio.h int check(int n,int m) { int i,temp,k; k=mn?m:n; for(i=1;i=k;i++) { if(m%i==0n%i==0) { temp=i; } } return temp; } 检查山洞 跳过m个山洞 Y 未回到起始山洞 跳过m个山洞 检查山洞 N 结束 开始 for(i=0;im;i++) p=p-next start head-state=1 for(i=0;im;i++) p=p-next head-num!=p-num p-state=1 end N Y 操作系统：Windows XP CPU：Intel Core 2 4300 1.8G主频 内存：2G 5699166 2682311 769354 1823781 1433433 357543 713158 363771 72183 7722 9 1004910 493258 273965 216528 164068 126588 81060 40790 8861 2379 8 4639727 524321 1765717 1442769 1155008 863073 570680 285075 56899 6452 7 2270657 970638 314221 621745 489370 130642 243270 121610 24486 3248 6 972837 384484 284097 207986 160869 120305 80115 40370 7711 1569 5 1047324 638628 279619 215363 160089 118586 77041 39735 8651 1649 4 2755274 1119811 333538 653313 493763 133091 254336 139908 25650 3483 3 896556 426172 311607 225759 176743 129702 86713 49082 9941 1839 2 1260762 1043750 8