24点算法的Java版和C语言版源码

guohui0522

贡献于2012-03-12

字数:6538 关键词: Java开发 Java

24点算法的Java版和C语言版源码 Java版共2个类:Application.java 和 Node.java == Application.java== package num24; public class Application { double num[] = new double[4]; boolean mark[] = new boolean[4]; /** * 获得k个数运算,结果为result的第一个Node,比如get(24,4) * @param result * @param n * @return */ public Node get(double result, int n) { Node left = null, right = null; if (n <= 0) { return null; } //如果个数小于0,返回空 for (int i = 0; i < 4; i++) { if (mark[i]) { continue; //如果已经打上标志,继续找下一个 } mark[i] = true; //如果没有打标志,就打上标志,并且对其进行处理 //如果只有一个数并且这个数就是给出的结果,就返回一个只有一个数的节点 if (result == num[i] && n == 1) { return new Node(num[i]); } left = get(result - num[i], n - 1); if (left != null) { return new Node(0.0, "+", left, new Node(num[i])); } left = get(result + num[i], n - 1); if (left != null) { return new Node(0.0, "-", left, new Node(num[i])); } left = get(result * num[i], n - 1); if (left != null) { return new Node(0.0, "/", left, new Node(num[i])); } if (Math.abs(num[i]) > 1e-10) { left = get(result / num[i], n - 1); if (left != null) { return new Node(0.0, "*", left, new Node(num[i])); } } for (int j = 0; j < 4; j++) { if (mark[j]) { continue; } mark[j] = true; if (result == num[i] * num[j] && n == 2) { //a*b return new Node(0.0, "*", new Node(num[i]), new Node(num[j])); } left = get(result + num[i] * num[j], n - 2); //a*b-(c?d)=result if (left != null) { right = new Node(0.0, "*", new Node(num[i]), new Node(num[j])); return new Node(0.0, "-", left, right); } left = get(result - num[i] * num[j], n - 2); //a*b+(c?d)=result if (left != null) { right = new Node(0.0, "*", new Node(num[i]), new Node(num[j])); return new Node(0.0, "+", left, right); } if (Math.abs(num[j]) > 1e-10) { if (result == num[i] / num[j] && n == 2) { return new Node(0.0, "/", new Node(num[i]), new Node(num[j])); } left = get(result + num[i] / num[j], n - 2); //a/b-(c?d)=result==>c?d=result+a/b if (left != null) { right = new Node(0.0, "/", new Node(num[i]), new Node(num[j])); return new Node(0.0, "-", left, right); } left = get(result - num[i] / num[j], n - 2); if (left != null) { right = new Node(0.0, "/", new Node(num[i]), new Node(num[j])); return new Node(0.0, "+", left, right); } } if(result==num[i]-num[j]&&n==2){ return new Node(0.0,"-",new Node(num[i]),new Node(num[j])); } if(Math.abs(num[i]-num[j])>1e-10){ left=get(result/(num[i]-num[j]),n-2); if(left!=null){ right=new Node(0.0,"-",new Node(num[i]),new Node(num[j])); return new Node(0.0,"*",left,right); } } mark[j]=false; } //end for(int j... mark[i]=false; } //end for(int i... return null; } public void output(Node node) { if (node == null) { return; } if (node.left != null) { if ( (node.left.name.equals("+") || node.left.name.equals("-")) && (node.name.equals("*") || node.name.equals("/"))) { System.out.print("("); output(node.left); System.out.print(")"); } else { output(node.left); } } if (!node.name.trim().equals("")) { System.out.print(node.name); } else { System.out.print(node.num); } if (node.right != null) { if ( (node.right.name.equals("+") || node.right.name.equals("-")) && (node.name.equals("*") || node.name.equals("/")) || (node.right.name.equals("+") || node.right.name.equals("-")) && (node.name.equals("-")) || (!node.right.name.trim().equals("")) && (node.name.equals("/")) ) { System.out.print("("); output(node.right); System.out.print(")"); } else { output(node.right); } } } /** * * @param args */ public static void main(String[] args) { Application app=new Application(); app.num[0]=Double.parseDouble(args[0]); app.num[1]=Double.parseDouble(args[1]); app.num[2]=Double.parseDouble(args[2]); app.num[3]=Double.parseDouble(args[3]); double result; Node tree=null; //while(true){ result=24.0; // if(result==-1.0)break; app.mark[0]=false; app.mark[1]=false; app.mark[2]=false; app.mark[3]=false; tree=app.get(result,4); if(tree!=null){ app.output(tree); System.out.println("="+result); }else{ System.out.println("No!"); } //} } } ===Node.java=== package num24; public class Node { public double num; String name; Node left, right = null; public Node() { num = 0.0; name = " "; left = right = null; } public Node(double aNum){ this(aNum," ",null,null); } public Node(double aNum, String aName, Node aLeft, Node aRight) { num = aNum; name = aName; left = aLeft; right = aRight; } public void delete(){ if(left!=null){ left.delete(); } if(right!=null){ right.delete(); } left=null; right=null; } } C 语言版 //用二叉树保存表达式,输出无多余括号。 #include #include #include using namespace std; double n[4]; bool mark[4]; class node { public: double num; char c; node *left,*right; node() { num=0.0;c=' ';left=right=NULL; } node(double x,char ch=' ',node *l=NULL,node *r=NULL) { num=x;c=ch;left=l;right=r; }; void del() { if(left!=NULL) left->del(); if(right!=NULL) right->del(); delete(left); delete(right); } ~node() { del(); } }; //获得k个数运算,结果为r的node //get(24,4) node *get(double r,int k) { int i,j; node *lc,*rc; if(k<=0) return NULL; for(i=0;i<4;i++) { if(mark[i]) continue; mark[i]=true; if(r==n[i]&&k==1) { return new node(n[i]); } lc=get(r-n[i],k-1); if(lc!=NULL) { return new node(0.0,'+',lc,new node(n[i])); } lc=get(r+n[i],k-1); if(lc!=NULL) { return new node(0.0,'-',lc,new node(n[i])); } lc=get(r*n[i],k-1); if(lc!=NULL) { return new node(0.0,'/',lc,new node(n[i])); } if(fabs(n[i])>1e-10) { lc=get(r/n[i],k-1); if(lc!=NULL) { return new node(0.0,'*',lc,new node(n[i])); } } for(j=0;j<4;j++) { if(mark[j]) continue; mark[j]=true; if(r==n[i]*n[j]&&k==2) { return new node(0.0,'*',new node(n[i]),new node(n[j])); } lc=get(r+n[i]*n[j],k-2); if(lc!=NULL) { rc=new node(0.0,'*',new node(n[i]),new node(n[j])); return new node(0.0,'-',lc,rc); } lc=get(r-n[i]*n[j],k-2); if(lc!=NULL) { rc=new node(0.0,'*',new node(n[i]),new node(n[j])); return new node(0.0,'+',lc,rc); } if(fabs(n[j])>1e-10){ if(r==n[i]/n[j]&&k==2){ return new node(0.0,'/',new node(n[i]),new node(n[j])); } lc=get(r+n[i]/n[j],k-2); if(lc!=NULL){ rc=new node(0.0,'/',new node(n[i]),new node(n[j])); return new node(0.0,'-',lc,rc); } lc=get(r-n[i]/n[j],k-2); if(lc!=NULL) { rc=new node(0.0,'/',new node(n[i]),new node(n[j])); return new node(0.0,'+',lc,rc); } } if(r==n[i]+n[j]&&k==2){ return new node(0.0,'+',new node(n[i]),new node(n[j])); } if(fabs(n[i]+n[j])>1e-10) { lc=get(r/(n[i]+n[j]),k-2); if(lc!=NULL) { rc=new node(0.0,'+',new node(n[i]),new node(n[j])); return new node(0.0,'*',lc,rc); } } if(r==n[i]-n[j]&&k==2){ return new node(0.0,'-',new node(n[i]),new node(n[j])); } if(fabs(n[i]-n[j])>1e-10) { lc=get(r/(n[i]-n[j]),k-2); if(lc!=NULL) { rc=new node(0.0,'-',new node(n[i]),new node(n[j])); return new node(0.0,'*',lc,rc); } } mark[j]=false; } mark[i]=false; } return NULL; } void output(node* T) { if(T==NULL) return; if(T->left!=NULL) { if((T->left->c=='+'||T->left->c=='-')&&(T->c=='*'||T->c=='/')) { cout<<'('; output(T->left); cout<<')'; } else output(T->left); } if(T->c!=' ') cout<c; else cout<num; if(T->right!=NULL) { if( (T->right->c=='+'||T->right->c=='-')&&(T->c=='*'||T->c=='/')|| (T->right->c=='+'||T->right->c=='-')&&(T->c=='-')|| (T->right->c!=' ')&&(T->c=='/') ) { cout<<'('; output(T->right); cout<<')'; } else output(T->right); } } int main() { double result; node* Tree; for(;cin>>n[0]>>n[1]>>n[2]>>n[3];) { result=24.0; if(result==-1.0)break; memset(mark,false,sizeof(mark)); Tree=get(result,4); if(Tree!=NULL) { output(Tree); cout<<'='<

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ]
2 人已下载

下载文档

相关文档