程式設計之美—24點遊戲

問題：給4張牌，每張的面值在1—13之間，允許其中數值相同的牌。采用加、減、乘、除四則運算，允許中間運算存在小數，并且可以使用括号，但每張牌隻能使用一次，嘗試構造一個多項式，使其運算結果為24。

 本文主要講如何使用動态規劃實作，給定4個數：A={a0，a1，a2，a3}。采用4位二進制表示集合，當且僅當ai在某一個子集中時，該子集所代表的二進制數對應的第i位為1，否則為0，比如A1={a1，a2，a3}，則1110代表A1，總共需要1到2^n-1表示所有的子集，包括A自身。是以不妨設S表示所有子集所有的運算結果。比如：s[3]表示A3={a0，a1}的運算，s[3]中存儲{a0+a1、a0-a1、a1-a0、a0*a1、a0/a1、a1/a0}。s[1]={a0}、s[2]={a1}、s[4]={a2}、s[8]={a3}。對于{a0,a1,a2}—>{a0}+{a1，a2}、{a1}+{a0，a2}、{a2}+{a0，a1}，即：s[1]中元素與s[6]中元素進行加、減、乘、除六種的運算，結果存儲在s[7]中，同樣s[2]與s[5]，s[3]與s[4]，這樣就完成了{a0,a1,a2}所有的可能組合表達式的運算。其它的依次類推。自底向上計算，s[15]中存儲{a0，a1，a2，a3}所有可能的組合表達式的結果，隻要周遊s[15]中結果為24的表達式将其輸出，就可以找到所有滿足結果為24的表達式。具體過程詳見程式設計之美，這裡隻是講解程式是如何實作的。

game24.h

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Game
{
public:
	void insert(int x);
	void start();
	void Find(int k);
	void Fork(int a,int b);
	void show();
private:
	vector<int> c;
	vector<vector<double> > s;
	vector<vector<string> > result;
};
           

game24.cpp

#include"stdafx.h"
#include"game24.h"
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;

void Game::insert(int x)
{
	c.push_back(x);
}
void Game::start()
{
	int n=c.size();
	int m=pow(2,(double)n);
	s.resize(m);//其中s[0]不使用
	result.resize(m);
	for(int i=0;i<n;i++)
	{
		char buffer[20];
		s[pow(2,(double)i)].push_back(c[i]);
		_itoa_s(c[i],buffer,10);
		result[pow(2,(double)i)].push_back(buffer);
	}
	for(int i=1;i<m;i++)
		Find(i);
}
void Game::Find(int k)
{
	if(!s[k].empty())
		return ;
	for(int i=1;i<k;i++)
	{
		int t=i&k;
		if((t==i)&&(i<k-i))//i&k=i時,i才為k的子集，比如，k=0101，隻有i=0001、0100才是其子集k=0101
			Fork(i,k-i);   //代表A5={a2，a0}其子集隻有{a2}、{a0}，其它不滿足
	}
}
void Game::Fork(int a,int b)
{
	string str;
	int n1=s[a].size();
	int n2=s[b].size();
	for(int i=0;i<n1;i++)
		for(int j=0;j<n2;j++)
		{
			s[a+b].push_back(s[a][i]+s[b][j]);
			str='('+result[a][i]+'+'+result[b][j]+')';
			result[a+b].push_back(str);


			s[a+b].push_back(s[a][i]-s[b][j]);
			s[a+b].push_back(s[b][j]-s[a][i]);
			str='('+result[a][i]+'-'+result[b][j]+')';
			result[a+b].push_back(str);
			str='('+result[b][j]+'-'+result[a][i]+')';
			result[a+b].push_back(str);



			s[a+b].push_back(s[a][i]*s[b][j]);
			str='('+result[a][i]+'*'+result[b][j]+')';
			result[a+b].push_back(str);


			if(s[b][j]!=0)
			{
				s[a+b].push_back(s[a][i]/s[b][j]);
				str='('+result[a][i]+'/'+result[b][j]+')';
			    result[a+b].push_back(str);
			}
			if(s[a][i]!=0)
			{
				s[a+b].push_back(s[b][j]/s[a][i]);
				str='('+result[b][j]+'/'+result[a][i]+')';
			    result[a+b].push_back(str);
			}
		}
}
void Game::show()
{
	start();
	int m=c.size();
	int k=pow(2,(double)m)-1;
	int n=s[k].size();
	vector<string> s1;
	for(int i=0;i<n;i++)
		if(fabs(s[k][i]-24)<1E-6)
		{
			if(s1.empty())
			{
            cout<<result[k][i]<<"=24"<<endl;
			s1.push_back(result[k][i]);
			cout<<endl;
			}
			int n1=s1.size();
			for(int j=0;j<n1;j++)
			{
				if(result[k][i]!=s1[j])
				{
				cout<<result[k][i]<<"=24"<<endl;
				cout<<endl;
				}
			}
		}
}
           

Beauty-24dynamic.cpp

// Beauty-24dynamic.cpp : 定義控制台應用程式的入口點。
//
//程式設計之美：24點遊戲，分治算法和動态規劃思想
#include "stdafx.h"
#include"game24.h"
#include<iostream>
#include<vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{

	Game g;
	cout<<"Input numbers:"<<endl;
	for(int i=0;i<4;i++)
	{
		int x;
		cin>>x;
		g.insert(x);
	}
	g.show();
	return 0;
}