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

《广度优先搜索算法-实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：计科081实验日期：2010-11-26姓名：学号：指导教师：实验序号：五实验成绩：一、实验名称广度优先搜索-抓住那头奶牛 二、实验目的及要求1、学会使用在线测评的算法题目评分系统；2、通过直观的应用问题，加深对广度优先搜索算法的理解；三、实验环境任一C或C++编写调试工具，北京大学ICPC在线测评系统POJ四、实验内容1、注册POJ账号，找到题号为3278的题目-抓住那头奶牛  ；2、进行简单测试，完成之后提交到POJ系统。五、算法描述及实验步骤描述约翰有一头奶牛逃跑了，约翰要去

2、抓住它。约翰在数轴上的位置N(0<=N<=100,100),奶牛在数轴上的位置K(0<=K<=100,100),约翰有两种移动的方式：（1）向前或者向后一步，即X到X-1或者X+1，花费1分钟；（2）传送到两倍距离位置，即X到2*X，花费1分钟；假设奶牛不知道自己正被抓捕，不会移动。请设计程序求出约翰需要的最少分钟数。输入1行，分别是约翰的位置N和奶牛的位置K。输出1行，所需要的最少分钟数。例子输入517例子输出4最短路径为5-4-8-16-17，共需4分钟。实验步骤：1、核心代码：while(!b.empty()){y=b.front()

3、;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

4、建立队列，令队首为-1，队尾为约翰的位置N，开始搜索队列。从队首取出一个数，若为-1，让分钟数加1，并把-1放到队尾；若不为-1，则计算其加1减1及乘二的结果分别放到队尾，取下一个数，重复上述步骤，直到出现结果K。退出循环，输出分钟数。3、算法复杂度不会……调试过程及实验结果总结这个程序由于一直在做广度扩展，生成的子项非常多，需要很大的存储空间，找了很久终于找到最佳值。队列是一种动态存储结构，优点是长短随意，按需分配，缺点是只能访问队首和队尾。附录#include#includeusingnamespace

5、std;intmain(){longintx=0,n,k,y,a[200000]={0};queueb;cin>>n>>k;if(n<0

6、

7、k<0)return0;if(n>100000

8、

9、k>100000)return0;if(n==k){cout<<0<k){cout<

10、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