主题：【原创】将24进行到底 -- 泰让
这是答应过面壁同学的c原码，因为周末在玩新买的电视，加上犯懒，所以晚了.
稍后将给出算法的解释.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define TAGET 24
#define NOP 4
#define EOP NOP*2-1
int comp[EOP];
double op[NOP];
int validate(void ){
int top=0;
double stack[NOP];
int i=0;
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
stack[top]=op[comp[i]-1];
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
stack[top-1]+=stack[top];
break;
case 2:
top--;
stack[top-1]-=stack[top];
break;
case 3:
top--;
stack[top-1]*=stack[top];
break;
case 4:
top--;
if (stack[top]==0)
return 0;
stack[top-1]/=stack[top];
break;
}
}
}
if (fabs(stack[0]-TAGET)<=1e-5)
return 1;
else
return 0;
}
void output(void ) {
int i;
int top=0;
char* stack[EOP];
char tempstr[255];
for (i=0;i<EOP;i++) {
stack[i]=malloc(255*sizeof(char));
}
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
sprintf(stack[top]," %d ",(int)op[comp[i]-1]);
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
sprintf(tempstr,"(%s+%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 2:
top--;
sprintf(tempstr,"(%s-%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 3:
top--;
sprintf(tempstr,"(%s*%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 4:
top--;
sprintf(tempstr,"(%s/%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
}
}
}
printf("%s\n",stack[0]);
for (i=0;i<EOP;i++) {
free(stack[i]);
}
}
int expandable(int i, int j){
int repeat=0;
int k;
if (j<=NOP) {
repeat=0;
for (k=0;k<=i-1;k++)
if (comp[k]==j) {
return 0;
}
}
int op=0;
int act=0;
for (k=0;k<=i-1;k++) {
if (comp[k]<=NOP)
op++;
else
act++;
if (op<act)
return 0;
}
return 1;
}
void expand(int i) {
int j;
if (i==EOP){
if (validate())
output();
}
else {
for (j=1;j<=NOP+4;j++) {
if (expandable(i+1,j)==1) {
comp[i]=j;
expand(i+1);
}
}
}
}
int main(int argc,char **argv) {
int a;
int i;
for (i=0;i<=(NOP-1);i++) {
scanf("%d",&a);
op[i]=a;
}
expand(0);
}
本帖一共被 1 帖 引用 (帖内工具实现)
你的程序我编译运行了一下，四张牌是没有什么问题的。但是我牌数改为6，Target改为5188，程序就似乎没有解了。你能看一下这个问题吗？
我改动了你程序中的两个常量
#define TAGET 5188
#define NOP 6
这里是程序运行结果
错误原因在第9行
double op[4];
这个magic number 4应该改成NOP
应该是
我这段时间也再想这个问题
算出结果不难，但是要考虑交换律和结合律还是要费点工夫
楼主的程序显然没有考虑交换律的问题，屏幕上打印出的结果实际上是同一个
还是烦请老兄再添点儿注解，这样应该更能领会得深一些
谢谢了。
另外，我这VC编译器上只能这样才行：59行：stack[i]=(char*)malloc(255*sizeof(char));
首先说一下总体上的思路。其实很多朋友已经看出，如果想穷尽4张牌的所有可能的计算，需要找到一个排列方法，能够不遗漏的列举每个算式。运算的数好办，因为它们都只严格的出现1次，问题是对于运算符，简单的插入三个运算符在四个数的空隙中是不行的，因为要是我们加入括号改变运算顺序，其结果也就不同了。但是如果我们要考虑所有插入括号的方式，虽然仍然是可行，但问题就变的相当复杂了。
好在算术表达式不仅仅有常见的中缀法，还有后缀法，或者称为逆波兰法（RPN）。这种方法先写两个参加运算的部分（可以是数，或者小一极的表达式）。简单的说就是原本用1＋2来表示的运算，写成rpn就是1 2＋，再比如说我们用中缀表示的算式(4-4/7）*7用后缀可以表示成4 4 7 / - 7 *。注意我们这里假定运算数间有可分辨的分隔，这样4 ，4 ，7三个数不至于同四百四十七混淆。
这样表示有什么好处？第一：这么写以后可以不用括号表达所有算式，而如果我们把一个数看作一位，一个运算符也看作1位的话，这个表达式长度总是7位。第二：这样写后计算过程简单。对于有括号的四则运算的解析和运算其实是相当复杂的问题，编译原理中会有一章专门讲这个问题。对于RPN计算就简单很多，我们可以很机械的执行以下步骤：遇到运算数则压栈，如果遇到运算符则将栈顶两运算数进行相应操作。最后如果RPN没有语法错误的话，栈应该只剩下一个数，就是结果。
回到原本的问题，我们现在要做的就是生成所有可能的RPN,然后运算之，检查它是否结果是24。如果我们用1到4代表输入的4张牌点，5到8代表加减乘除四种运算的话，问题就变成了我们如何生成一个7个数的组合，满足以下条件：
1：一到四出现1次且仅出现一次
2：五到八可以重复出现，也可以不出现
3：在任何时候，一到四出现的总数，比五到八出现的次数多（这一条是保证生成的是合乎语法的RPN）
生成了一个组合后，再用上面说的计算方法来算出结果，检查下是否是目标就可以了。当然注意运算过程中别发生除零的错误。
有了思路后编程就不是很难的事情，下面对代码本身解释一下：
comp数组是存放组合的，op数组存放输入的四张牌点。validate函数计算已经生成的7位排列是否算出目标值,output把comp的逆波兰转化成熟悉的中缀表示法。注意这两个函数很象，只不过一个算浮点，另一个算字符串而已。
expand和expandable是生成排列的主体，其中expand用递归的办法从左向右试探comp的每一位，如果7位全部填完则调用validate和output输出结果。而expandable函数则试探在特定的位置上是否可以放置特定的数。其中第一个循环判断条件1（运算数出现最多1次），第二个循环测试条件3（从左往右扫描的时候运算数总比运算符多）。当试探成功后则在comp数组相应位置放上这个数，由于是递归，回溯可以自动进行。
程序应该可以在大多数c编译器上通过。我用的是windows 下的LCC和linux下的gcc。由于目标和牌数都定义成常量，所以容易改动，以解决更多张牌或者不同目标数的情况，也可以把它们定义成用户输入的变量。
虽然我知道比较不同语言的程序运行速度意义不大，可还是忍不住大致做了下测试。对于跑完全部4张牌的情况，在赛扬2.4G Windows XP SP2.0下大概需要9秒钟左右。同样的Binary在另一台双核1.8G笔记本上速度约7秒。当然，程序没有用到任何多线程的东西，所以在双核下没有太多的优势。
我的下门考试已经看到了曙光，所以继续学习两位老兄的Codes。
俺的程序改用了递归，输出依然还是问题。
为了学习方便，两位老兄是否考虑几个验算输出。即：任意4个数，如果有解，最多有多少个解？或者说，A+B,B+A算2个解，简单的全排列一下，总共有多少个解才不会有漏掉的排列？
俺用泰让兄的程序算了一下，1 3 5 4（52个解），1 5 5 5（12个解），4 4 7 7（8个解）。
仔细考虑了一下，这个想法完全没有必要！
你可以自己在上面根据你的需要更改。怎么样？
想学习学习multi－threading部分
这里是多线程部分。用了一些JDK 5.0以后的new feature，所以可能看起来有些“异怪”。加了很简单一些注释，希望能有点小小帮助。
package game;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
/**
* This one has ability to scale up to multiple CPUs. It is
* subclass of plain version of PokerGame
*/
public class PokerGameMT extends PokerGame
{
//uses the latest Java concurrent feature--Thread pool
private final ExecutorService pool =
Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
private final Object OBJ = new Object();
/**
* Inner class, do real calculation job. Basically it is just another
* way to execute calculate() function defined in base class
*/
private class Runner implements Runnable
{
private int[] set;
private Map<String, Object> solutions;
private CountDownLatch latch;
Runner(int[] set, Map<String, Object> solutions, CountDownLatch latch)
{
this.set = set;
this.solutions = solutions;
this.latch = latch;
}
public void run()
{
for (Operator[] opCombo : opCombos)
{
Set<int[]> calcSeq = PokerGameMT.this.getCalcSequence(opCombo);
for (int[] seq : calcSeq)
{
String solution = PokerGameMT.this.calculate(set, opCombo, seq);
if (solution != null)
{
solutions.put(solution, OBJ);
}
}
}
latch.countDown();
}
}
/**
* Given a number of poker, find the total sulotions
*/
protected Set<String> findSolution(int[] nums)
{
/**
* use ConcurrentHashMap is for performance reason. Otherwise,
* Set<String> would be just fine.
*/
Map<String, Object> solutions = new ConcurrentHashMap<String, Object>();
Map<Integer, int[]> workingSet = new ConcurrentHashMap<Integer, int[]>();
int[] aPokeSet = new int[nums.length];
for(int[] set : this.permutations)
{
for (int i = 0; i < nums.length; i++)
{
aPokeSet[i] = nums[set[i]];
}
/**
* avoid duplication calculation. Only different set
* is sent to runner threads.
*/
int code = this.getPokeHashCode(aPokeSet);
if (!workingSet.containsKey(code))
{
int[] aCalcset = new int[nums.length];
System.arraycopy(aPokeSet, 0, aCalcset, 0, nums.length);
workingSet.put(code, aCalcset);
}
}
int totalPerm = workingSet.size();
//new feature of JDK 5.0 or after. Just like old join()
CountDownLatch latch = new CountDownLatch(totalPerm);
//submit job to runner thread
for(int[] set : workingSet.values())
{
pool.execute(new Runner(set, solutions, latch));
}
try
{
//wait for runner finish calculation
latch.await();
}catch(InterruptedException ex)
{
ex.printStackTrace();
}
return solutions.keySet();
}
/**
* tear down the thread pool
*/
protected void close()
{
super.close();
pool.shutdownNow();
}
/**
* Constructor. first one specify poke number and
* second one specify expected value, 24 for instance
* @param pokeNum
* @param answer
*/
public PokerGameMT(int pokeNum, int answer)
{
super(pokeNum, answer);
}
}
俺这个算法还没搞定，又是多线程
，哎，谁教俺面壁是出了名的慢。不过，嘿嘿，出题权还在俺!
忙活了一个星期天，参照highway兄得输出办法，终于把输出解决了，但程序已经惨不忍睹。早知花上一个周末，还不如把逆波兰表达式吃透。不敢再玩了，就先这样吧。这个程序如果没有输出的问题，我认为这个算法还是很不错的。4个数两两相运算，变成3个数，再两两相运算，变成2个数，最后得结果。如果没有输出，适用N个数。
#include<iostream>
#include<vector>
using namespace std;
#define N 4
int z = 0,k1=0,k2=0;
vector<double> Operand(4);
vector<int> Operator(3);
void print(vector<double> A,vector<int> op,int i);
void PRINT(vector<double> A,vector<int> op,int i); // (a#b)#(c#d)
void print_op(int i)
{
switch (i)
{
case 0 : cout<<" + "; break;
case 1 : cout<<" - "; break;
case 2 : cout<<" * "; break;
case 3 : cout<<" / "; break;
case 4 : cout<<" - "; break;
case 5 : cout<<" / "; break;
}
}
inline double operation(const double x,const double y,int i)
{
double res;
switch (i)
{
case 0 : res = x + y; break;
case 1 : res = x - y; break;
case 2 : res = x * y; break;
case 3 : res = x / y; break;
case 4 : res = y - x; break;
case 5 : res = y / x; break;
}
return res;
}
inline void rechnen(vector<double> a,int n)
{
if (n==2) // Rekursion end
{
for (int i=0;i<6;i++)
{
if (operation(a[0],a[1],i)==24.0)
{
z++;
int k3=0; if (i>3) k3++;
Operator[2]=i;
print(Operand,Operator,k1+k2+k3); cout<<endl;
break; // z.B. a+b=24, a#b(b#a)!=24
}
}
}
else
{
vector<double> b(n-1);
for (int u=0;u<n;u++)
{
for (int v=u+1;v<n;v++)
{
if (n==4) { Operand[0]=a[u]; Operand[1]=a[v]; }
if (n==3) { Operand[2]=a[v-u]; Operand[3]=a[3-v+u]; }
// A, B, C, D
for (int i=0,j=1;j<n-1;i++)
{ if (i!=u&&i!=v) b[j++]=a[i]; }
// "n=4" b[1],b[2]
// "n=3" b[1]
for (int i=0;i<6;i++)
{
Operator[4-n]=i;
// op[0], op[1]
b[0]=operation(a[u],a[v],i);
if (i>3) { if (n==4) k1=4; if (n==3) k2=2; }
if (n==3&&u==1)
// (a#b)#(c#d)
{
for (int i=0;i<6;i++)
{
if (operation(b[1],b[0],i)==24.0)
{
z++;
int k3=0; if (i>3) k3++;
Operator[2]=i;
PRINT(Operand,Operator,k1+k2+k3);
cout<<endl; break;
}
}
}
else rechnen(b,n-1);
k2=0;
if (n==4) k1=0;
}
}
}
}
}
int main()
{
while (1)
{
double f; vector<double> a(N);
cout<<"give me "<<N<<" nummer, please:"<<endl;
for (int i=0;i<N&&cin>>f;i++) a[i]=f;
// for (int i=0;i<4;i++) cout<<a[i]<<' ';
rechnen(a,N);
cout<<"\nso there are "<<z<<" kinds of ideas.\n\n";
}
return 0;
}
1 3 5 4 有12个结果，4 4 7 7 有4个结果， 1 5 5 5 有6个结果。
void print(vector<double> A,vector<int> op,int i)
{
if (i==4||i==5||i==6||i==7) { swap(A[0],A[1]); i=i-4; }
switch (i)
{
case 0 : cout<<"(("<<A[0]; print_op(op[0]); cout<<A[1]<<')';
print_op(op[1]); cout<<A[2]<<')';
print_op(op[2]); cout<<A[3]; break;
// ((A#B)#C)#D
case 1 : cout<<A[3]; print_op(op[2]);
cout<<"(("<<A[0]; print_op(op[0]); cout<<A[1]<<')';
print_op(op[1]); cout<<A[2]<<')'; break;
// D#((A#B)#C)
case 2 : cout<<'('<<A[2]; print_op(op[1]);
cout<<'('<<A[0]; print_op(op[0]); cout<<A[1]<<"))";
print_op(op[2]); cout<<A[3]; break;
// (C#(A#B))#D
case 3 : cout<<A[3]; print_op(op[2]);
cout<<'('<<A[2]; print_op(op[1]);
cout<<'('<<A[0]; print_op(op[0]); cout<<A[1]<<"))"; break;
// D#(C#(A#B))
}
}
void PRINT(vector<double> A,vector<int> op,int i)
{
if (i==4||i==5||i==6||i==7) swap(A[0],A[1]);
if (i==2||i==3||i==6||i==7) swap(A[2],A[3]);
if (i%2==0)
{
cout<<'('<<A[0]; print_op(op[0]); cout<<A[1]<<')';
print_op(op[2]);
cout<<'('<<A[2]; print_op(op[1]); cout<<A[3]<<')';
// (A#B)#(C#D)
}
else
{
cout<<'('<<A[2]; print_op(op[1]); cout<<A[3]<<')';
print_op(op[2]);
cout<<'('<<A[0]; print_op(op[0]); cout<<A[1]<<')';
// (C#D)#(A#B)
}
}