huaxiazhihuo

 

玩具代码 24点游戏

        所谓24点,就是甩出几个整数,整数之间没有固定的前后顺序,给它们添加上加减乘除括号等,形成一条式子,最后运算结果等于24。很自然的想法,就是祭出表达式树。但24点只是一个小程序,用表达式树来解决,实在有点大材小用了,太委屈表达式树了,所以坚决抵制。
        浏览各网友们的24点文章,发现大多数都在用最笨拙的穷举法写程序,或者是先搞成字符串,然后再对字符串求值,毫无新意,代码风格也差,都是四五重循环,难以扩充。用穷举法也没什么不好,但是,就算是穷举,也要穷举得漂漂亮亮,虽不能遗漏,但也不要重复,然后代码中也不能写死了,要保持一定的扩充性。不过得承认,不管怎么样,他们终究还是写出了24点的代码。
        24点粗看起来似乎有点棘手。但很容易就可以发现一种很自然的方法,假如4个整数参与24点了,那么就从中取出两个数,进行加减乘除之后合成一个数,放回去,于是4个数变成3个数,再用同样的办法使这每一排3个数的组合变成两个数,最后就只剩下两个数,稍一运算,很容易就可以判断两个数能否凑成24。很容易就看得出来,这属回溯法,最适合写成递归的形式。但是,这一次的递归,要用代码表达出来,却着实有点不容易。不过,只要有了算法,总是有办法写成代码。为了加深难度,也为效率,我也不打算在代码中用到递归。
        一般来说,回溯法属深度优先搜索法,它从问题领域中选取一个状态作为当前节点,进行某一种运算之后,形成下一级的状态,作为节点,再进行某种运算,再形成下下级的状态,作为根据地,再尝试新的节点,直到没有可用的节点了,称为叶子,就判断此时的状态是否满足问题的解。不满足,退回父节点,进行运算,进入下一级的状态,继续深度搜索。如果父节点无法进入新的状态,那么只好退回祖父节点,进行同样的操作。所以回溯算法的关键,在于新状态的运算代码,和各级节点的保存恢复代码。
        再看看24点的问题,为便于行文,假设只有4个数参与运算。先来考察第一级状态的节点数量。首先,从4个数中任意取出两个数,共有C(4,2) = 6 种组合,两个数a和b,利用加减乘除和交换位置,可以凑出6个结果,分别为a+b,a*b,b-a,a/b,a-b,b/a。于是,第一级状态就有36节点。同理类推,第二级状态有C(3,2)*6,第三级状态有C(2,2)*6,没有第四级了,第三级的节点,全部都是叶子,都要判断。这意味着,24点算法中,存在36*18*6片叶子需要判断。此外,24点中,4个数的状态级数为3,可以预料到24点中状态的级数比输入参数的数目少1,你应该知道WHY的。
        由以上分析可知,每一级的状态,由3个参数决定,分别是第1个数a、第2个数b和运算符号。运算符号取值范围为0-5,分别表示a+b,a-b,a*b,a/b,b-a,b/a这6种运算。这3个参数是一个整体,代码中用Step来表示,分别为nFst,nSnd,nOper。
……
        忽略了思考过程,下面简单说明代码结构。CGame24是主类,用以玩出24点游戏的解。其成员函数CalcNextResult()在内部状态中用输入的数构造出一个最终的表达式,这个表达式可能是正确的解,也可能不是。而Play()则通过调用不停地调用CalcNextResult()以尝试得到一个正确的解。Express()则将表达式表示成字符串的形式。m_Nums用以储存原始的输入数据和中间运算结果,其中最后的一个数为表达式的最终运算结果。m_Flags用以指示m_Nums中的数是否已参与表达式中,以阻止同一个数多次进入表达式中。
        于是Step中的nFst,nSnd为m_Nums中的数的索引,很明显,由于是组合关系,所以nSnd必将大于nFst。Step中还有一个nNext的变量,指向的是nSnd的下一个可用的索引,当nOper为最后一种运算时,nSnd就要进入到下一个位置了,也就是被赋予nNext的值。如果nNext没有可用的值时,就表示要改变nFst的下标了。本来nNext的出现是为了将代码写得好看一点而硬造出来的一个变量,但不料在后面,却发挥了很重要的作用,简直是假如没有它,代码就没法编了。
        整片程序的压力全在Step::ToNext()上,它所做的事情,不过是为了使状态进入下一个状态中。但是其实现,却异常复杂,要考虑组合的各种可能的情况,甚至还要考虑除数是否为0。承担了太多的职责,但是我也想不出更好的方式,也不打算再思考了。
        好吧,我也承认代码写得异常糟糕,不过,这只是玩具代码,原本就不愿精雕细刻,它还存在好多不足之处,比如输出结果中,有时会加入多余的括号,这个问题还能解决。然后,它还不够智能,遍历出来的一些解,其本质上看还是相同,这个的解决就很有点难度了。此外,按抽象的观点来看,回溯算法其实相当于一个容器,它的循环遍历叶子节点或者解,可看成迭代器,这种思路,完全可以表达成C++的代码等等。如果读者愿意优化,请将优化后的结果发给在下,在下也很想瞅瞅。其实,我想说的是,就算老夫亲自操刀,也不见得就胜过一众宵小了,惭愧。
        算法这东西,现实中用得很少,高效复杂的算法自然有人在研究,我们只要注意将代码写得清晰一点就好了。不过,话又说回来,经过各种算法狂轰滥炸后的大脑,编出来的代码,貌似比没有经过算法折磨过的人,似乎总是要强一点。
#include <stdio.h>
#include 
<math.h>
#include 
<assert.h>
#include 
<utility>
#include 
<iostream>

using namespace std;

unsigned 
int gcd(unsigned int x, unsigned int y)   
{   
    unsigned  
int  nTimes=0;   
    
for (; 0 == (x&1&& 0 == (y&1); x>>=1, y>>=1)
        
++nTimes;

    
if (x < y)
        swap(x, y);

    
while (y > 0)
    
{
        
for (; 0 == (x & 1 );x >>= 1 )
            ;   

        
if (x < y)
            swap(x, y);
        x 
-= y;
        
if (x < y)
            swap(x, y);
    }

    
return x << nTimes;
}
 


class CRational
{
public:
    CRational(
int nNumberator=0int nDenominator=1)
        : m_nNum(nNumberator), m_nDe(nDenominator)
    
{
        assert(nDenominator 
!= 0);
        standarlize();
    }

    
int Numberator()const return m_nNum;}
    
int Denominator()const return m_nDe;}

    CRational
& operator+=(const CRational& _Right)
    
{
        m_nNum 
= m_nNum*_Right.m_nDe + _Right.m_nNum*m_nDe;
        m_nDe 
*= _Right.m_nDe;
        standarlize();
        
return *this;
    }


    CRational
& operator-=(const CRational& _Right)
    
{
        m_nNum 
= m_nNum*_Right.m_nDe - _Right.m_nNum*m_nDe;
        m_nDe 
*= _Right.m_nDe;
        standarlize();
        
return *this;
    }


    CRational
& operator*=(const CRational& _Right)
    
{
        m_nNum 
*= _Right.m_nNum;
        m_nDe 
*= _Right.m_nDe;
        standarlize();
        
return *this;
    }


    CRational
& operator/=(const CRational& _Right)
    
{
        assert(_Right.Denominator() 
!= 0);
        m_nNum 
*= _Right.m_nDe;
        m_nDe 
*= _Right.m_nNum;
        standarlize();
        
return *this;
    }


private:
    
void standarlize()
    
{
        
if (m_nDe < 0)
        
{
            m_nDe 
= -m_nDe;
            m_nNum 
= -m_nNum;
        }

        
int nGcd = gcd(abs(m_nNum), m_nDe);
        m_nNum 
/= nGcd;
        m_nDe 
/= nGcd;
    }

    
int m_nNum;
    
int m_nDe;
}
;

ostream
& operator << (ostream& outconst CRational& rat)
{
    cout 
<< rat.Numberator();
    
if (rat.Denominator() != 1)
        cout 
<< "/" << rat.Denominator();
    
return out;
}


CRational 
operator-(const CRational& _Left, const CRational& _Right)
{
    CRational _Tmp(_Left);
    
return _Tmp -= _Right;
}


CRational 
operator+(const CRational& _Left, const CRational& _Right)
{
    CRational _Tmp(_Left);
    
return _Tmp += _Right;
}


CRational 
operator*(const CRational& _Left, const CRational& _Right)
{
    CRational _Tmp(_Left);
    
return _Tmp *= _Right;
}


CRational 
operator/(const CRational& _Left, const CRational& _Right)
{
    CRational _Tmp(_Left);
    
return _Tmp /= _Right;
}


bool operator==(const CRational& _Left, const CRational& _Right)
{
    
return _Left.Numberator()==_Right.Numberator() && _Left.Denominator()==_Right.Denominator();
}


enum OperType{ OPER_ADD, OPER_SUB1, OPER_MUL, OPER_DIV1, OPER_SUB2, OPER_DIV2};

const char* g_sOPER_SYMBOL = "+-*/-/";
class CGame24
{
public:
    CGame24(
int nRes, int* pNums, int nLen);

    
bool Play();
    
bool CalcNextResult();
    size_t Express(
char* pExp);

private:
    
struct Step
    
{
        
char nOper;
        
char nFst;
        
char nSnd;
        
char nNext;

        
void ToNext(bool* pFlags, const CRational* pNums, int nMax);

        
bool HasNext(const bool* pFlags, int nMax)
        
{
            
if (nNext >= nMax)
            
{
                
int nCount = 0;
                
for (char i = nFst+1; i < nSnd && nCount<2; i++)
                
{
                    
if (!pFlags[i])
                        nCount
++;
                }

                
return nCount == 2;
            }

            
return true;
        }


        
void Discard(bool* pFlags)
        
{
            pFlags[nFst] 
= false;
            pFlags[nSnd] 
= false;
            nFst 
= 0;
            nSnd 
= 0;
            nNext 
= 0;
        }

    }
;

    size_t buildExpress(
char* pExp, char nStep, char nSuperOper);

    
enum {_nSIZE = 100};
    CRational m_Nums[_nSIZE
*2];
    
bool m_Flags[_nSIZE*2];
    Step m_Steps[_nSIZE];
    
int m_nRes;
    
char m_nLen;
    
char m_nCur;
}
;

void CGame24::Step::ToNext(bool* pFlags, const CRational* pNums, int nMax)
{
    assert(HasNext(pFlags, nMax));
    
if (nNext == nMax)
    
{
        pFlags[nFst] 
= false;
        pFlags[nSnd] 
= false;
        nOper 
= 0;
        nNext 
= 0;
        nFst
++;
        nSnd 
= nFst;
    }

    
if (nFst >= nSnd)
    
{
        
for (; nFst<nMax-1 && pFlags[nFst]; nFst++)
            ;
        nOper 
= 0;
        pFlags[nFst] 
= true;
        nSnd 
= nFst;
        
for (nNext = nFst+1; nNext<nMax && pFlags[nNext]; nNext++)
            ;
        assert (nNext 
!= nMax);
    }


    
if (nNext > nSnd)
    
{
        assert(
!pFlags[nNext]);
        
if (nSnd != nFst)
            pFlags[nSnd] 
= false;
        nSnd 
= nNext;
        pFlags[nSnd] 
= true;
        nOper 
= 0;
        
return;
    }

    nOper
++;
    
if (nOper==OPER_DIV1 && pNums[nSnd].Numberator()==0)
        nOper
++;
    
char nNextOper = nOper+1;
    
if (nNextOper>OPER_MUL)
    
{
        
if (nNextOper == OPER_DIV1 && pNums[nSnd].Numberator()==0)
            nNextOper
++;
        
if (nNextOper == OPER_DIV2 && pNums[nFst].Numberator()==0)
            nNextOper
++;
    }


    
if (nNextOper > OPER_DIV2)
    
{
        
for (nNext=nSnd+1; nNext<nMax && pFlags[nNext]; nNext++)
            ;
    }

}


CRational OperateRationals(
const CRational& fst, const CRational& snd, char nOper)
{
    
switch (nOper)
    
{
    
case OPER_ADD: return fst + snd; 
    
case OPER_SUB1: return fst - snd; 
    
case OPER_SUB2: return snd - fst; 
    
case OPER_MUL: return fst * snd; 

    
case OPER_DIV1: 
        assert (snd.Numberator() 
!= 0);
        
return fst/snd;

    
case OPER_DIV2: 
        assert (fst.Numberator() 
!= 0);
        
return snd/fst;
    }

    assert (
false);
    
return 0;
}


CGame24::CGame24(
int nRes, int* pNums, int nLen)
{
    assert(nLen 
> 0 && nLen < _nSIZE);
    m_nRes 
= nRes;
    
for (int i=0; i<nLen; i++)
        m_Nums[i] 
= pNums[i];
    memset(m_Flags, 
0sizeof(m_Flags));
    memset(m_Steps, 
0sizeof(m_Steps));
    m_nLen 
= static_cast<char>(nLen);
    m_nCur 
= 0;
}


bool CGame24::CalcNextResult()
{
    
while (m_nCur >= 0 && !m_Steps[m_nCur].HasNext(m_Flags, m_nLen+m_nCur))
        m_Steps[m_nCur
--].Discard(m_Flags);
    
if (m_nCur < 0)
        
return false;

    
while (m_nCur < m_nLen-1)
    
{
        m_Steps[m_nCur].ToNext(m_Flags, m_Nums, m_nLen
+m_nCur);
        
const Step& step = m_Steps[m_nCur];
        m_Nums[m_nLen
+m_nCur] = OperateRationals(m_Nums[step.nFst], m_Nums[step.nSnd], step.nOper);
        m_nCur
++;
    }

    m_nCur
--;

    
return true;
}


bool CGame24::Play()
{
    
while (CalcNextResult())
    
{
        
if (m_Nums[m_nLen+m_nCur] == m_nRes)
            
return true;
    }

    
return false;
}


size_t CGame24::Express(
char* pExp)
{
    size_t len 
= buildExpress(pExp, m_nCur, OPER_ADD); // 加法的运算级别最低
    pExp[len] = 0;
    
return len;
}


bool NeedParentheses(char nSuperOper, char nSubOper)
{
    assert(nSuperOper 
<= OPER_DIV2);
    assert(nSubOper 
<= OPER_DIV2);
    
static const char g_ACTUAL_OPER[] = {OPER_ADD, OPER_SUB1, OPER_MUL, OPER_DIV1, OPER_SUB1, OPER_DIV1};
    nSuperOper 
= g_ACTUAL_OPER[nSuperOper];
    nSubOper 
= g_ACTUAL_OPER[nSubOper];
    
return (nSuperOper>nSubOper) || (nSuperOper==nSubOper && (nSubOper==OPER_SUB1 || nSuperOper==OPER_DIV1));
}


size_t CGame24::buildExpress(
char* pExp, char nStep, char nSuperOper)
{
    assert(nStep 
<= m_nCur);
    
char* sPos = pExp;
    
const Step& step = m_Steps[nStep];
    
char nFst = step.nFst;
    
char nSnd = step.nSnd;
    
char nOper = step.nOper;
    
if(step.nOper==OPER_SUB2 || step.nOper==OPER_DIV2)
        swap(nFst, nSnd);

    
bool bParentheses = NeedParentheses(nSuperOper, nOper);
    
if (bParentheses)
        
*sPos++ = '(';
    
if (nFst >= m_nLen)
        sPos 
+= buildExpress(sPos, nFst-m_nLen, nOper);
    
else
        sPos 
+= sprintf(sPos, ("%d"), m_Nums[nFst].Numberator());

    
*sPos++ = g_sOPER_SYMBOL[nOper];

    
if (nSnd >= m_nLen)
        sPos 
+= buildExpress(sPos, nSnd-m_nLen, nOper);
    
else
        sPos 
+= sprintf(sPos, ("%d"), m_Nums[nSnd].Numberator());

    
if (bParentheses)
        
*sPos++ = ')';
    
return sPos-pExp;
}


int main()
{
    
char sExpress[256= 0 };
    
int Nums[] = {12345};
    CGame24 game(
24, Nums, 5);
    
while (game.Play())
    
{
        game.Express(sExpress);
        cout 
<< sExpress << endl;
    }

    
return 0;
}

posted on 2012-06-07 16:20 华夏之火 阅读(1700) 评论(1)  编辑 收藏 引用 所属分类: 玩具代码

评论

# re: 玩具代码 24点游戏 2012-06-15 14:29 ss

可以运行吗  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜