package newjosephu;
public class myfinaljosephu {
//你可能会说crazy
//我只想说ez!
public static void main(String[] args)
{
circlelinkedlist list = new circlelinkedlist();
list.add(100);
//list.shownode();
list.outnode(2,1);
}
}
class circlelinkedlist
{
node first = null;
public void add(int num)
{
node curnode = null;
for(int i=1;i<=num;i++)
{
node s = new node(i);
if(i==1)
{
first = s;
first.next = first;
curnode = first;
}
else
{
curnode.next = s;
s.next = first;
curnode = curnode.next;
}
}
}
public void shownode()
{
node s = first;
while(true)
{
System.out.println(s.number);
if(s.next==first)
{
break;
}
s = s.next;
}
}
public void outnode(int count,int no)
{
//count 是数几次
//sum 是有几个数,跟前面的比较
//no 是从第几个开始数
node helper = first;
//helper是位于first之后的一个指针
while(helper.next!=first)
{
helper = helper.next;
}
//从第几个人开始数
for(int i=0;i<no-1;i++)
{
first = first.next;
helper = helper.next;
}
//数几次--直到最后一个
while(helper!=first)
{
for(int i=0;i<count-1;i++)
{
first = first.next;
helper = helper.next;
}
System.out.println(first.number+"出圈了!");
first = first.next;
helper.next = first;
}
System.out.println("最后幸存的是"+first.number);
}
}
class node
{
int number;
node next;
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public node(int number) {
super();
this.number = number;
}
public node getNext() {
return next;
}
public void setNext(node next) {
this.next = next;
}
public String toString() {
return "node [number=" + number + "]";
}
}
约瑟夫环问题
你可能会说crazy,但我只想说EZ。
-
好啦!我们拥有了一个环形链表,现在我们就可以进行之前的游戏了
-
首先我们先想想,因为我们要删除一个小朋友,就得让他之前的那个node的下一个不再指向它,这很容易理解,因为他已经退出游戏了,所以!我们需要两个指针--一个用来找到我们要退出游戏的小朋友,另一个就在前一个指针的后面,准备把这个小朋友之前的那个节点的指向从要退出游戏的小朋友的身上移开!
所以--我们定义一个front,就是代表我们环形链表的开头,根据之前的分析,我们还需要ige指向front之后一位的节点
所以我们定义一个helper来帮助我们,我们先让他加入我们的队伍--helper = front ,为了让他在front的背后,我们选择用while遍历,直到helper.next = front 说明helper已经来到了front的后一个,目的实现了!
-
接着,准备工作完全完成,开始了游戏 。首先,我们要找到第一个开始的小朋友,因为不一定是从第一个小朋友开始的--这很ez
我们只需用while循环,一个一个遍历即可
-
接着选出人淘汰,由于第一个小朋友就会报1,如果我们逢2淘汰的话,那么我们的指针大队只用移动一位就可以了,所以
i = 0;i<count-1;i++
找到了要淘汰的就开始行动 头指针先离开
head = head.next
然后让后面的节点连接到头指针的新位置
cur .next = head;
-
如此重复,直到链表只剩下一个节点!;此时helper == first
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)