廣度優先搜索典例
00 題目
描述：
最簡單的佇列的使用
1 #include <iostream> 2 #include <queue> 3 using namespace std; 4 queue<int> q1; 5 int main() 6 { 7 int temp, x; 8 q1.push(5);//入隊 9 q1.push(8);//入隊 10 temp = q1.front();//訪問隊首元素 11 q1.pop();//出隊 12 q1.empty();//判佇列是否為空 13 q1.back();//回傳隊尾元素 14 q1.size();//回傳佇列長度 15 }
給定兩個正整數m、n，問只能做加1、乘2和平方這三種變化，從m變化到n最少需要幾次
輸入：
輸入兩個10000以內的正整數m和n，且m小于n
輸出：
輸出從m變化到n的最少次數
輸入樣例：
1 16
輸出樣例：
3
01 思路0
01-1 型別
雖然看上去感覺有一些無處下手，但是實際上就是一個三叉樹，并且要去去找 到達目標節點 的最低高度，
這個圖轉自加1乘2平方題解
很明顯，這是個廣搜典型題，
01-2 演算法
-
以初始數字（如1）當作根結點，入隊，出隊，產生三個子節點next，對子節點篩選符合條件的繼續進隊
關于三個子結點的產生，可以設定標志位標記為0，1，2
-
0->當前值+1
-
1->當前值*2
-
2->當前值*當前值
對應我的change函式
-
-
對next值進行判斷
-
當next為終點數字時，就停止，回傳高度（高度需要變數來記）
-
當next>終點數字時，不再入隊，
-
當next<終點數字時，入隊，方便下一步找它的子節點，
-
-
在bfs主控函式中把佇列走完，就能解決問題，
-
輸出
02 代碼0
1 //方法2 2 //按照題目要求使用佇列，相應演算法是廣搜 3 #include<iostream> 4 #include<queue> 5 using namespace std; 6 ? 7 queue<int> q; 8 int m,n; 9 int step[10000]; 10 int used[10000]; 11 ? 12 int bfs();//廣度優先搜索 13 int change(int now, int i);//三種變換 14 bool istarget(int now, int next); 15 //判斷是否達到目標數字 16 int main(){ 17 cin >> m >> n; 18 //始末位置 19 q.push(m); 20 //m入隊 21 cout << bfs() << endl; 22 return 0; 23 } 24 int bfs(){ 25 int next; 26 while(!q.empty() ){ 27 int now = q.front(); 28 q.pop(); 29 used[now]=1; 30 for(int i=0; i<3; i++){ 31 next = change(now,i); 32 //生成當前節點的下一節點（一共三個） 33 if(istarget(now, next)){ 34 return step[next]; 35 }//如果就達到目標，就回傳走了幾步，由于使用廣搜，就是最短路徑 36 } 37 } 38 return 0;//這點很重要，雖然code永遠到不了這里 39 } 40 ? 41 bool istarget(int now,int next){ 42 if(next<=n && used[next]==0){//確保子節點未超過目標值且未被訪問過 43 used[next]=1; 44 step[next] = step[now] + 1;//從當前到子節點需+1 45 //核心判斷 46 if(next == n){ 47 return true; 48 } 49 else{ 50 q.push(next); 51 //如果不是就吧這個節點當成普通節點放入佇列 52 } 53 } 54 return false; 55 } 56 ? 57 int change(int now, int i){ 58 if(i==0) return now+1; 59 if(i==1) return now*2; 60 else return now*now; 61 }
03 思路1
03-1 型別
動態規劃，更為簡潔，只需要一個main函式和兩個指標
03-2 演算法
-
從起始數字開始，我設定一個行走位逐個去走到終點
-
對i進行討論
-
先設定基準步伐，比較i的路經長度和i-1的路徑長度+1
-
當i為偶數，比較到達i的路徑長度和i/2的路徑長度+1
-
當i為平方數，（可以提前設定一個int 的i的根號，當t*t==i即為這個條件）比較到達i的路徑長度和t的路徑長度+1
-
-
演算法原理，因為i是從m開始走的，所以天然不需要回圈，只需不斷地呼叫之前的結果進行比較就能得到新的結果，這就是動態規劃的魅力所在，演算法時間復雜度為O(m-n).
04 代碼1
1 //加1乘2平方 2 ? 3 #include<stdio.h> 4 #include<string.h> 5 #include<iostream> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 const int maxn = 10000+50; 10 int dp[maxn],m,n; 11 ? 12 //min函式內置了 13 int main(){ 14 cin>>m>>n; 15 memset(dp,0x3f3f3f,sizeof(dp)); 16 dp[m] = 0; 17 for(int i = m+1; i <= n; i++){ 18 int t = sqrt(i); 19 dp[i]=min(dp[i],dp[i-1]+1); 20 if(i%2==0){ 21 dp[i] = min(dp[i], dp[i/2]+1); 22 } 23 if(t*t == i){ 24 dp[i] = min(dp[i],dp[t]+1); 25 } 26 } 27 cout << dp[n] << endl; 28 return 0; 29 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333373.html
標籤：其他