用数组和面向对象诀别解决数三退一智力游戏

用数组和面向对象分别解决数三退一智力游戏

        “数三退一”介绍

             n个人编号0～n-1，手拉手围成一个圈，按照一定的方向从0号开始数，每数到3的人退出，从下一个人继续数，直到剩下最后一个人。
求这个人的编号。

          用数组通过面向过程实现

public class Count3Quit
{
	public static void main(String[] args)
	{
		Boolean[] people=new Boolean[500];
		for(int i=0;i<people.length;i++)
		{
			people[i]=true;
		}
		
		int leftNum=500;
		int countNum=0;
		int index=0;
		
		while(leftNum>1)
		{
			if(people[index]==true)
			{
				countNum++;
			}
			
			if(countNum==3)
			{
				leftNum--;
				people[index]=false;
				countNum=0;
			}
			
			index++;
			
			if(index==people.length)
			{
				index=0;
			}
		}
		
		for(int i=0;i<people.length;i++)
		{
			if(people[i]==true)
			{
				System.out.println(i);
			}
		}
	}
}

         用面向对象的思想解决

public class OOCount3Quit
{
	public static void main(String[] args)
	{
		kidCircle c=new kidCircle(500);
		
		int flag=0;
		kid k=c.first;		//拿到第一个小孩
		
		while(c.count>1)
		{
			flag++;
			if(flag==3)
			{
				flag=0;
				c.delete(k);
			}
			k=k.right;
		}
		
		//输出
		System.out.println(c.first.id);
	}
}

//定义一个小孩类
class kid
{
	int id;		//序号
	kid left;	//左边的小孩
	kid right;	//右边的小孩
	
	kid(int id)
	{
		this.id=id;
	}
}

//定义一个圈类
class kidCircle
{
	int count=0;	//圈里面还有多少个小孩
	kid first;		//第一个小孩
	kid last;		//最后一个小孩
	
	//构造方法
	kidCircle(int n)
	{
		for(int i=0;i<n;i++)
		{
			add();
		}
	}
	
	//定义一个方法，用来添加小孩
	void add()
	{
		kid k=new kid(count);
		if(count==0)
		{
			first=k;
			last=k;
			k.left=k;
			k.right=k;
		}
		else
		{
			last.right=k;
			k.left=last;
			k.right=first;
			first.left=k;
			last=k;
		}
		count++;
	}
	//定义一个删除一个小孩的方法
	void delete(kid k)
	{
		//圈里没有小孩了
		if(count==0)
		{
			return;
		}
		else
		{
			k.left.right=k.right;
			k.right.left=k.left;
			if(k==first)     //如果删除的是第一个小孩
			{
				/*下面这句话是多余的，
				因为last的右边一直是first*/
				//last.right=k.right;
				first=k.right;
			}
			else if(k==last)	//如果删除的是最后一个小孩
			{
				last=k.left;
			}
		}
		count--;
	}
}

 

             还有一个思路就是通过数组来模拟链表实现。。。