锐客网

  1. 首页 > 生活百科 > it技术 > >

包含JAVA围坐一圈报数代码的词条

IT技术报数

n个小孩围成一个圈,从一开始数,数到七的人出列,求依次出列的次序. 求用java写这个问题是很经典的编程问题 ， 叫约瑟夫环问题 ， 我之前有写程序，所以直接拷给你吧，我初始的n值为13，你也可以自己修改
//YueSeFu.java
public class YueSeFu {
public static void main(String[] args)
{
final int n=13,s=1,m=5;//n为总人数 ， 从第1个人开始报数，报数到m的出圈
int[] p=new int[n];//数组p用于标记已出圈的人
int[] q=new int[n];//数组q存放出队的顺序
int i,j,k,N=0;
k=s-2;//k从1开始数出圈人的下标
for(i=1;i=n;i)
{
for(j=1;j=m;j)//从1到m报数，计算出圈人的下标k
{
if(k==n-1)//当出圈人的下标达到末尾时
{
k=0;//出圈人的下标从0开始
}
else
k;//否则下标 1
if(p[k]==1)//若平p[k]=1，说明下标为k的人已出圈
{
j--;//由于让过已出圈的人，所以j要-1，以保证每次数过m个人
}
}
p[k]=1;//将下标为k的数组元素置1，表示出圈
q[N]=k 1;//将下标为k的人的编号k 1,存入数组元素q[N]中
}
System.out.println("出圈顺序为：");
for(i=0;in;i)
{
System.out.print(q[i] "");
}
}
}
10个人排成圈，然后报数，报到7的人出列 ， 然后从第八个人再开始报一，，，，，循环 。求java代码！public class Josephus{
public static void main(String[] args) {
mAndN(7,10);
}
public static void mAndN(int m, int n) {
CircleList cl = new CircleList(n);
cl.showSequence(m);
}
}
class CircleList{
Node head;
CircleList(int n){
head = new Node(1);
Node tail = head;
Node temp;
for(int i = 2;i = n;i){
temp = new Node(i);
tail.setNext(temp);
tail = temp;
}
tail.setNext(head);
}
public void showSequence(int m) {
Node temp = head;
System.out.println("The sequence of getting out:");
while(head != head.getNext()){
for(int i = 0;im;i)
temp = temp.getNext();
System.out.print(temp.getNumber()" ");
remove(temp);
head = temp;
}
System.out.println(head.getNumber());
}
public void remove(Node n){
n.setNumber(n.getNext().getNumber());
n.setNext(n.getNext().getNext());
}
}
class Node{
private int i;
private Node next;
Node(int i){
this.i = i;
}
public void setNumber(int i){
this.i = i;
}
public void setNext(Node next){
this.next = next;
}
public int getNumber(){
return i;
}
public Node getNext(){
return next;
}
}
输出：
The sequence of getting out:
8 6 5 7 10 3 2 9 4 1
java编程17人编号为0-16围成一圈，0号人开始从1报数，凡是报数为3倍数的人离开圈子 ， 继续到一个，问他编号这是一个约瑟夫环的问题
解答如下：
依据提议，可以将题目等价变换为：“n(n=17)人编号为0到(n-1)围成一圈，0号人开始从0报数，凡是报数为m-1 (m=3)倍数的人离开圈子，继续到一个，问他编号”
一开始的状态
0,1 ， 2，3，4，5 ..... (n-2), (n-1) 【n个人】
第一个人被踢之后 设第一个被踢的人的编号为k, 则 k = m%n-1 【当n=17,m=3时,k=2 。也就是说编号为2的人离开了圈子】
这时候的状态
0, .... (k-1), (k 1) ,(k 2)...(n-2),(n-1) 【(n-1)个人,当n=17,m=3时: 0,1,3,4,5,6,7,8,9,10,11,12,13,14,15,16】
将这时候的编号做转换. 因为是围城一个圈子，下一个开始数的是(k 1).所以也可以表示为
(k 1),(k 2) ... (n-2),(n-1),0....(k-1) 【(n-1)个人,当n=17,m=3时: 3,4,5,6,7,8,9,10,11,12,13,14,15,16,0,1】
重新编号 。得到：
0，1 ， 2，3 ， 4...(n-3),(n-2)【（n-1）个人】 这个时候 ，这里重新构成了一个约瑟夫环 。也就是说，这是一个递推的关系 。
这里我们进行了重新编号 。那么 (n-1)个人和 n个人之间的编号不一样的 。但是两者之间有一定的关系，可以冲新编号推导出老的
公式如下： i' = (i k)%(n-1) 【比如，当n=17,m=3时 . 新的环编号是 (n-2),我要求他在老的环中的编号，那么编号是 i' = ( (n-2)k ) % (n-1) = 17 = 1,就是老的换种编号为1的那一个 】
反过来有 ：i= (i' m)%n
有了上面的推断，可以代码如下：
int ysf(int n,int m){
if(n==1){
return 0; //当环内只有一个人的时候，就是他自己
}
return (ysf(n-1,m)m ) % n ;
}
------------------完整代码---------------------
public class Test{
public static void main(String[] args){
int a = 17;
int b = 3;
System.out.println(ysf(a,b));
}
static int ysf(int n,int m){
if(n==1){
return 0;
}
return (ysf(n-1,m)m) % n;
}
}
n个人围成一圈报数，报到3的人退出，依次直到剩下一人 ， 这人是第几个人？用java ， 不知道哪里错昨天改了下 ， 忘了跟你回答了 ， 刚想起来，我把你的main稍微修改了下，你试试 。我测得可以 。
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入一个正整数：");
int num = input.nextInt();
int[] nums = new int[num];
for (int i = nums.length - 1; i = 0; i--) {
nums[i] = i1;
}
// 数组定义完毕
int i = 0;
int count = 0;
boolean flag = false;
int temp1 = -1, temp2 = -1;
while (!flag) {
if (nums[i] == 0) {
i;
if (i == nums.length)// 到头循环
i = 0;
continue;
}
count;// 计数还在游戏中的人所报的数
if (count == 1)// 报数时报到1的人
temp1 = i;
if (count == 2)// 报数时报到2的人
temp2 = i;
if (temp1 == temp2) {// 如果报数报到1的人等于报数报到2的人 只剩1人 ， 退出，输出此人
flag = true;
continue;
}
if (count == 3) { // 报到3的人退出
count = 0;
nums[i] = 0;
// num--;
}
// if(num == 1)
// break;
i;
if (i == nums.length)// 到头循环
i = 0;
}
System.out.println(nums[i]);
}
java问题：500个孩子围成圈，从第一个开始报数 ， 逢3退出 ， 然后从下一个孩子继续开始报数，直到只剩下一个逢3退出,我的理解是数字中带3的, 3 13 2330-39这些都是.
看了一下约瑟夫环,说的是 3的倍数.所以做了,两个判断方法.
isMod3
isMeet3
从实现上来说,用list这样的集合方便一些.数组不具有删除相应元素的能力,只能写方法来处理.
fun1- list
fun2- 用一个自定义对象数组
fun3 - 用int[]数组来处理.
你看一下吧.希望对你有帮助.
---------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.List;
public class Test1 {
public static void main(String[] args) throws Exception {
new Test1().fun1();
new Test1().fun2();
new Test1().fun3();
}
public void fun1() {
List listUser = new ArrayList();
for (int i = 1; i = 500; i) {
listUser.add(i);
}
int index = 0;
int count = 1;
while (listUser.size()1) {
// if (isMod3(count)) {
if (isMeet3(count)) {
listUser.remove(index);
index--;
}
if (listUser.size() ==index) {
index = 0;
}
}
System.out.println(listUser.get(0));
}
// 例3,6,9
public boolean isMod3(int x) {
return x % 3 == 0;
}
// 例3,13,23,30,31....
public boolean isMeet3(int x) {
boolean result = false;
while (x0) {
if (x % 10 == 3) {
result = true;
break;
}
x = x / 10;
}
return result;
}
public void fun2() {
User[] users = new User[500];
for (int i = 0; iusers.length; i) {
users[i] = new User();
users[i].no = i1;
}
int index = 0;
int meet = 1;
int count = 0;
while (users.length - count1) {
if (index == users.length) {
index = 0;
}
if (users[index].isDelete) {
index;
continue;
}
if (isMeet3(meet)) {
count;
users[index].isDelete = true;
}
meet;
index;
}
for (int i = 0; iusers.length; i) {
if (!users[i].isDelete) {
System.out.println(users[i].no);
}
}
}
class User {
int no = 0;
boolean isDelete = false;
}
public void fun3() {
int[] users = new int[500];
for (int i = 0; iusers.length; i) {
users[i] = i1;
}
int index = 0;
int count = 1;
while (users.length1) {
if (isMeet3(count)) {
users = arrayRemoveIndex(users, index);
index--;
}
if (users.length ==index) {
index = 0;
}
}
System.out.println(users[0]);
}
public int[] arrayRemoveIndex(int[] array, int index) {
int[] newArray = new int[array.length - 1];
int arrayIndex = 0;
for (int i = 0; iarray.length; i) {
if (i == index) {
continue;
}
newArray[arrayIndex] = array[i];
}
return newArray;
}
}
java：N个人坐一圈，从1号开始报数，报到3的人退出圈，到剩下两个人停止 。问剩下的两个人的序号是多少 。这是著名JAVA围坐一圈报数代码的约瑟夫问题 看图
采纳
【包含JAVA围坐一圈报数代码的词条】关于JAVA围坐一圈报数代码和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：机架式服务器怎么打开 机架服务器怎么下架拆图解

    下一篇：如何将笔记本电脑转变为游戏服务器？ 笔记本怎么弄成游戏服务器