韩信走马分油c++

题目

• 把油桶里还剩下的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;
}

原文地址：https://blog.csdn.net/qq_37755459/article/details/143034553

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！