首页 > C++ > 卖油翁问题(闲作)

卖油翁问题(闲作)

2013年4月21日 发表评论 阅读评论

题目叫卖油翁,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

分类: C++ 标签: