高难度的约瑟夫环
题目如下：提高挑战难度:编号为1~N的N个人按顺时针方向
围坐一圈，每人持有一个密码(正整数，可以自由
输入)，
开始人选一个正整数作为报数上限值M，
从第一个人按顺时针方向自1开始顺序报数，报道M
时停止报数。报M的人出列，将他的密码作为新的M
值，从他顺时针方向上的下一个人开始从1报数，一
如此下去，直至所有人全部出列为止。(题目出处：（小甲鱼）数据结构和算法 18约瑟夫环)
因为我最近在学java 所以就用Java照这个思路做了一下代码如下//作者：铁头娃鸭
//日期：2020.6。11
//作用：进阶约瑟夫环（每个人都拿着一个密码数字，数密码上线次
import java.io.*;
import java.util.*;
public class work7{
public static void main(String args[]){
Cyc_link cyclink=new Cyc_link();
cyclink.set_len();
cyclink.create_link();
cyclink.set_k();
cyclink.play();
}
}
class Child{
int no;//编号
int key;//手上持有的密码
Child next=null;
public Child (int no){
this.no=no;
}
}
class Cyc_link{
Scanner sr=new Scanner(System.in);
// 先定义一个指向链表第一个小孩的的引用（头结点）
Child first_child=null;
Child temp=null;//跑龙套的temp
int len=0;//表示共有几个小孩
int k=0;//从第几个小孩开始数
int key=0;
public void set_len(){
System.out.println("参加游戏的人数");
this.len=sr.nextInt();
}
public void set_k(){
System.out.println("从第几个人开始数?");
this.k=sr.nextInt();
}
public void create_link(){
System.out.println("开始围成一个圈，并赋予每人人手上一位密码,");
for(int i=1; i<=len;i++){
if(i==1){ //创建第一个小孩
Child ch=new Child(i);
this.first_child=ch;
this.temp=ch;
System.out.print("第"+i+"人的密码:");
ch.key=sr.nextInt();
}
else {
if (i==len){//最后一个小孩
Child ch=new Child(i);
System.out.print("第"+i+"人的密码:");
ch.key=sr.nextInt();
temp.next=ch;
temp=ch;
temp.next=this.first_child;
}
else {//其余小孩
Child ch=new Child(i);
System.out.print("第"+i+"人的密码:");
ch.key=sr.nextInt();
temp.next=ch;
temp=ch;
}
}
}
}
public void play(){//开始游戏
//首先找到第个数数的那个人
for (int i=1;i<k;i++){
temp=temp.next;
}
this.key=temp.next.key;
//再开始数数并退圈
while(temp!=temp.next){
for (int i=1;i<=this.key;i++){
temp=temp.next;
}
this.key=temp.next.key;
System.out.print("推出圈的人:"+temp.next.no+" ") ;
temp.next=temp.next.next;
}
System.out.println("最后存活的人 ："+temp.no);
}
}
测试结果如下
参加游戏的人数
10
开始围成一个圈，并赋予每人人手上一位密码,
第1人的密码:2
第2人的密码:3
第3人的密码:4
第4人的密码:7
第5人的密码:6
第6人的密码:11
第7人的密码:22
第8人的密码:11
第9人的密码:1
第10人的密码:11
从第几个人开始数?
2
推出圈的人:5 推出圈的人:2 推出圈的人:7 推出圈的人:9 推出圈的人:1 推出圈的人:6 推出圈的人:4 推出圈的人:10 推出圈的人:8 最后存活的人 ：3
{:10_275:} 都没加空格，把我难受的。 徐颖科 发表于 2020-6-12 07:57
都没加空格，把我难受的。
哈哈不是有冒号嘛
页:
[1]