Title Description

The farmer knows the location of a cow , Want to catch it . The farmer and the cow are on the number axis
, Farmer's starting point N(0<=N<=100000), Cattle at point
K(0<=K<=100000). There are two ways for farmers to move :
1, from X Move to X-1 or X+1, One minute per move
2, from X Move to 2*X, One minute per move
Suppose the cow didn't realize the farmer's action , Stand still . Farmers need at least
How long does it take to catch the cow ?

thinking ( Peking University Guo Wei )

Suppose the farmer starts at the point 3, Cattle are located 5
N=3,K=5, The right side is 6.
How to search for a way to 5 Path ?

strategy 1) Depth first search

Starting from the starting point , Randomly choose a direction , can
Go ahead, go ahead ( extend ), go
If you don't move, go back . Can't go already
Passing point ( To weigh ).

If you're lucky :
3->4->5
or 3->6->5
Problem solving

If you're not lucky :
3->2->4->5
The worst of luck :
3->2->1->0->4->5

Want to get the best ( short ) solution , Then all walks should be traversed . Can use
Optimization of various means , such as , If the path length has been found n
Solution , All lengths greater than n You don't have to try .
Nodes on the path need to be stored during the operation , Fewer quantity .
Using stack to store nodes

strategy 2) Breadth first search :

Layer nodes . The starting point is No. 0 layer . From then on
Minimum requirement n The point that can be reached in step belongs to the n
layer .
The first 1 layer :2,4,6
The first 2 layer :1,5
The first 3 layer :0

Layer nodes . The starting point is No. 0 layer . From then on
Minimum requirement n The point that can be reached in step belongs to the n
layer .
In hierarchical order , Expand nodes from small to large .
After all the low-level points are expanded , just
Will expand higher-level points .

search process ( Node expansion process ):
3
2 4 6
1 5
Problem solving .
Expansion time , Can't extend the passed section
spot ( To weigh ) .

Ensure the best solution is found , But because of the expansion
There are many nodes coming , And most nodes need
Preservation , Therefore, the storage space needed is large .
Using queue to store nodes .

Queue is first in, first out

To traverse all nodes :
 Deep search
1-2-4-8-5-6-3-7 
Guang Shu
1-2-3-4-5-6-7-8

Wide search algorithm :

1: First , Put the initial node So Put in open In the table
2: If the problem is misunderstood , Then fail to exit
3: hold open The first node of the table is taken out and put in closed surface , And the node is n
4: Inspection node n Is it the target node , If so, we'll find a solution , Sign out
5: If node n Non expansible , Turn to judgment open Whether the table is empty
6: Expansion node n, Keep it away. closed Table and open The child nodes in the table are placed again open Tail of table , And set the pointer to the parent node for each child node , Then turn to judge whether open Empty ?

Change process of breadth first search queue :
1:
Closed:
Open: 3
2
Closed: 3
Open: 2 4 6
3
Closed: 3 2
Open: 4 6 1
4
Closed: 3 2 4
Open: 6 1 5
5
Closed: 3 2 4 6
Open: 1 5
6
Closed: 3 2 4 6 1
Open: 5 0
7
Closed:3 2 4 6 1 5
Open: 0
Target node 5 Outgoing queue , Problem solving .

Code
#include<iostream> #include<cstring> #include<queue> using namespace std; int N
,K; const int MAXN = 100000; int visited[MAXN + 10];
// Weight mark ,visited[i]=true Express i Has been expanded struct Step { int x;// position int steps;// To the great x Steps required
Step(int xx, int s) :x(xx), steps(s) {} }; queue<Step>q;// queue , Namely open surface int main() {
cin>> N >> K; memset(visited, 0, sizeof(visited)); q.push(Step(N, 0)); visited[
N] = 1; while (!q.empty()) { Step s = q.front(); if (s.x == K) {// Find the target cout << s
.steps << endl; return 0; } else { if (s.x - 1 >= 0 && !visited[s.x - 1]) {
// Extend left q.push(Step(s.x - 1, s.steps + 1)); visited[s.x - 1] = 1;// Set access tag } if (
s.x + 1 <= MAXN && !visited[s.x + 1]) {// Extend right q.push(Step(s.x + 1, s.steps + 1)
); visited[s.x + 1] = 1; } if (s.x * 2 <= MAXN && !visited[s.x * 2]) { q.push(
Step(s.x * 2, s.steps + 1)); visited[s.x * 2] = 1; } q.pop(); } } return 0; }

Technology
©2019-2020 Toolsou All rights reserved,
java Comparing attribute values between two objects utilize Python handle Excel data ——xlrd,xlwt library Bidirectional linked list Why? Python Not a future oriented programming language ?Python【 Assignment statement 】 Special lecture , You can't just a=b ah ! Suggest mastering ! utilize Python handle Excel data ——pandas library see SQL-SERVER Data volume and occupied space of database and each table PID The algorithm finally figured out the principle , It was so simple web Two front-end practical games ( Attached source code ) Beginners learn Python Be sure to know what his basic algorithms are ? What is the function ?