资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法分析与设计,狼吃兔子问题,07级计算机科学与技术3班王尤峰,算法分析与设计狼吃兔子问题07级计算机科学与技术3班王尤峰,1,算法演示,cave5,cave0,cave4,cave2,cave3,cave1,Wolf,N=6,M=4,算法演示cave5cave0cave4cave2cave3c,2,问题分析,我们先做一个假设，你围着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时兔子有藏身之地。,问题分析我们先做一个假设，你围着400米的环形跑道跑步，分多,3,公约数法,void main(),int n,m,result;,scanf(%d,scanf(%d,result=check(n,m);,if(result=1),printf(“该兔子死定了！n);,else,printf(“有安全山洞！n);,#include ,int check(int n,int m),int i,temp,k;,k=mn?m:n;,for(i=1;i=k;i+),if(m%i=0&n%i=0),temp=i;,return temp;,公约数法void main()#include state=1,for(i=0;inext,head-num!=p-num,p-state=1,end,N,Y,search_rabbit流程检查山洞跳过m个山洞Y未回到起,5,系统介绍,操作系统：Windows XP,CPU：Intel Core 2 4300,1.8G主频,内存：2G,系统介绍操作系统：Windows XP,6,时间复杂度分析,时间复杂度分析,7,时间复杂度分析,总体上讲，程序运行的时间随着山洞的数目（n）增大而增大,同时程序运行的总时间与每次跳过山洞的数目有关，如果山洞数目n可以整除每次跳过的数目m，那么程序相对来说会快一点结束，速度关系大致是这样：,n整除m n和m公约数不为1 其他,时间复杂度分析 总体上讲，程序运行的时间随着山洞的数目（,8,时间复杂度分析,100,1000,5000,10000,15000,20000,25000,30000,35000,40000,0,674,449,464,429,449,644,574,459,559,634,1,1989,20292,144846,284620,413598,579641,716384,883896,1043750,1260762,2,1839,9941,49082,86713,129702,176743,225759,311607,426172,896556,3,3483,25650,139908,254336,133091,493763,653313,333538,1119811,2755274,4,1649,8651,39735,77041,118586,160089,215363,279619,638628,1047324,5,1569,7711,40370,80115,120305,160869,207986,284097,384484,972837,6,3248,24486,121610,243270,130642,489370,621745,314221,970638,2270657,7,6452,56899,285075,570680,863073,1155008,1442769,1765717,524321,4639727,8,2379,8861,40790,81060,126588,164068,216528,273965,493258,1004910,9,7722,72183,363771,713158,357543,1433433,1823781,769354,2682311,5699166,时间复杂度分析10010005000100001500020,9,时间复杂度分析,程序运行时间T=执行（p=p-next）m,n的最小公倍数次的时间T1+执行（p-state=1）m/m，n的最大公约数次的时间T2。,因此时间复杂度为O（m,n的最小公倍数）+O（m/（m，n的最大公约数）。,时间复杂度分析 程序运行时间T=执行（p=p-next,10,时间复杂度分析,时间复杂度分析,11,时间复杂度分析,时间复杂度分析,12,空间复杂度分析,对于该程序，存储山洞信息的链表可以动态改变，其总长度于山洞的总数量有关。,空间复杂度为S(n)。,空间复杂度分析 对于该程序，存储山洞信息的链表可以动态改变,13,#include ,#include ,#include ,typedef struct shandong,int num;,int state;,struct shandong *next;,cave;,链表法的具体实现,#include 链表法的具体实现,14,void createlist(cave *head,int n),/创建链表并初始化， p-state =0代表狼未进山洞,cave *p,*q;,int i;,p=head;,for(i=0;inum=i;,p-state=0;,q=(cave *)malloc(sizeof(cave);,p-next=q;,p=q;,p-num=n-1;,p-state =0;,p-next=head;,void createlist(cave *head,int,15,void search_rabbit(cave *head,int m),/,cave *p;,int i;,p=head;,p-state=1; /检查山洞,for(i=0;inext; /跳过m个山洞,while(head-num!=p-num),p-state=1; /检查山洞,for(i=0;inext; /跳过m个山洞,void search_rabbit(cave *head,16,void print_result(cave *head,int n),/,int i;,int count=0;,cave *p;,p=head;,for(i=0;istate=0),+count;,printf(“第% 个山洞安全！n,p-num);,p=p-next;,if(count=0) printf(“这只兔子死定了！n);,else printf(“安全的山洞共有%d个。n,count);,void print_result(cave *head,i,17,void main(),int m,n;,LARGE_INTEGER t1,t2,tc;,double t;,cave *head=(cave *)malloc(sizeof(cave);,printf(“山洞的数目n(int类型且n0)=);,scanf(%d,printf(“每次跳过山洞的数目m(int类型且m0)=);,scanf(%d,createlist(head,n);,QueryPerformanceFrequency(,QueryPerformanceCounter(,search_rabbit(head,m);,QueryPerformanceCounter(,print_result(head,n);,/ printf(Begin Time:%un,t1.QuadPart);,/ printf(End Time:%un,t2.QuadPart);,t=(double)(1000000000*(t2.QuadPart- t1.QuadPart)/tc.QuadPart);,printf(“Lasting Time: %f 纳秒。n,t);,void main(),18,小组成员：,王尤峰、刘鹏飞、刘建华、梁建文、李绵梁、陈秀珠、杨弘、王祎,指导老师：付红,19,Thanks,Thanks,20,
展开阅读全文