<强>一、简介
约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”)。
<>强例子:
len个人围成一个圈,玩丢手绢游戏。从第k个人开始,从1开始数数,当数到m时,数米的人就退出圈子,当圈子只剩下一个人为止。
<强>问题分析与算法设计
约瑟夫问题并不难,但求解的方法很多,题目的变化形式也很多。这里给出一种实现方法。
题目中len个人围成一圈,因而启发我们用一个循环的链来表示,可以使用结构数组来构成一个循环链。结构中有两个成员,其一为指向第一个孩子的头节点,另一个为作为判断的节点临时(负责跑龙套)。
具体代码如下:
包demo11;/* *
*约瑟夫问题,化为丢手绢
*
* @author tianq思路:建立一个孩子类一个循环列表类CyclLink
*/公开课demo11 {
公共静态void main (String [] args) {
CyclLink cyclink=new CyclLink ();
cyclink.setLen (15);
cyclink.createLink ();
cyclink.setK (2);
cyclink.setM (2);
cyclink.show ();
cyclink.play ();
}
}//先建立一个孩子类
类孩子{//孩子的标识
int没有;
孩子nextChild;//指向下一个孩子
公共子(int) {//构造函数给孩子一个id
这一点。没有=;
}
}
类CyclLink {//先定义一个指向链表第一个小孩的引用//指向第一个小孩的引用,不能动
孩子接着=零;
孩子temp=零;
int len=0;//表示共有几个小孩
int k=0;//开始的孩子
int m=0;//数到几推出//设置m
公共空间setM (int) {
这一点。m=m;
}//设置链表的大小
公共空间setLen (int len)
{
这一点。len=兰;
}//设置从第几个人开始数数
公共空间setK (int k) {
这一点。k=k;
}//开始玩
公共空间玩(){
孩子temp=this.firstChild;//1 .先找到开始数数的人
for (int i=1;我& lt;k;我+ +){
temp=temp.nextChild;
}
而这。len !=1) {//2 .下数米
for (int j=1;j & lt;m;j + +) {
temp=temp.nextChild;
}//找到要出圈的前一个小孩
孩子temp2=temp;
而(temp2。nextChild !=temp) {
temp2=temp2.nextChild;
}//3 .将数到m的小孩,退出
temp2。nextChild=temp.nextChild;//让临时指向下一个数数的小孩
temp=temp.nextChild;//this.show ();
this.len——;
}//最后一个小孩
system . out。println(“最后出圈”+ temp.no);
}//初始化环形链表
公共空间创建(){
for (int i=1;我& lt;=兰;我+ +){
如果(i==1) {//创建第一个小孩
孩子ch=new(我);
这一点。接着=ch;
这一点。temp=ch;
其他}{
如果我==len () {//创建第一个小孩
孩子ch=new(我);
temp.nextChild=ch;
temp=ch;
temp.nextChild=this.firstChild;
其他}{//继续创建小孩
孩子ch=new(我);
temp.nextChild=ch;
temp=ch;
}
}
}
}//打印该环形链表
公共空间展示(){
孩子temp=this.firstChild;
{做
System.out.print (temp。+ " ");
temp=temp.nextChild;
}
而(临时!=this.firstChild);
}
}
结果:
以上就是本文关于java编程约瑟夫问题实例分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
