数字游戏-算法.doc

运行结果： 初始状态： 点击运行后的结果首先：默认结果为20（可以指定），默认数字字符为1234567890（可以指定）第二次：手工指定结果为30，字符为123456789（可以为其他）源代码如下：三个类介绍如下：节点类：Node核心算法类：NumberGame界面启动类：ComposeDisplay在NumberGame中解决该问题运用了数据结构和算法的知识。创建树，对树进行先序、中序遍历（DFS），以及对树的广度遍历（BFS）。共分为 3 个类：=节点类=package com.clb.tree;import java.util.List;public class Node private Object data;private List listNodes;public Object getData() return data;public void setData(Object data) this.data = data;public List getListNodes() return listNodes;public void setListNodes(List listNodes) this.listNodes = listNodes;public Node() super();public Node(Object data, List listNodes) super();this.data = data;this.listNodes = listNodes;=核心算法类=package com.clb.tree;import java.math.BigDecimal;import java.util.ArrayList;import java.util.List;/* * 在=的左边的数字间加入+，-或 ，使得以下等式成立 * 1 2 3 4 5 6 7 8 9 0=20 * author Administrator * */public class NumberGame private int nums =1, 2, 3, 4, 5, 6, 7, 8, 9, 0;private char chs = +, -, ;/* * 创建完全树 * 如：（用*代表空格） * (空节点) * 1 * + - * * 2 2 2 * + - * + - * + - * * 3 3 3 3 3 3 3 3 3 * + - * * * * param tree * param index * return */public Node createTree(Node tree, int index)if(index = nums.length)return null;List listNodes = tree.getListNodes();/* * 创建数字1为例外，即树中的第一个节点 */if(index=0)Node newnode = new Node(numsindex, new ArrayList();listNodes.add(newnode);tree.setListNodes(listNodes);createTree(newnode, +index);else/* * 之后以加入符号和下一个数字为一个组合构建剩余的树，即每次构建两层 */创建一个数字节点，以备将该节点准备接到上一个字符节点中，该数字节点将作为下次构建树的根节点Node numNode = new Node(numsindex, new ArrayList();/为根节点中加入三个字符节点及下个数字根节点for (int k = 0; k chs.length; k+) List chListNode = new ArrayList();chListNode.add(numNode);/创建一个字符节点,并将数字节点接到该字符节点中来Node chNode = new Node(chsk, chListNode);/将该字符节点加入到根节点集合中，构建树过程listNodes.add(chNode);createTree(numNode, +index);return tree;ListList DFSResult = new ArrayListList();/save the all possible resultsList rs = new ArrayList();/* * DFS遍历树（遍历所有的可能结果从根节点到每个叶子节点的所有路径） * 该方法仅适用于此题类型(完全树叶子节点均在最后一层) * param tree */public ListList DFSAllResult(Node tree)List listNodes = tree.getListNodes();if(listNodes = null | listNodes.size() = 0)/当该节点为叶子节点时List temp = new ArrayList();/保存最后一次DFSResult中的值if(DFSResult.size() tempSize-1-rs.size(); k-)temp.remove(k);temp.addAll(rs);DFSResult.add(temp);rs.clear();/利用先序遍历树的方式进行遍历for (int i = 0; i listNodes.size(); i+) rs.add(listNodes.get(i);DFSAllResult(listNodes.get(i);return DFSResult;/* * 根据给定的字符串表达式，计算是否能计算得到预计结果 * 如表达式为：1-2+3 4 5 6 7+8-9 0 * param exp * return */public long calc(String exp)long rs = Long.MIN_VALUE;if(exp = null | exp.length()=0)return rs;String firstValue = 0;String sencondValue = 0;char mark = 0;int length = 0;if(exp.charAt(length) = -)mark=-;length+;if(exp.charAt(length) = +)mark=+;length+;doif(mark != 0 & (exp.charAt(length) = + | exp.charAt(length) = -)if(mark = +)firstValue = String.valueOf(Long.parseLong(firstValue) + Long.parseLong(sencondValue);else if(mark = -)firstValue = String.valueOf(Long.parseLong(firstValue) - Long.parseLong(sencondValue);sencondValue = ;mark = exp.charAt(length);continue;switch(exp.charAt(length)case +:mark = +;break;case -:mark = -;break;case :break;case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:case 0:if(mark = 0)firstValue += exp.charAt(length);elsesencondValue += exp.charAt(length);while(+length 0)firstValue = firstValue.charAt(0)=0?firstValue.substring(1):firstValue;tryif(!firstValue.equals()rs = Long.parseLong(firstValue);catch(Exception e)e.printStackTrace();return Long.MAX_VALUE;return rs;/* * 返回所有的结果 * return */public List getAllResults(int arrays, char marks, long preresult)this.nums = arrays;this.chs = marks;long result = preresult;List results = new ArrayList();Node tree = this.createTree(new Node(null, new ArrayList(), 0);/获取该题目要求的所有可能结果StringBuffer sbuffer = new StringBuffer();ListList allResults = this.DFSAllResult(tree);for (List list : allResults) for (Node node : list) sbuffer.append(node.getData();long rs = this.calc(sbuffer.toString();if(rs = result)ComposeDisplay.COUNT+;results.add(sbuffer.toString();sbuffer.delete(0, sbuffer.length();return results;/* * 将一个列表的内容复制到另一个空列表中 * param dest目标列表 * param src原列表 */private void copy(List dest, List src)for (Node node : src)dest.add(node);=主界面类=package com.clb.tree;import java.awt.Color;import java.awt.Cursor;import java.awt.Font;import java.awt.Label;import java.awt.TextArea;import java.awt.Toolkit;import java.awt.event.MouseAdapter;import java.awt.event.MouseEvent;import java.util.List;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JTextArea;import javax.swing.JTextField;public class ComposeDisplayprivate JFrame jframe = null;/the main windowprivate int WIDTH = 251,HEIGHT = 340;private JButton startRun = null;/start runprivate Label divideLine = new Label();/the divide line of mainly window with detail resultsprivate JButton details = null; /calculator resultsprivate TextArea results = null;/the detail all of results/* * display all detail infomations */private Label record_rs = null;/results countpublic static int COUNT = 0;/results countprivate Label usedTime_rs = null;/used timeprivate long startTime = 0;/start run time/* * input datas */private JTextField arrays_nums = null;/arraysprivate JTextField marks_chs = null;/marksprivate JTextField preresult_value = null;/preresultprivate int ARRAYS_NUMS = 1, 2, 3, 4, 5, 6, 7, 8, 9, 0;private char MARKS_CHS = +, -, ;private long PRERESULT_VALUE = 20;/* * hidden area font */private Label fontSize_dec = null;private Label fontSize_inc = null;public ComposeDisplay()jframe = new JFrame(number game chenglognbo);/get the screens px of width and heightint width=Toolkit.getDefaultToolkit().getScreenSize().width; int height=Toolkit.getDefaultToolkit().getScreenSize().height;jframe.setSize(WIDTH, HEIGHT);/set the windows size jframe.setLocation(width-WIDTH)/2,(height-HEIGHT)/2);/locate to the middle of layout screen jframe.setResizable(false);jframe.setLayout(null);startRun = new JButton(start);startRun.setBorderPainted(false);startRun.setToolTipText(run start);startRun.setBounds(WIDTH-180, HEIGHT-20-35-60, 90, 20);startRun.addMouseListener(new MyEventListenner();jframe.add(startRun);details = new JButton(detail);details.setContentAreaFilled(false);details.setBorderPainted(false);details.setToolTipText(scanning details);details.setBounds(WIDTH-90, HEIGHT-20-35, 90, 20);details.addMouseListener(new MyEventListenner();jframe.add(details);inputData();displayDetailResults();/dispaly all results arearunInfo();divideLine.setBounds(WIDTH, 0, 2, HEIGHT);divideLine.setBackground(Color.LIGHT_GRAY);jframe.add(divideLine);jframe.setVisible(true);jframe.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);/* * describle the question and input some datas */private void inputData()/describle of the questionJTextArea desrible = new JTextArea();String describle_question = QUESTION:n +Now give you ten numbers and n +these order as flow:n +eg:1 2 3 4 5 6 7 8 9 0=20n +you can insert a mark(+,-or )n +make it truthly.please list all ofn +expression like that.n +eg:1-2-3 4+5+6 7-8-9+0=20;desrible.setFont(new Font(null, Font.BOLD, 13);desrible.setBackground(jframe.getBackground();desrible.setBounds(5, 5, WIDTH-30, HEIGHT-180);desrible.setText(describle_question);desrible.setCursor(new Cursor(Cursor.HAND_CURSOR);desrible.setEditable(false);jframe.add(desrible);/need to input arraysLabel arrays_lab = new Label(Arrays);arrays_lab.setBounds(5, HEIGHT-170, 50, 20);arrays_lab.setForeground(Color.RED);jframe.add(arrays_lab);arrays_nums = new JTextField(1,2,3,4,5,6,7,8,9,0);arrays_nums.setBounds(55, HEIGHT-170, 170, 20);jframe.add(arrays_nums);/maybe using marksLabel marks_lab = new Label(Marks);marks_lab.setBounds(5, HEIGHT-145, 50, 20);marks_lab.setForeground(Color.RED);jframe.add(marks_lab);marks_chs = new JTextField(+,-, );marks_chs.setBounds(55, HEIGHT-145, 50, 20);jframe.add(marks_chs);/result finallyLabel preresult_lab = new Label(Preresult);preresult_lab.setBounds(125, HEIGHT-145, 60, 20);preresult_lab.setForeground(Color.RED);jframe.add(preresult_lab);preresult_value = new JTextField(20);preresult_value.setBounds(185, HEIGHT-145, 40, 20);jframe.add(preresult_value);/* * deal with all input datas */private void convertInputDatas()/is or is not happend exception when convert datasboolean has_exception = false;/convert arraysint temp_arrays = null;try String arrays = arrays_nums.getText().split(,);temp_arrays = new intarrays.length;for (int i=0; iarrays.length;i+)temp_arraysi = Integer.parseInt(arraysi); catch (NumberFormatException e) has_exception = true;catch (Exception e)has_exception = true;if(!has_exception)ARRAYS_NUMS = temp_arrays;has_exception = false;/convert markschar temp_marks = null;try String marks = marks_chs.getText().split(,);temp_marks = new charmarks.length;for (int i=0; imarks.length;i+)temp_marksi = marksi.charAt(0); catch (NumberFormatException e) has_exception = true;catch (Exception e)has_exception = true;if(!has_exception)MARKS_CHS = temp_marks;has_exception = false;/convert preresultlong temp_preresult = 0;try temp_preresult = Long.parseLong(preresult_value.getText(); catch (NumberFormatException e) has_exception = true;catch (Exception e)has_exception = true;if(!has_exception)PRERESULT_VALUE = temp_preresult;/* * recording infomation when start run */private void runInfo()Label record = new Label(Record);record.setBounds(15, HEIGHT-85, 45, 20);jframe.add(record);record_rs = new Label(0);record_rs.setFont(new Font(null, Font.PLAIN, 15);record_rs.setForeground(Color.RED);record_rs.setBounds(20+40, HEIGHT-85, 30, 20);jframe.add(record_rs);Label usedTime = new Label(UsedTime);usedTime.setBounds(20+45+35, HEIGHT-85, 60, 20);jframe.add(usedTime);usedTime_rs = new Label(0ms);usedTime_rs.setFont(new Font(null, Font.PLAIN, 15);usedTime_rs.setForeground(Color.RED);usedTime_rs.setBounds(20+45+25+80, HEIGHT-85, 50, 20);jframe.add(usedTime_rs);/* * dispaly all results at the details compose */private void displayDetailResults()results = new TextArea();/results.setAutoscrolls(false);/the titleLabel title = new Label(all results, Label.CENTER);title.setBounds(WIDTH, 8, 200, 17);/title.setForeground(Color.BLUE);title.setFont(new Font(null, Font.PLAIN, 18);jframe.add(title);results.setBackground(jframe.getBackground();results.setBounds(WIDTH+4, 25, 190, HEIGHT-80);/the bottom informationsLabel fontSize = new Label(FontSize);fontSize.setBounds(WIDTH+20, HEIGHT-20-35, 60, 20);jframe.add(fontSize);fontSize_dec = new Label(-, Label.CENTER);fontSize_dec.setFont(new Font(null, Font.BOLD, 22);fontSize_dec.setBounds(WIDTH+85, HEIGHT-20-35, 30, 20);fontSize_dec.setCursor(new Cursor(Cursor.HAND_CURSOR);fontSize_dec.addMouseListener(new MyEventListenner();jframe.add(fontSize_dec);fontSize_inc = new Label(+, Label.CENTER);fontSize_inc.setFont(new Font(null, Font.BOLD, 22);fontSize_inc.setBounds(WIDTH+125, HEIGHT-20-35, 30, 20);fontSize_inc.setCursor(new Cursor(Cursor.HAND_CURSOR);fontSize_inc.addMouseListener(new MyEventListenner();jframe.add(fontSize_inc);jframe.add(results);public static void main(String args) new ComposeDisplay();private boolean finished = false;/is or is not run finished class MyThread extends ThreadOverridepublic void run() super.run();while(true)long useTime = System.currentTimeMillis()-startTime;String usetimestr = useTime 1000? useTime+ms : useTime/1000+s;record_rs.setText(COUNT+);usedTime_rs.setText(usetimestr);if(finished)finished = false;break;/* * haddle