从一道Java算法题看Java程序员的思维局限解决方案-Java教程-爱易网页

从一道Java算法题看Java程序员的思维局限解决方案

日期：2014-05-20　浏览次数：20932 次

从一道Java算法题看Java程序员的思维局限
原题:
用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求： "4 "不能在第三位， "3 "与 "5 "不能相连.

然后发现很少Java程序员知道递归回溯法解决该问题。思想基本都被严重的‘OO’化了。本题给的是数字，一堆人都在操作字符串。总而言之是缺少算法知识，这对Java社区来说是个很大的缺陷，也是C/C++程序员谈到Java就面露不屑表情的原因之一。学Java学到基本算法都不知道实在是一种悲哀。

再回头看这题，假如换成数学问题，就问多少方案呢？显然是个排列问题，可以先计算所有的情况，然后去除不满足条件的。
1。不加任何约束，则一共P6/P2=360种（因为2重复了，所以除以P2)
2。4在第三位的情况有：P5/P2=60种（去掉4，其他数字的全排列）
3。3，5相连的情况有：P5*P2/P2=120(把3，5看成一个整体，全排列，然后乘以P2是3,5这个整体的排列，除以2的重复）
4。4即在第三位，而且3，5又相连。
4.1）考虑3,5在第一二位，则有P2×（P3/P2）=6.
4.2）3,5不在头两位。
4.2.1）左边全是2的情况，（P2×P2）=4
4.2.2）左边是1，2的情况 (P2×P2×P2)= 8
5。根据容斥原理：总共：360-(60+120)+(6+4+8)=198种。

回到程序解答上，其实就是一个搜索问题，搜索所有的可行解，搜索空间就是所有排列，这类问题一般都可用回溯法解决。
回溯法的算法框架一般都是：

Java code


void backtrace(int steps[],int depeth)
{
    if(depth>=LIMIT){sloved();}

    constructCondicates();
    foreach condicates do{
       steps[depth]=condicates[i];
       backtrace(depth++);
    }
}

关键在于构造可行解。

本题的相应Java算法如下：

Java code



/**
 * @author yvon
 * 
 */
public class TestGen {
    int constructCondicates(int steps[], int[] used, int level, int[] condicates) {
        int cn = 0;
        boolean has2 = false;
        for (int j = 0; j < 5; j++) {
            if (used[j] == 0) {
                if (level > 0) {
                    if ((j == 2 && steps[level - 1] == 5)
                            || (j == 4 && steps[level - 1] == 3)
                            || (j == 3 && level == 2)) {// 三五不相连,四不能在第三位
                        continue;
                    }
                }
                if (j == 1) {
                    if (!has2) {
                        has2 = true;
                    } else {// 可行解里只能一次包含2.相同的位置（排除重复）
                        continue;
                    }
                }
                condicates[cn++] = j + 1;
                // 如果是2的话，还可以使用一次，前提是可行解没使用
            } else if (j == 1 && !has2 && used[j] == 1) {
                condicates[cn++] = j + 1;
                has2 = true;
            }
        }
        return cn;
    }

    void doGen(int steps[], int used[], int level, int[] total) {
        if (level == 6) {
            for (int i = 0; i < 6; i++) {
                System.out.print(steps[i] + " ");
            }
            System.out.println();
            total[0]++;
            return;
        }
        int condicates[] = new int[6];
        int cn = constructCondicates(steps, used, level, condicates);
        for (int k = 0; k < cn; k++) {
            int todo = condicates[k];
            steps[level] = todo;
            used[todo - 1]++;
            doGen(steps, used, level + 1, total);
            used[todo - 1]--;
        }
    }
    public static void main(String[] args) {
        int[] steps = new int[6];
        int[] used = new int[6];
        int total[] = new int[1];
        new TestGen().doGen(steps, used, 0, total);
        System.out.println("Totally:" + total[0]);
    }

}

运行结果：

Java code

 
 1 2 2 3 4 5  
 1 2 2 5 4 3  
 1 2 3 2 4 5  
 1 2 3 2 5 4  
 1 2 3 4 2 5  
 1 2 3 4 5 2  
 1 2 5 2 3 4  
 1 2 5 2 4 3  
 1 2 5 4 2 3  
 1 2 5 4 3 2  
 1 3 2 2 4 5  
 1 3 2 2 5 4  
 1 3 2 4 2 5  
 1 3 2 4 5 2  
 1 3 2 5 2 4  
 1 3 2 5 4 2  
 1 4 2 3 2 5  
 1 4 2 5 2 3  
 1 4 3 2 2 5  
 1 4 3 2 5 2  
 1 4 5 2 2 3  
 1 4 5 2 3 2  
 1 5 2 2 3 4  
 1 5 2 2 4 3  
 1 5 2 3 2 4  
 1 5 2 3 4 2  
 1 5 2 4 2 3  
 1 5 2 4 3 2  
 2 1 2 3 4 5  
 2 1 2 5 4 3  
 2 1 3 2 4 5

免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

从一道Java算法题看Java程序员的思维局限解决方案

相关资料更多>

推荐阅读更多>