数据结构（六）

学习数据结构与算法过程中的心得体会以及知识点的整理，方便我自己查找，也希望可以和大家一起交流。

—— 抓住那头牛 ——

1.题目描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

1.1 输入

两个整数，N和K

1.2 输出

一个整数，农夫抓到牛所要花费的最小分钟数

1.3样例输入与输出

样例输入
5 17
样例输出
4

2.代码实现

c++

#include 
   
    #include 
    
     using namespace std;int vis[200010];//队列数据节点typedef struct node{
       //农夫所处位置    int x;    //已经走过的步数    int step;}node;void path(queue
     
       que,int k);int main(){
      int N,K;    cin >> N >> K;    queue
      
        que;    node first;    first.x=N;    first.step=0;    que.push(first);    path(que,K);    return 0;}void path(queue
       
         que,int k){
       while(!que.empty())    {
           //将队列里第一个元素取出        node newnode=que.front();        //删除队列第一个元素        que.pop();        int x=newnode.x,step=newnode.step;        //如果到达牛的位置就结束        if(x==k)        {
               cout << step;            return;        }		//当前位置退后一格的假设        if(x-1>=0 && x-1<=100000 && vis[x-1]==0)        {
               node a;            a.step=step+1;            a.x=x-1;            que.push(a);            vis[x-1]=1;        }        //当前位置前进一格的假设        if(x+1>=0 && x+1<=100000 && vis[x+1]==0)        {
               node a;            a.step=step+1;            a.x=x+1;            que.push(a);            vis[x+1]=1;        }        //当前位置前进一倍的假设        if(x*2<=100000 && x*2>=0 && vis[x*2]==0)        {
               node a;            a.step=step+1;            a.x=x*2;            que.push(a);            vis[x*2]=1;        }    }}

3.代码说明

其实这道题我能想到的方法就是枚举法，把每一种可能都列举出来。利用队列我是这么做的：

在队列中插入每一种可能性，然后每一次将队列的第一个元素取出：

再通过取出元素的三种运算模式，把三种可能性的元素再次放入队列中：

通过不断的枚举，当第一个符合要求的元素被取出的时候，它是就是步数最少的选择，即答案。

这种计算方式并不是穷举法，因为我们规避了很多不必要的计算流程和限定范围，这种算法叫做分支界限法，也可以是回溯法，二者的相异之处在于：

回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

二者明显的区别在进行树的运算中尤为明显，而在队列中，对比并不强烈。

转载地址：http://tfazi.baihongyu.com/

你可能感兴趣的文章