国王和100个囚犯

看到一个关于算法的帖子，总结了下跟帖的算法发表一下：

原贴地址：http://www.iteye.com/topic/569275

解决方案：

1. 指定100其中的一个人来做管理员

2. 设定第一个出来的囚犯是管理员
3. 管理员第一次出来放风时候把灯打开
4. 其他人放风的时候， 如果自己是第一次出来 看灯的状态，如果是亮的，那么关闭它
5. 其他人如果不是第一次出来，不改变灯的状态，关着就让它关着，开着就让它开着
6. 如果第一次出来的时候 灯为关闭状态， 那么不改变状态，并且当自己没出来，下次出来仍然是第一次出来
7. 当管理员再次出来时候如果灯是关闭的 说明除他之外有一个人放出来了 心中的计数器加1， 并把灯打开， 如果灯是开着的，说明除他之外没有人出来过， 不做任何操作

 

代码如下：

import java.util.Random;

public class TestRandom {

	public static void main(String[] args) {
		Random rr = new Random();
		int[] persons = new int[100];
		boolean isONorOFF = true;
		int day = 0;
		int maanagerno;//管理员
		int count = 0;// 计数
		int n = rr.nextInt(100);
		persons[n] = 1;
		maanagerno = n;
		day++;
		count += 1;
		while (true) {
			if (count == 100) {
				break;
			}

			day++;
			n = rr.nextInt(100);
			// 是管理员放风，并且符合计数要求，计数加一
			if (maanagerno == n) {
				if (!isONorOFF) {
					persons[n] = 1;
					count += 1;
					isONorOFF = true;
				}
			}
			// 不是管理员
			else {
				// 第一放风，灯开着，符合标记条件，关闭灯
				if (persons[n] != 1) {
					if (isONorOFF) {
						isONorOFF = false;
						persons[n] = 1;
					}
				}
			}
		}

		int row = 0;
		for (int i = 0; i < persons.length; i++) {
			row += persons[i];

		}
		System.out.println("嘻嘻哈哈" + day);
		System.out.println("嘻嘻哈哈" + day / 365);
		System.out.println("嘻嘻哈哈" + row);
	}

}