解决数三退一问题（数组，面向对象）

冷不防 2022-01-06 07:13 304阅读 0赞

# 数三退一算法 #

## 1.数组方法 ##

### 1. 算法描述 ###

--------------------

500个小孩手拉手围成一个圈，第一个小孩从0开始数，数到3，就淘汰出局，退出这个圈，直至剩余最后一个，输出该小孩。

### 2. 分析 ###

--------------------

1.  创建小孩数组，并将每个小孩赋布尔初值为 true 表示在圈内；
2.  默认从数组下标为0开始数，用count 计数（初值为1）；
3.  当count == 3 淘汰这个小孩，即将其值设为false，并将计数器count置为初值1；
4.  循环完所有数组元素后，将元素为true的元素下标打印出来；

### 3.代码 ###

package com.fjh.test;
    
    public class Count3Quit1 { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    
    		Boolean[] children = new Boolean[5];// 创建5个小孩
    		// 初始化
    		for (int i = 0; i < children.length; i++) { 
    			children[i] = true;// 表示都在圈内
    
    		}
    		// 开始报数
    		int count = 1;// 计数器
    		int index = children.length;// 剩余人数
    		int flag = 0;// 当前下标
    		while (index > 1) { 
    			if (children[flag]) { 
    				count++;
    				if (count == 3) { 
    					children[flag] = false;// 淘汰出局
    					index--;
    					count = 0;// 重置计数器
    					System.out.println("小孩" + flag + "淘汰！");
    				}
    
    			}
    			flag++;
                //轮完一圈开始新的一圈
    			if (flag == children.length) { 
    				flag = 0;
    			}
    		}
    
    		// 输出剩余这个孩子
    		for (int i = 0; i < children.length; i++) { 
    			if (children[i]) { 
    				System.out.println("小孩" + i + "胜出！");
    			}
    		}
    	}
    
    }

--------------------

## 2.面向对象 ##

1.  **person类**

属性成员
    	id ; //id
    	Person left;//左边成员
    	Person right;//右边成员

1.  **circle类**  
    ***分析***

1. 属性成员	
    	圈子对象 cicle
        圈子大小 count = 0
        圈子的第一个人person  first 
        圈子的最后一个人person last
        
    2. 方法抽象
    	new cicle（500）//圈子要初始化
    
    3. 方法 加人（person p）
         圈子中已经有人的情况
            count ++  
            原来圈子中最后一个人的右边 》 新加人p 
            新加人p的左边 》 原来圈子中的最后一个人
            新加人p的右边 》 原来圈子中第一个人
            原来圈子中最后一个人 = 新加人p
            原来圈子中第一个人的左边新加人p的右边
    	 如果是一个空圈  count= 0
             圈子中的第一个人 = 新加人p
             圈子中最后一个人 = 新加人p
    
    方法 删除人（person p）
        删除人p左边的人 》 删除人右边的人
        删除人右边的人 》 删除人左边的人
    
        如果删除的是第一个人
        删除人的右边的人变成了圈子中的第一个人
    
        如果删除人是最后一个人
        删除人的左边变成了圈子中的最后一个人

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODk2OTk3_size_16_color_FFFFFF_t_70]

**person类**

package com.fjh.entity;
    
    public class Person { 
    	/** * ID */
    	private int id ; 
    	/** * 左边的人 */
    	private Person left;
    	/** * 右边的人 */
    	private Person right;
    	public int getId() { 
    		return id;
    	}
    	public void setId(int id) { 
    		this.id = id;
    	}
    	public Person getLeft() { 
    		return left;
    	}
    	public void setLeft(Person left) { 
    		this.left = left;
    	}
    	public Person getRight() { 
    		return right;
    	}
    	public void setRight(Person right) { 
    		this.right = right;
    	}
    	
    	public Person(int id) { 
    		super();
    		this.id = id;
    	}
    	public Person() { 
    		super();
    	
    	}
    	
    	
    }

**circle类**

package com.fjh.entity;
    
    public class Circle { 
    	// 初始化
    	/** * 圈子大小 */
    	private int count;
    	/** * 圈第一个人 */
    	private Person first;
    	/** * 最后一个人 */
    	private Person last;
    
    	public int getCount() { 
    		return count;
    	}
    
    	public void setCount(int count) { 
    		this.count = count;
    	}
    
    	public Person getFirst() { 
    		return first;
    	}
    
    	public void setFirst(Person first) { 
    		this.first = first;
    	}
    
    	public Person getLast() { 
    		return last;
    	}
    
    	public void setLast(Person last) { 
    		this.last = last;
    	}
    
    	/** * 添加 * @param p 要加入圈子的人 */
    	
    	public void addPerson(Person p) { 
    		// 如果圈子中有person
    		if (this.count > 0) { 
    			this.last.setRight(p);// 原来圈子中最后一个人的右边 -> 新加人p
    			p.setLeft(last);//新加人P的左边指向原来圈子最后一个
    			p.setRight(first);//新加人P的右边指向原来圈子的第一个
    			this.last = p;//原来圈子最后一个人赋给新加入的牌P
    			this.first.setLeft(p);//原来圈子的第一个人左边指向新加入p
    
    		} else { 
    		//如果圈子里没人
    			this.first = p;//将新加入p指向圈子第一个人
    			this.last = p;//将新加入的p指向圈子最后一个
    			p.setRight(p);//将新加入p的右边指向自己
    			p.setLeft(p);//将新加入p的左边指向自己
    
    		}
    		this.count++;//圈内人数加1
    	}
    
    	/** * 移除 * @param p 将要移除的人 */
    	public void removePerson(Person p) { 
    		p.getLeft().setRight(p.getRight());// 删除人p左边的人 》 删除人右边的人
    		p.getRight().setLeft(p.getLeft());// 删除人右边的人 》 删除人左边的人
    
    		if (p == this.first) { //如果移除的是第一个，则将将要其右边的人作为第一个
    			this.first = this.first.getRight();
    
    		}
    		if (p == this.last) { //如果移除的是最后一个，则将将要其左边的人作为最后一个
    			this.last = this.last.getLeft();
    		}
    		this.count--;//减掉圈内人数
    	}
    
    	/** * 数三取一 */
    	public void C3Q() { 
    		int flag = 0;// 计数器
    		Person p = this.first;//默认从第一个开始
    		while (this.count > 1) { 
    			flag++;
    			if (flag == 3) { 
    				this.removePerson(p);
    				System.out.println("移除了：" + p.getId());
    				flag = 0;
    			}
    			p = p.getRight();//“指针”右移
    
    		}
    
    	}
    
    	/** * 构造方法初始化圈的大小 * * @param count * 圈的大小 */
    	public Circle(int count) { 
    		super();
    		for (int i = 0; i < count; i++) { 
    			Person person = new Person(i);// 利用构造方法给圈子赋count个person，i为id
    			this.addPerson(person);
    		}
    	}
    
    }

**测试类**

package com.fjh.test;
    
    import com.fjh.entity.Circle;
    
    public class Count3QuitTest { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Circle circle = new Circle(5);//创建5个person
    		circle.C3Q();
    		System.out.println(circle.getFirst().getId());
    	}
    
    }

**结果**  
![在这里插入图片描述][20190624193040653.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwODk2OTk3_size_16_color_FFFFFF_t_70]: /images/20211227/91069e2dbb014f1295f117f8ff3b0b3f.png
[20190624193040653.png]: /images/20211227/504b5e5e8a7b48ac880d4b82c06a599a.png