首页 / JAVA / java求解约瑟夫问题
java求解约瑟夫问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java求解约瑟夫问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3569字，纯文字阅读大概需要6分钟。
内容图文
文章目录
前言
约瑟夫问题是数据结构中的经典算法题，这里使用java中的单向环形链表解决该问题。
一、问题描述
n个人围成一圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到m的人出圈，接着下一个人又从1开始报数，如此循环，直到剩余人数为0，输出出队序列。例如当n=25,m=12时，出队序列为12，24，11，25，14，3，18，8，1，19，13，7，5，4，6，10，17，23，20，16，22，21，15，9，2。给定n和m，请你输出出队序列。
二、解决思路
题目中描述了n个人围成一圈，所以我们可以使用java中的单向环形链表来模拟该结构，接着我们可以使用双层for循环来不断的数数与出队，直到出队完即可得到结果。
三、过程图解
当出队了1后，curNode就指向了下一节点2，preNode不变，还是curNode的前一节点，当2也出队了后，curNode和preNode就指向了同一节点，此时表示只剩下了最后一人，无需再数，直接出队即可
四、时间复杂度
使用单向循环链表求解的时间复杂度为O(n*m)。
五、代码实现
1.测试代码
代码如下：
package com.yc.linkedlist;
public class Josephu {
public static void main(String[] args) {
Josephu josephu = new Josephu();
CircleSingleLinkedList circleLinkedList = josephu.new CircleSingleLinkedList();
circleLinkedList.add(25);
System.out.println("求解前");
circleLinkedList.list();
System.out.println("求解后");
circleLinkedList.counter(1, 12, 25);
}
class CircleSingleLinkedList {
private Node first;
/**
* 单向循环链表，从no编号开始，不断数数与出队，直到全部人都出队
* @param no 从no编号开始数1
* @param m 出队数到m的那个人
* @param len 总共有多少人
*/
public void counter(int no,int m,int len){
if(no<1||m<1||no>len||first==null){
return;
}
//首先preNode和curNode都指向首节点，此处的首节点不是一般意义上的头节点，里面保存的是第一个人的编号，编号为1
//curNode表示从哪个人开始数，当出队一人后，该节点就会指向出队那个人的下一人，表示从这个人开始重新数，进行新的一轮的判断
//preNode表示不管curNode指向哪一个人，它始终指向curNode的前一个人，该节点用于辅助判断什么时候所有人都已出队
Node preNode = first;
Node curNode = first;
while(true){
//curNode不变，把preNode指向尾节点，因为是循环链表，所以此时preNode就可看成curNode的前一节点
if(preNode.next == first){
break;
}
preNode = preNode.next;
}
//根据参数no，调整preNode和curNode指向的位置
for(int i=1;i<no;i++){
curNode = curNode.next;
preNode = preNode.next;
}
//循环数，直到所有人全部出队
while(true){
//终止条件，当人全部出队时执行该语句
if(preNode == curNode){
break;
}
//从1数到m，然后出队一人，此处的出队会直接丢弃出队那人的节点，然后preNode和curNode就都会发生相应的变化
for(int i=1;i<m;i++){
curNode = curNode.next;
preNode = preNode.next;
}
System.out.print(curNode.no+" ");
curNode = curNode.next;
preNode.next = curNode;
}
System.out.print(curNode.no+" ");
return;
}
/**
* 根据人数生成对应的单向循环链表
* @param num
*/
public void add(int num){
if(num<1){
return;
}
Node curNode = null;
for(int i = 1;i <= num;i++){
if(i==1){
first = new Node(i);
first.next = first;
curNode = first;
}else{
Node newNode = new Node(i);
curNode.next = newNode;
newNode.next = first;
curNode = newNode;
}
}
return;
}
/**
* 打印输出节点
*/
public void list(){
if(first==null){
return;
}
Node curNode = first;
while(true){
System.out.print(curNode.no+" ");
if(curNode.next==first){
break;
}
curNode = curNode.next;
}
System.out.println();
return;
}
}
//单一节点
class Node {
private int no;
private Node next;
public Node(int no){
this.no = no;
}
public Node(){
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
2.代码分析
代码分为三部分，测试代码，节点和单向循环链表，有兴趣的朋友可以测试查看结果。
总结
这是我用数据结构中的链表解决的第一个问题，还是很有收获，希望能和更多的朋友一起进步。
内容总结
以上是互联网集市为您收集整理的java求解约瑟夫问题全部内容，希望文章能够帮你解决java求解约瑟夫问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。