约瑟夫环问题
大致题意：n个人围成一圈(编号从1到n)，从第1个人开始报数，报到m的人出列，从下一个人重新报数，报到m的人出列，依此类推，直至最后一个人。求最后一个人的编号。
假设有10个人围成一圈，编号分别为1 2 3 4 5 6 7 8 9 10，从第一个人开始报数，报到3的人出列，从下一个人重新报数，报到3的人出列，依次类推，直到最后一个人。求最后一个人的编号。
程序实现步骤：
1）从第一个元素开始报数，报3的数组元素值置为-1
2）当我们遍历到数组最后一个元素的时候就需要从头开始遍历
3）遍历数组时，当数组元素值为-1的时候就跳过去，遍历后面不是-1的数组元素
4）直到剩下最后元素，返回该数组元素值
代码实现：
package com.wysheng.src;
/**
* @Author Wang Yongsheng
* @Date 2021/10/30 10:21
* @Version 1.0
*/
public class TestDemo02 {
public static int yusefu(int[] arr,int n) {
int count = 0;//用来报数 1,2,3
int surplus_num = arr.length;//统计剩余的数组元素个数
for (int i = 0; surplus_num > 1; i = ++i % arr.length) {//i = ++i % arr.length用来从头开始遍历数组
if (arr[i] != -1) {
count++;
}
if (count == n) {
arr[i] = -1;//报 3 的人退出
count = 0;
surplus_num--;
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] != -1) {
return arr[i];
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = 3;//报3
int result = yusefu(arr,n);
System.out.println("最后一个数是：" + result);
}
}
运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95576.html
