一个简单的求解算法，简单求解算法,学生时期老师的一个小程序

一个简单的求解算法，简单求解算法,学生时期老师的一个小程序

学生时期老师的一个小程序, 用途如下: 任意给定几个数字, 程序自动去计算能否由前面的数字通过加/减能否得出等于最后一个数, 如 给出 1 2 3 6得出 1+2+3=6. 若有解(可能有多个解), 程序返回计算出来的等式.(虽然程序只返回一个可能解, 但有规律哦,细心的看官可以琢磨下源码).

分享这段代码既是出于对老师的思念(老师是印度人,在我看来是大牛,有我这么菜的学生老师您不会嫌弃吧~), 又是希望好的代码能给大家共享.

写程序不一定要用到那些著名的算法, 有时自己的一个小构思也能巧妙的解决问题, 就如图老师的这个程序一样.

当初老师给这个代码是要练习我们阅读代码并画流程图的能力, 请老鸟们勿喷, 新手们可以练习画画图,相信能学到很多.

最后一句, 老师的代码和注释都是挺漂亮的, 英语不好的童鞋们...请见谅~

使用的时候输入数字至少是3个 并以空格分开 只能输入1到9 (关于输入的规则运行程序后的界面上会有提示)

package wis.lacrosse;/* * This program tries to find an arithmetic pattern with a set * of integers and three operators '+', '-' and '='. For * example, *      5 + 3 - 2 = 6 * Given a set of integers, the program tries to find at least one solution * that satisfies the numbers. For the above example, the input is the sequence * of numbers '5', '3', '2' and '6' in that order. The program comes up with the * pattern that uses the numbers '5', '3' and '2' so that the result is '6'. * Notice that there could be more than one solution for a given set of * numbers, but the program finds at least one, if one exists. * * Written by: Kasi Periyasamy * Date created: September 26, 2010. */import javax.swing.*;import java.util.*;public class ArithmeticPattern {    public static void main(String[] args) {        java.awt.EventQueue.invokeLater(new Runnable() {            public void run() {                new ArithmeticPattern().solve();            }        });    }    /**     * This method receives a sequence of integers from input and calls another     * method to find the solution for this pattern. This method validates every     * input to make sure that it is a positive integer.     */    public void solve() {        Vector<Integer> numbers;        Vector<Character> operators;        boolean received, found, done, terminate;        String inString;        String components[];        int i;        String regularExpressionInt = "[1-9]+";        terminate = false;        while (!terminate) {            //            // initialize variables            //            inString = "";            components = null;            numbers = new Vector<Integer>();            operators = new Vector<Character>();            received = false;            while (!received) {                //                // Get the string representing all numbers                //                inString = JOptionPane.showInputDialog(null,                        " Input the sequence of positive integers that represent the pattern, separated by spaces.\\n"                        + " For example, if 5 + 3 - 2 = 6 is the ultimate expression you expect, then input\\n"                        + "       5 3 2 6\\n"                        + " in that order. Remember that the integers must be all positive.\\n"                        + " Any number that is a zero or associated with a non-numeric character will be discarded.\\n\\n"                        + " Press 'Cancel' to terminate the program.");                if (inString == null) {                    received = true;                    terminate = true;                }                else {                    components = inString.split(" ");                    if (components.length < 3)                        display(" There must be at least three inputs\\n", true);                    else {                        //                        // extract individual integers from the input                        //                        done = false;                        i = 0;                        while (!done && i < components.length) {                            if (!components[i].matches(regularExpressionInt)) {                                display(" Input " + (i + 1) + " is not a positive integer\\n", true);                                done = true;                            } else {                                numbers.add(Integer.parseInt(components[i]));                                i++;                            }                        }                        if (!done)                            received = true;                    }                }            }            //            // Call the 'findSolution()' method and see whether there is at            // least one solution for the            // given pattern.            //            if (numbers.size() > 0) {                found = findSolution(numbers, operators);                if (found)                    printSolution(numbers, operators);                else                    display(" No solution is found for the given pattern", true);            }        } // end of while (!terminate)    }    /**     * This method tries to find a solution for a given pattern. It receives an     * integer vector that contains the numbers to be manipulated and a     * character vector to fill up the operators.     *      * @param numbers     *            the integer vector containing the numbers.     * @param operators     *            the character vector for the operators; passed as empty; to be     *            filled in by this method.     */    public boolean findSolution(Vector<Integer> numbers, Vector<Character> operators) {        int j, howmany, iter, result;        boolean success = false;        /*         * The following array will be used to store a binary pattern of a         * number.         */        int[] binary = new int[numbers.size()];        /* Initialize the binary array to -1 */        for (j = 0; j < binary.length; j++)            binary[j] = -1;        howmany = numbers.size();        /*         * There are "howmany" integers and "howmany-1" operators. The integer         * at numbers[homany-1] is the final answer of the the pattern and the         * operator in front of that integer is '='. Therefore, we need to find         * "howmany-2" operators. There are 2 raised to the power (howmany - 2)         * possible ways of arranging the operators. Get the binary pattern for         * each of these combinations and assign '+' for 'true' and '-' for         * 'false'. Use each such combination to verify the result. When one         * matches, stop checking and report the pattern.         */        iter = 1;        while (!success && iter <= (int) (Math.pow(2, howmany - 2))) {            result = (Integer) numbers.elementAt(0);            binary = computeBinary(iter, howmany - 2);            for (j = 0; j < howmany - 2; j++) {                if (binary[j] == 1)                    result = result + (Integer) numbers.elementAt(j + 1);                if (binary[j] == 0)                    result = result - (Integer) numbers.elementAt(j + 1);            }            success = result == (Integer) numbers.elementAt(howmany - 1);            iter++;        }        if (success) { // set the operators            for (j = 0; j < howmany - 2; j++) {                if (binary[j] == 1)                    operators.add((Character) ('+'));                if (binary[j] == 0)                    operators.add((Character) ('-'));            }            // Set the '=' operator at the end            operators.add((Character) ('='));        }        return success;    }    /**     * This method computes and returns the binary pattern of a number.     *      * @param num     *            the number whose binary pattern is required.     * @param len     *            the number of binary digits required.     * @return the binary pattern.     */    public static int[] computeBinary(int num, int len) {        int[] bin = new int[10]; // must be edited again.        int i;        for (i = 0; i < len; i++)            bin[i] = 0;        for (i = len; i < bin.length; i++)            bin[i] = -1;        i = 0;        while (num > 0) {            bin[i++] = num % 2;            num = num / 2;        }        return bin;    }    /**     * This method prints the solution.     *      * @param the     *            vector containing the numbers     * @param the     *            vector that contains the operators     */    public void printSolution(Vector<Integer> numbers, Vector<Character> operators) {        String out = " Here is one possible solution\\n";        for (int i = 0; i < numbers.size() - 1; i++) {            out = out + " " + numbers.elementAt(i) + " " + operators.elementAt(i);        }        out = out + " " + numbers.elementAt(numbers.size() - 1) + "\\n";        display(out, false);    }    /**     * This method displays the error or informative messages.     *      * @param msg     *            the message to be displayed.     * @param what     *            the type of message - `true' indicates error message and     *            `false' indicates informative message.     */    public void display(String msg, boolean what) {        if (what)            JOptionPane.showMessageDialog(null, " Error : " + msg + "\\n");        else            JOptionPane.showMessageDialog(null, msg + "\\n");    }}//该片段来自于http://byrx.net