社交网站 备案百度代理推广

题目

• 把油桶里还剩下的10斤油平分，只有一个能装3斤的油葫芦和一个能装7斤的瓦罐。如何分。

算法

1. 油壶编号0，1，2。不同倒法有：把油从0倒进0（本壶到本壶，无效），从0倒进1，从0倒进2；从1倒进0，从1倒进1（无效），从1倒进2；从2倒进0，从2倒进1，从2倒进2（无效）。此过程可用二个for循环来摸拟，见下图。
2. 为方便计算，以这种倒法为一次大循环，然后再不停地重复倒油。每次倒油，3个壶中的油量：10，0，0（举个例）是确定值，存入向量vector中。
3. 每种结果，再重复1中的9种倒法，又会产生更多的油量结果vector[0]、vector[1]、vector[2]。结果产生更多的结果……
4. 符合广度优先算法。用双端队列存储每一种结果，把初始值（10，0，0）入队。取出进行处理（相互之间倒油，有9种可能），将结果入队。再出队，处理，再入队，直到队列为空。
5. 倒油的结果（10，0，0），其种类是有限的，不同的倒油方法会产生重复结果现象，用map来去重。而且map还可以记录油的变化过程，即map[vector₀]=vector₀是初始，以后产生一个新结果作为键，值为上一次的状态。
   

代码

#include<iostream>
#include<vector>
#include<map>
#include<deque>
using namespace std;
//判断油壶的状态是否符合结果，即有没有出现5l油量的壶 
bool ok(vector<int>& v,int goal){for(int n:v){if(n==goal) return true;}return false;
}
//广度优先算法 
bool f(int* a,vector<int> v,int goal){deque<vector<int> > q;//双端队列 q.push_back(v);//初始值入队 map<vector<int>,vector<int> >  m;m[v]=v;while(1){int n=q.size();if(n==0) return false;for(int i=0;i<n;i++){vector<int> t=q.front();if(ok(t,goal)){while(m[t]!=t){cout<< t[0] <<"-"<< t[1]<< "-"<<t[2]<<endl;t=m[t];}return true;} q.pop_front();//倒油，从i壶倒进j壶 for(int i=0;i<3;++i)for(int j=0;j<3;++j){if(i==j) continue;if(t[i]==0) continue;if(t[j]==a[j]) continue;vector<int> t1=t;t1[j]+= t1[i];t1[i]=0;if(t1[j]>a[j]){//接收的油超过其容量 t1[i]=t1[j]-a[j];t1[j]=a[j];}if(m.count(t1)) continue;m[t1]=t;q.push_back(t1);} }}
}
int main(){int a[]={10,7,3};vector<int> v={10,0,0};f(a,v,5);return 0;
}