猜生日算法

通过询问对方5个问题，每个问题均是提问其生日在不在给出的集合中，如果是则输入1，不是输入0，那么在5个回合后，程序将给出这个人生日为几号。

参考《Introduction to Java Programming 8th》，在最后面写出了原理的实现，下面是代码。

import java.util.Scanner;

public class Item_001
{
	/**
	 * 通过询问某个人5个问题，找出其出生日期
	 */
	public static void main(String[] args)
	{
		//给定5个集合
		String gather1 = "",gather2="",gather3="",gather4="",gather5="";
		for(int i = 1;i<=31;i++)
		{
			String iBin = Long.toBinaryString(i);
			int len = iBin.length();
			if(len<5)for(int j =0;j<5-len;j++)iBin="0"+iBin;//统一的输出5位数，位数不够则左边用0补齐
			//System.out.printf("%-2d----%5s
",i,iBin);//debug
			for(int k=0;k<5;k++)//确定第几位是1，然后放入对应的集合中
			{
				int isOne = Integer.parseInt(iBin.substring(k, k+1));
				if(isOne==1)
					switch (k)
					{
						case 4:
							 gather1 = gather1 +"	"+ Integer.parseInt(iBin,2);//中间的空格需要用tab来空出
							 break;
						case 3:
							 gather2 = gather2 + "	"+Integer.parseInt(iBin,2);
							 break;
						case 2:
							 gather3 = gather3 + "	"+Integer.parseInt(iBin,2);
							 break;
						case 1:
							 gather4 = gather4 +"	"+ Integer.parseInt(iBin,2);
							 break;
						case 0:
							 gather5 = gather5 + "	"+Integer.parseInt(iBin,2);
							 break;
					}
			}
		}
		int day = 0;
		Scanner sc = new Scanner(System.in);
		FormatOutput(gather1);
			int answer = sc.nextInt();
			if(answer == 1) day+=1;
		FormatOutput(gather2);
			answer = sc.nextInt();
			if(answer == 1) day+=2;
		FormatOutput(gather3);
			answer = sc.nextInt();
			if(answer == 1) day+=4;
		FormatOutput(gather4);
			answer = sc.nextInt();
			if(answer == 1) day+=8;
		FormatOutput(gather5);
			answer = sc.nextInt();
			if(answer == 1) day+=16;
		System.out.println("
Your birthday is "+day+"!");
		sc.close();
	}
	public static void FormatOutput(String str)
	{
		System.out.println("Is your birthday in this set?");
		String arr[] = str.split("	");
		 for(int m=1;m<arr.length;m++)
		 {
			 System.out.print(arr[m]+"	");
			 if(m%4==0)System.out.println('
');;
		 }
		 System.out.println("
Enter 0 for NO and 1 for Yes:");
		 System.out.println();
	}
	
}
/*
 * 关于猜生日的一些说明：
 * 一个人的生日只能是[1,31]号中的某一天，31的二进制位11111=00001+00010+00100+01000+10000，也就是：
 * 		00001--------------1
 * 		00010--------------2
 * 		00100--------------4
 * 		01000--------------8
 * 	+	10000--------------16
 * ————————————————————————————
 *      11111--------------31
 * 然而我们知道，二进制只能由0或者1组成，所以一个数字[1,31]的各个位数只能是0或者1，所以由上面的数组合可以组合相加，可以得到任意一个数字。
 * 这样的话，我们任意取一个数字,其二进制表示为：abcde(注：分别为各个位上的数字，比如10110，则a=1，b=0,c=1,d=1,e=0)，
 * 则abcde可以由如下算式得到：
 * 		0000e
 * 		000d0
 * 		00c00
 * 		0b000
 * 	 +	a0000 
 * ————————————————————————————
 * 		abcde
 * 显然这个abcde是任意的，并且a，b,c,d或者e要么为0要么为1。这样我们可以将一个数[1,31]放在5个集合的某个集合中，
 * 规则是：
 * 如果这个数的e=1(不限定其他位数字),那么就应该放在集合set1中。
 * 如果这个数的d=1(不限定其他位数字),那么就应该放在集合set2中。
 * 如果这个数的c=1(不限定其他位数字),那么就应该放在集合set3中。
 * 如果这个数的b=1(不限定其他位数字),那么就应该放在集合set4中。
 * 如果这个数的a=1(不限定其他位数字),那么就应该放在集合set5中。
 * 注：显然可能一个数字放在多个集合中。
 * 当将这些数放置在不同的集合中后，通过指定某个数存在于5个集合中的哪些集合。我们便可以轻易的得到这个数字。
 * 举个例子来说，比如23，其二进制为10111，那么我们会将它放置到set1，set2，set3，set5中。
 * 这样当你指定说某个数在集合set1，set2，set3，set5，那么我们便知道，你说的某数必然是a=1,b=0,c=1,d=1,e=1.
 * 很容易的我们便可以猜出你说的某数为16+4+2+1=23。
 */