告诉你什么是优雅的代码（4）-----智力题的解法（答案）

以下智力题摘自某一帖子。在纸上画了一下之后有了答案。出于职业敏感，开始考虑如何用程序来解决。现在已经有了基本的模型和算法，就等实现。不过，这次不再急于告诉大家什么是优雅的代码，让聪明的你们先来思考一下。实现随后放出。如果帖子过快被隐藏，那么你们又错失一次学习优雅代码的机会了。好了，废话少说，大家一起动脑思考吧。

   1. 6.宴会桌旁  
   2.   
   3. 　　在某宾馆的宴会厅里，有4位朋友正围桌而坐，侃侃而谈。他们用了中、英、法、日4种语言。现已知：  
   4.   
   5. 　　A．甲、乙、丙各会两种语言，丁只会一种语言；  
   6.   
   7. 　　B．有一种语言4人中有3人都会；  
   8.   
   9. 　　C．甲会日语，丁不会日语，乙不会英语；  
  10.   
  11. 　　D． 甲与丙、丙与丁不能直接交谈，乙与丙可以直接交谈；  
  12.   
  13. 　　E． 没有人既会日语，又会法语。  
  14.   
  15. 　　请问：甲乙丙丁各会什么语言？  

首先，建立一张二维表，如图所示：
*     中  英 法 日
*  甲          
*  乙    
*  丙
*  丁          
某人掌握某语言则标1，不掌握则标0。则问题转化为在表的状态空间下找出符合题中约束的一张表。状态空间的数目为 16*16*16*16,这个数虽然不是天文数字，但效率显然是低下的，编程起来也异常麻烦。
不要急，我们来整理下题中纷乱的约束，重新整理如下：

  甲： 会日语，会两种语言，不会法语
  乙： 不会英语，会两种语言，不同时会日语和法语
  丙： 会两种语言，不同时会日语和法语
  丁： 不会日语，只会一种语言

  全局约束：甲与丙、丙与丁不能直接交谈，乙与丙可以直接交谈，有一种语言4人中有3人都会

Ok,现在二维表的状态如下：
       中  英  法  日
   甲                1
   乙     0
   丙
   丁                0
先忽略全局约束，根据各人的约束，则状态空间变为（其中c(a,b)是组合数）：
(c(3,1) - 1) * (c(3,2) - 1) * (c(4,2)-1)*c(3,1) = 2*2*5*3 = 60
显然非常少了。接下来我们只要在这个状态空间下寻找出满足全局约束的状态就可以了。

就在我准备用二维数组来实现的时候，一个火花在脑中突然迸发。那就是按位与运算。我们来看下与运算：

1001&1100 = 1000  0010&0101 = 0000

看出端倪了吗？两个人如果能互相交流证明其状态按位与的结果不为0，否则则为0.

于是一个优雅的方案浮出水面：

/*
 *   A．甲、乙、丙各会两种语言，丁只会一种语言；  
#   
# 　　B．有一种语言4人中有3人都会；  
#   
# 　　C．甲会日语，丁不会日语，乙不会英语；  
#   
# 　　D． 甲与丙、丙与丁不能直接交谈，乙与丙可以直接交谈；  
#   
# 　　E． 没有人既会日语，又会法语。  
 
 *
 *分析
 *  甲： 会日语，会两种语言，不会法语
 *  乙： 不会英语，会两种语言，不同时会日语和法语
 *  丙： 会两种语言，不同时会日语和法语
 *  丁： 不会日语，只会一种语言
 *  全局约束：甲与丙、丙与丁不能直接交谈，乙与丙可以直接交谈，有一种语言4人中有3人都会
 *  
 *     8   4 2  1
 *     中  英 法 日 
 *  甲           1
 *  乙     0
 *  丙
 *  丁           0
 */
public class Fun {
	public static void main(String[] args) {
		
		int[] a = {9,5};
		int[] b = {10,9};
		int[] c = {5,6,9,10,12};
		int[] d = {8,4,2};
		boolean solved = false;
		
		for (int i = 0; i < a.length&&!solved; i++) {
			
			
			for (int j = 0; j < b.length&&!solved; j++) {
				
				
				for (int k = 0; k < c.length&&!solved; k++) {
					//甲与丙不能直接交谈
					if((a[i]&c[k]) != 0 )
						continue;
					//乙与丙可以直接交谈
					if((b[j]&c[k]) == 0)
						continue;
					
					for (int l = 0; l < d.length; l++) {
						//丙与丁不能直接交谈
						if((c[k]&d[l]) != 0)
							continue;
						//有一种语言4人中有3人都会
						if((a[i]&b[j]&c[k])!=0 || (a[i]&b[j]&d[l])!=0 || (a[i]&c[k]&d[l])!=0
						|| (b[j]&c[k]&d[l])!=0 ){
							
							System.out.print("甲：");
							parse(a[i]);
							System.out.println();
							System.out.print("乙：");
							parse(b[j]);
							System.out.println();
							System.out.print("丙：");
							parse(c[k]);
							System.out.println();
							System.out.print("丁：");
							parse(d[l]);
							System.out.println();
							solved = true;
							break;
						}
					}
				}
			}
		}
		
	}

	private static void parse(int num) {
		while(num!=0){
			if(num >= 8){
				System.out.print(" 中 ");
				num -= 8;
			}
			else if(num >= 4){
				System.out.print(" 英 ");
				num -= 4;
			}
			else if(num >= 2){
				System.out.print(" 法 ");
				num -= 2;
			}
			else{
				System.out.print(" 日 ");
				num -= 1;
			}
		}
		
	}
}

评论

16 楼 wfm0105 2016-02-04  

daisy_rainbow 写道

       
不懂这些数组里面的值是什么意义？？

        int[] a = {9,5}; 
        int[] b = {10,9}; 
        int[] c = {5,6,9,10,12}; 
        int[] d = {8,4,2}; 

补全下作者的2维图你就会明白，这些数组代表什么了

       8   4 2  1
*     中  英 法 日 
*  甲         0  1
*  乙     0
*  丙            0
*  丁            0

a 数组代表 甲会的语言，8+1或者4+1 ,乙丙丁 以此类推


解释不到位不要喷。

15 楼 daisy_rainbow 2015-02-27  

       
不懂这些数组里面的值是什么意义？？

        int[] a = {9,5}; 
        int[] b = {10,9}; 
        int[] c = {5,6,9,10,12}; 
        int[] d = {8,4,2}; 

14 楼 tonly85 2010-10-05  

先不考虑代码，和题目逻辑。用中国人的想法，题目既然中国人出的，会的人最多的那种语言肯定是中文。

13 楼 yangguo 2010-09-26  

zhao103804 写道

我只是推算出来了，并未写成程序，不知对否
甲：中日
乙：中法
丙：英法
丁：法

错了，你的丙与丁可以直接交流。代码已贴出，自己跑下。

12 楼 yangguo 2010-09-26  

Sweegi 写道

留言啦~到处学习学习

代码已贴出。

11 楼 Sweegi 2010-09-26  

留言啦~到处学习学习

10 楼 zhao103804 2010-09-25  

我只是推算出来了，并未写成程序，不知对否
甲：中日
乙：中法
丙：英法
丁：法

9 楼 VeeSong 2010-09-22  

留言就能看到吗？

8 楼 yangguo 2010-09-19  

ge_cc 写道

想看看  ·

已发。

7 楼 ge_cc 2010-09-19  

想看看  ·

6 楼 lzxz1234 2010-09-15  

我要代码，楼主发给我吧，谢了

5 楼 yangguo 2010-09-10  

mqlfly2008 写道

画图我会了，但要写成程序，还没想出来，等待哥们的优雅代码

代码已经发放过了。你来迟了。要的话我发你。

4 楼 mqlfly2008 2010-09-10  

画图我会了，但要写成程序，还没想出来，等待哥们的优雅代码

3 楼 yangguo 2010-09-09  

那你不妨拿出来show show.

2 楼 tangchj 2010-09-09  

俺也实现了一种，思路基本一致，方式略有不同

1 楼 xiaoxiaoniao 2010-09-08  

这种题锻炼脑子，
找到大学时的感觉了。

喜欢