返回顶部

收藏

一个简单的求解算法

更多

学生时期老师的一个小程序, 用途如下: 任意给定几个数字, 程序自动去计算能否由前面的数字通过加/减能否得出等于最后一个数, 如 给出 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://outofmemory.cn

标签:java,算法

收藏

0人收藏

支持

0

反对

0

发表评论