广度优先搜索算法-实验报告

计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：计科081实验日期：2010-姓名：学号：指导教师：实验序号：五实验成绩：一、实验名称广度优先搜索-抓住那头奶牛

二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对广度优先搜索算法的理解；三、实验环境任一C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、注册POJ账号，找到题号为3278的题目-抓住那头奶牛

；2、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤描述约翰有一头奶牛逃跑了，约翰要去抓住它。约翰在数轴上的位置N(0<=N<=100,100),奶牛在数轴上的位置K(0<=K<=100,100),约翰有两种移动的方式：向前或者向后一步，即X到X-1或者X+1，花费1分钟；传送到两倍距离位置，即X到2*X，花费1分钟；假设奶牛不知道自己正被抓捕，不会移动。请设计程序求出约翰需要的最少分钟数。输入1行，分别是约翰的位置N和奶牛的位置K。输出1行，所需要的最少分钟数。例子输入517

例子输出

4最短路径为5-4-8-16-17，共需4分钟。实验步骤：1、核心代码：while(!b.empty()){ y=b.front(); b.pop(); if(y==-1){x++;b.push(-1);y=b.front();b.pop();} a[y]=1; if(y>0&&a[y-1]==0){ b.push(y-1); if(y-1==k)break; a[y-1]=1;} if(a[y+1]==0&&y<k){ b.push(y+1); if(y+1==k)break; a[y+1]=1;} if(a[y*2]==0&&y<k&&y<50001){ b.push(2*y); if(2*y==k)break; a[2*y]=1;} }2、算法框架（流程图、纯文字语言、有注释的关键C代码均可）先建立队列，令队首为-1，队尾为约翰的位置N，开始搜索队列。从队首取出一个数，若为-1，让分钟数加1，并把-1放到队尾；若不为-1，则计算其加1减1及乘二的结果分别放到队尾，取下一个数，重复上述步骤，直到出现结果K。退出循环，输出分钟数。3、算法复杂度不会……调试过程及实验结果总结这个程序由于一直在做广度扩展，生成的子项非常多，需要很大的存储空间，找了很久终于找到最佳值。队列是一种动态存储结构，优点是长短随意，按需分配，缺点是只能访问队首和队尾。附录#include<iostream>#include<queue>usingnamespacestd;intmain(){ longintx=0,n,k,y,a[200000]={0}; queue<int>b; cin>>n>>k; if(n<0||k<0)return0; if(n>100000||k>100000)return0; if(n==k){cout<<0<<endl;return0;} if(n>k){cout<<n-k<<endl;return0;} b.push(-1); b.push(n); a[n]=1; while(!b.empty()){ y=b.front(); b.pop(); if(y==-1){x++;b.push(-1);y=b.front();b.pop();} a[y]=1; if(y>0&&a[y-1]==0){ b.push(y-1); if(y-1==k)break; a[y-1]=1;} if(a[y+1]==0&&y<k){ b.push(y+1); if(y+1==k)break; a[y+1]=1;} if(a[y*2]==0&&y<k&&