(7)求解约瑟夫环问题(选作) 有N个犯人站成一圈,从第S个人开始数起,每数到第D个犯人,就拉出来处决,然后再数D个,再处决,以此类推,直到剩下最后一个赦免。 设N=5,S=1,D=2时,约瑟夫环执行情况。使用数组存储每人的编号,数组下标按循环方式递增。对于N,S,D的任意一组值,显示出环者次序,并显示赦免人的编号。用java语言实现
时间: 2023-04-06 15:01:35 浏览: 76
我可以回答这个问题。以下是Java语言实现约瑟夫环问题的代码:
import java.util.ArrayList;
public class JosephusProblem {
public static void main(String[] args) {
int N = 5; // 犯人数量
int S = 1; // 开始数的位置
int D = 2; // 数的间隔
ArrayList<Integer> prisoners = new ArrayList<Integer>();
for (int i = 1; i <= N; i++) {
prisoners.add(i);
}
int index = S - 1;
while (prisoners.size() > 1) {
index = (index + D - 1) % prisoners.size();
prisoners.remove(index);
}
System.out.println("约瑟夫环执行情况:");
for (int i = 0; i < prisoners.size(); i++) {
System.out.print(prisoners.get(i) + " ");
}
System.out.println("赦免人的编号:" + prisoners.get(0));
}
}
阅读全文