卖油翁问题(闲作)
题目叫卖油翁,Category放在Coding这一栏里面,就已经注定了这是篇水文了,没错,我来灌水了!!
倒不是讨论什么算法,或者别的什么的,毕竟卖油翁的问题,虽然我没google过,但是我相信早就烂大街了。。。那我干嘛写?谁告诉你我这里没有烂大街的东西的??好吧,其实真是的原因是,我早就告诉你了嘛,这是篇水文的说。。。
没有,其实是这个样子的,最近稍显烦躁,事情有那么一点多,你看嘛,比如书我一周前装的《零之轨迹》我到现在为止就只玩了一个小时左右;上周借的五本小说,现在为止才看完了1.5本;还是上周,自己给自己开的坑,要看完CLAMP的《翼》和《xxxholic》,现在两本各看了一卷才,还有40+卷还在坑里面;再然后,你说嘛最近雀龙门老是四位三位的,怎么回事,难道我被发牌姬讨厌么了??;再再再然后,B站最近被奇艺什么的攻占了,虽然有黑科技,但是看番总觉得没以前那么爽了是吧。。。。。。。。。。然后最近老板突然把实验室春游的是突然搞给我负责,然后春学期马上就要结束了,我他喵的还有一篇论文没写,最重要的是,还有一个大作业完全不知道怎么弄,马上就要交了魂淡!!所以嘛,烦躁。。。
so?我就大半夜的在IPAD上找了十来个游戏来玩,其中一个叫《the curse》,就是各式各样的谜题,你来解,然后不就遇到了卖油翁问题了么?然后喜闻乐见的发现自己解不开了么?然后发现忙了一下午春游跟旅行团那边沟通的事,还有半个小时就到我个人固定的吃饭时间了,能干嘛呢?于是,就写了卖油翁的程序。。。(背景略长是吧。。。)
其实我这里并不是想讲卖油翁的程序啊算法啊什么的,说过那东西应该烂大街了,而且我就随手写的程序,能有什么有深度的东西在里面?那我干嘛写BLOG?不说了嘛,灌水。。
为了点个题,我就还是说两句吧,争取200字以内完成,那个程序算法啊什么的,不就是个状态空间搜索嘛,深度优先,其实我以前写过卖油翁的问题的,用的是这里里面那个自己写的接口,刚刚瞄了一下以前写的那个程序,好像比我今天这个效率更高,它会判断是否回到曾经到达过的这个状态,而我这里就做了一个超级无敌简单的剪枝(虽然效率就提高了好多倍),但是对于是否同一个状态没有判断,反正深度达到指定最大值就算失败。
为什么写个这么简单的东西还要专门上来说呢?因为写完这个程序,感觉。。心情舒畅了好多,最近搞的都是些压力超大,不知道要怎么弄的东西,然后搞了一个轻松加愉快的东西,(果然我这种人在SAO里面的话永远只能刷小怪。。),最重要的是,百来行的代码,码了19分钟,然后一遍直接通过编译运行出结果,那种心情真他喵的ki摸机,果然我就说嘛,编程这种东西,最好就是闲着么事干写一写,玩一玩,给自己自娱自乐用的,把它当做工作或者以它为工作谋生的话,对我而言,实在伤不起。。
好吧,就当一篇杂谈了,附上代码,以便自己下次还会用得上。。
#include <iostream> #include <stdlib .h> #include <list> using namespace std; #define BUTTOM_NUMBER 3 //瓶子个数 #define MAX_DEPTH 6 //最深深度 const double ButtonCapacity[BUTTOM_NUMBER] = {7,4,3}; //每个瓶子容量 const double GoldState[BUTTOM_NUMBER] = {2,2,3}; //目标状态 int Operation[BUTTOM_NUMBER*(BUTTOM_NUMBER-1)][2] = {0}; //移动操作 double InitState[BUTTOM_NUMBER] = {7,0,0}; //初始状态 class CState { public: double Volume[BUTTOM_NUMBER]; }; void InitOperation() { int counter = 0; for(int i = 0;i < BUTTOM_NUMBER;i++) { for(int j = 0;j < BUTTOM_NUMBER;j++) { if(j == i) continue; else { Operation[counter][0] = i; Operation[counter++][1] = j; } } } } CState GetNextState(CState CurState,int OperationIdx) { int From_idx = Operation[OperationIdx][0]; int To_idx = Operation[OperationIdx][1]; if (CurState.Volume[From_idx] + CurState.Volume[To_idx] <= ButtonCapacity[To_idx]) { CurState.Volume[To_idx] += CurState.Volume[From_idx]; CurState.Volume[From_idx] = 0; } else { CurState.Volume[From_idx] -= ButtonCapacity[To_idx]-CurState.Volume[To_idx]; CurState.Volume[To_idx] = ButtonCapacity[To_idx]; } return CurState; } int ReachGoal(CState state) { for(int i = 0;i < BUTTOM_NUMBER;i++) { if(state.Volume[i] != GoldState[i]) return 0; } return 1; } void ShowResult(list<CState> m_list) { list<cstate>::iterator iter= m_list.begin(); for (;iter != m_list.end();iter++) { for(int i = 0;i < BUTTOM_NUMBER;i++) { cout<<(*iter).Volume[i]; if(i != BUTTOM_NUMBER-1) cout<<"->"; } cout< <endl; } cout<<endl<<endl<<endl; } void FigureGame(list<CState> m_list,CState FinalState,int OperationIdx) { if(m_list.size() > MAX_DEPTH || FinalState.Volume[Operation[OperationIdx][0]] == 0) return; CState NexState = GetNextState(FinalState,OperationIdx); m_list.push_back(NexState); if(ReachGoal(NexState)) ShowResult(m_list); for(int i = 0;i < BUTTOM_NUMBER*(BUTTOM_NUMBER-1);i++) FigureGame(m_list,NexState,i); } int main(int argc,char* argv[]) { list<CState> m_list; CState state; for(int i = 0;i < BUTTOM_NUMBER;i++) state.Volume[i] = InitState[i]; m_list.push_front(state); InitOperation(); for(int i = 0;i < BUTTOM_NUMBER*(BUTTOM_NUMBER-1);i++) FigureGame(m_list,state,i); system("pause"); return 0; }
【完】
本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com