大学网站首页设计,百度公司地址,贵阳网站建设王道下拉惠,齐家网装修口碑怎么样韩信走马分油c 题目算法代码 题目
把油桶里还剩下的10斤油平分#xff0c;只有一个能装3斤的油葫芦和一个能装7斤的瓦罐。如何分。
算法
油壶编号0#xff0c;1#xff0c;2。不同倒法有#xff1a;把油从0倒进0#xff08;本壶到本壶#xff0c;无效#xff09; 题目算法代码 题目
把油桶里还剩下的10斤油平分只有一个能装3斤的油葫芦和一个能装7斤的瓦罐。如何分。
算法
油壶编号012。不同倒法有把油从0倒进0本壶到本壶无效从0倒进1从0倒进2从1倒进0从1倒进1无效从1倒进2从2倒进0从2倒进1从2倒进2无效。此过程可用二个for循环来摸拟见下图。为方便计算以这种倒法为一次大循环然后再不停地重复倒油。每次倒油3个壶中的油量1000举个例是确定值存入向量vector中。每种结果再重复1中的9种倒法又会产生更多的油量结果vector[0]、vector[1]、vector[2]。结果产生更多的结果……符合广度优先算法。用双端队列存储每一种结果把初始值1000入队。取出进行处理相互之间倒油有9种可能将结果入队。再出队处理再入队直到队列为空。倒油的结果1000其种类是有限的不同的倒油方法会产生重复结果现象用map来去重。而且map还可以记录油的变化过程即map[vector0]vector0是初始以后产生一个新结果作为键值为上一次的状态。
代码
#includeiostream
#includevector
#includemap
#includedeque
using namespace std;
//判断油壶的状态是否符合结果即有没有出现5l油量的壶
bool ok(vectorint v,int goal){for(int n:v){if(ngoal) return true;}return false;
}
//广度优先算法
bool f(int* a,vectorint v,int goal){dequevectorint q;//双端队列 q.push_back(v);//初始值入队 mapvectorint,vectorint m;m[v]v;while(1){int nq.size();if(n0) return false;for(int i0;in;i){vectorint tq.front();if(ok(t,goal)){while(m[t]!t){cout t[0] - t[1] -t[2]endl;tm[t];}return true;} q.pop_front();//倒油从i壶倒进j壶 for(int i0;i3;i)for(int j0;j3;j){if(ij) continue;if(t[i]0) continue;if(t[j]a[j]) continue;vectorint t1t;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};vectorint v{10,0,0};f(a,v,5);return 0;
}
