import java.io.*;
import java.util.*;public class YSF {
LinkedList<Integer> ysf = new LinkedList<Integer>();
int m, pos = -1;
public void create() throws Exception {
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
String line = rd.readLine();
m = Integer.parseInt(rd.readLine());
for (String str : line.split(" ")) {
try {
ysf.add(Integer.parseInt(str));
} catch (NumberFormatException e) {
}
}
}
public void couter() {
if (ysf.size() == 1) {
System.out.print(ysf.get(0) + ",");
ysf.remove(0);
return;
}
pos = (pos + m) % ysf.size();
m = ysf.get(pos);
System.out.print(m + ",");
ysf.remove(pos--);
}
public void doYSF() {
for (;ysf.size() != 0; couter());
System.out.print("\n");
}
public void run() throws Exception {
create();
doYSF();
} public static void main(String[] args) throws Exception {
new YSF().run();
}
}
import java.util.*;public class YSF {
LinkedList<Integer> ysf = new LinkedList<Integer>();
int m, pos = -1;
public void create() throws Exception {
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
String line = rd.readLine();
m = Integer.parseInt(rd.readLine());
for (String str : line.split(" ")) {
try {
ysf.add(Integer.parseInt(str));
} catch (NumberFormatException e) {
}
}
}
public void couter() {
if (ysf.size() == 1) {
System.out.print(ysf.get(0) + ",");
ysf.remove(0);
return;
}
pos = (pos + m) % ysf.size();
m = ysf.get(pos);
System.out.print(m + ",");
ysf.remove(pos--);
}
public void doYSF() {
for (;ysf.size() != 0; couter());
System.out.print("\n");
}
public void run() throws Exception {
create();
doYSF();
} public static void main(String[] args) throws Exception {
new YSF().run();
}
}
http://topic.csdn.net/u/20120627/20/4f300b35-b616-4d3d-8a22-e5313f9fc3cb.html
import java.io.*;
import java.util.*;public class YSF {
static LinkedList<Integer> ysf = new LinkedList<Integer>();
static int m, pos = -1; public static void main(String[] args) throws Exception {
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
String line = rd.readLine();
m = Integer.parseInt(rd.readLine());
for (String str : line.split(" "))
ysf.add(Integer.parseInt(str));
for (;ysf.size() != 1; ysf.remove(pos--)) {
pos = (pos + m) % ysf.size();
m = ysf.get(pos);
System.out.print(m + ",");
}
System.out.print(ysf.get(0) + "\n");
}
}
System.out.println(josephus2(5));
} /**
* 计算约瑟夫问题,间隔 1 个的值,这个有数学解法,即:将最高位的 1 取出,将数值左移一位,
* 再将最高位的那个 1 添至最低位即可<br />
* 例如 1010 的约瑟夫间隔为 1 的值为 0101(5)。Concrete Mathematics 书中并未加 1,
* 那是由于其第一个从 0 开始的,如果从 1 开始时需要加 1<br />
* 算法参考:Concrete Mathematics 一书第一章最后部分
*
* @param count
* @return
*/
public static int josephus2(int count) {
int n = (count ^ leftOneBit(count)) << 1;
return (n | 1) + 1;
} /**
* 获得一个数最高位为 1 的值,比如 1111(15)的最高位值为 1000<br />
* 算法参考:Hacker's Delight 一书第三章
*
* @param num
* @return
*/
public static int leftOneBit(int num) {
for(int i = 0; i < 5; i++) {
num |= (num >> (1 << i));
}
return num - (num >>> 1);
}
}这个算法的复杂度可以是 O(1),Concrete Mathematics 的作者高德纳等人不简单,这应该是效率最高计算间隔为 1 约瑟夫环的算法了。当然了 Hacker's Delight 一书的作者也很了不起!