逻辑练习《6人参加会议》

2017-05-19 本文已影响0人 w_左拖拖

源于《三个变态的循环》第一题

原文链接http://www.cn-java.com/www1/bbs/viewthread.php?tid=93104&extra=page=1

参加会议:有人邀请A,B,C,D,E,F6个人参加一项会议，这6个人有些奇怪，因为他们有很多要求，已知：
(1).A,B两人至少有1人参加会议。
(2).A,E,F 3人中有2人参加会议。
(3).B和C两人一致决定，要么两人都去，要么两人都不去。
(4).A,D两人中只1人参加会议。
(5).C,D两人中也只要1人参加会议。
(6).如果D不去，那么E也决定不去。
那么最后究竟有哪几个人参加了会议呢？

题外话

最开始在上面的原文论坛回答一个小伙伴的提问，后来换了几家公司原代码已经找不到了，下面的代码是之后整理过的代码。今年2月份的时候在CSDN博客上看到被人收集并且标记为原创，感觉自己的东西被人偷去了一样难受，于是又整理了一份。

推理

从4，5两个条件出发A，D互斥同时C，D互斥（当然这里有一定歧义，只要1人参加可以理解为必须选1人参加或者理解为要么1人参加要么两个都不参加，因为这里没有强调必须去。）

假设D参加，那么A，C不参加，根据条件(1)B就必须参加得到BD
再根据条件(3)要求BC要么同去要么同不去，所以C也必须去，得到BCD，与条件(5)相矛盾，所以D是肯定无缘参加了。
D不参加根据条件(6)得到E也不参加，那么条件(2)中AEF就排除掉E 得到AF
回到上面提的歧义，如果理解为后一种的话那AF可以满足所有条件，如果理解为前一种的话D不参加C就必须参加得到ACF，再回到条件(3)可知B也必须去最终得到ABCF
那么最终的人选是ABCF 或者再算上歧义的结果AF

转换成程序的基本思路是找出6人所有可能的组合，然后根据1~6这6个条件一个一个判断是否满足，找出完全满足条件的组合即可。应该也有更好的思路不用进行组合，先假定6人都去然后再根据条件进行排除。

获取所有组合
得到A，B，C，D，E，F，AB，AC，AD，AE，AF...ABCDEF这样的全组合，可以使用递归法(回溯)，也可以使用一维数组。
下面是使用一维数组的方法。

    /**
     * 组合不排列
     * @param items
     * @return 数组中所有可能的组合
     */
    public static String[] combination(String[] items) {
        int n = items.length, index = 0, _n = n;
        // 每个人都有两种状态,要么去,要么不去所以总共的组合就有2^6,
        // 但是全部不去这种组合没有意义要去掉
        String[] comb = new String[(1 << n) - 1];
        System.arraycopy(items, 0, comb, 0, n);
        while (++index < n) {
            int j = _n;
            for (int s = 0, len = n - index; s < len; s++) {
                for (int ss = (j - count(n - s - 1, index)); ss < j; ss++) {
                    comb[_n++] = comb[s] + comb[ss]; // 最好使用StringBuilder
                }
            }
        }
        return comb;
    }

    protected static int count(int p, int c) {
        if (p < c) return 0;
        if (p == c) return 1;
        if (c > p >> 1) c = p - c;
        int _p = 1, _c = 1;
        for (int i = p, size = (p - c); i > size; i--) _p *= i;
        for (int i = 2; i <= c; i++) _c *= i;
        return _p / _c;
    }

得到组合遍历每个组合判断是否全部满足6个条件
最初版是这样子

boolean match(String str) {
        // (1).A,B两人至少有1人参加会议。
        if (!str.contains("A") && !str.contains("B")) {
            return false;
        }
        // (2).A,E,F3人中有2人参加会议。
        if (!((str.contains("A") && str.contains("E"))
                || (str.contains("A") && str.contains("F"))
                || (str.contains("E") && str.contains("F")))) {
            return false;
        }
        // (3).B和C两人一致决定，要么两人都去，要么两人都不去。
        if ((str.contains("B") && !str.contains("C"))
                || (!str.contains("B") && str.contains("C"))) {
            return false;
        }
        // (4).A,D两人中只1人参加会议。
        if (str.contains("A") && str.contains("D")) {
            return false;
        }
        // (5).C,D两人中也只要1人参加会议。mark: 这里并没有说C,D必须有一人参加
        if (str.contains("C") && str.contains("D")) {
            return false;
        }
        // (6).如果D不去，那么E也决定不去。
        if (!str.contains("D") && str.contains("E")) {
            return false;
        }
        return true;
    }

后来整理的时候发现这些判断有很多冗余，比如分支1，2，4都有str.contains("A")，就想办法把它们提出去只调有一次，判断也可以演化为逻辑运算，比如条件(1)A，B至少1人参加可以改为(a|b) == 1，于是就有了一个改版

    boolean match1(String str) {
        // 每个人两个信号量1：去，0：不去
        int a = str.indexOf('A') > -1 ? 1 : 0
                , b = str.indexOf('B') > -1 ? 1 : 0
                , c = str.indexOf('C') > -1 ? 1 : 0
                , d = str.indexOf('D') > -1 ? 1 : 0
                , e = str.indexOf('E') > -1 ? 1 : 0
                , f = str.indexOf('F') > -1 ? 1 : 0;
        // (1).A,B两人至少有1人参加会议。
        if ((a | b) == 0) {
            return false;
        }
        // (2).A,E,F3人中有2人参加会议。
        if ((a & e | a & f | e & f) == 0) {
            return false;
        }
        // (3).B和C两人一致决定，要么两人都去，要么两人都不去。
        if ((b ^ c) == 1) {
            return false;
        }
        // (4).A,D两人中只1人参加会议。
        if ((a & d) == 1) {
            return false;
        }
        // (5).C,D两人中也只要1人参加会议。
        if ((c & d) == 1) {
            return false;
        }
        // (6).如果D不去，那么E也决定不去。
        if ((~d & e) == 1) {
            return false;
        }

        return true;
    }

改为之后发现为何不将非判断改为与判断呢？这样就可以将6个if判断合并为1个判断，最终改为了下面的形式

 boolean match2(String str) {
        int a = str.indexOf('A') > -1 ? 1 : 0
                , b = str.indexOf('B') > -1 ? 1 : 0
                , c = str.indexOf('C') > -1 ? 1 : 0
                , d = str.indexOf('D') > -1 ? 1 : 0
                , e = str.indexOf('E') > -1 ? 1 : 0
                , f = str.indexOf('F') > -1 ? 1 : 0;
        return ((a | b) // (1).A,B两人至少有1人参加会议。
                & (a & e | a & f | e & f) // (2).A,E,F3人中有2人参加会议。
                & ~(b ^ c) // (3).B和C两人一致决定，要么两人都去，要么两人都不去。
                & ~(a & d) // (4).A,D两人中只1人参加会议。必须去一个就改为 & (a ^ d)
                & ~(c & d) // (5).C,D两人中也只要1人参加会议。必须去一个就改为 & (c ^ d)
                & ~(~d & e) // (6).如果D不去，那么E也决定不去。
        ) == 1;
    }

最后只需要一个main函数就可以运行了。

public static void main(String[] args) {
        // 得到6个人所有的组合
        String[] list = combination(new String[] {"A", "B", "C", "D", "E", "F"});
        // 判断每种组合是否满足所有的条件
        for (String str : list) {
            if (match2(str)) {
                System.out.println(str);
            }
        }
    }

当然，运行结果与上面推论的一样，

下一个目标是不拉出所有组合直接处理。

逻辑练习《6人参加会议》

题外话

推理

猜你喜欢

热点阅读