约瑟夫问题求解
我在网上看到：http://blog.csdn.net/jcwKyl/article/details/3885386他们是用0开始计数，通过动态规划求解这个问题。
他们的思想我都知道。但是我改成从1开始计数，比如：
人的编号从1开始到n；报数也从1开始报到m；
他的递推式应该没有变吧。就是f[n] = (f[n-1]+m%n)%n;
因为：如果m=3；k=3%n+1;
1 ---> k-3
2 ---> k-2
3 --->出列
4 ---> k ---> 1
5 ---> k+1 ---> 2
6 ---> k+2 ---> 3
.
.
.
n --->
f[n] = (f[n-1]+m%n)%n;
但是我的结果就是错误的，我不清楚为什么？
是不是因为我理解有问题？
请教解答~~谢谢！ --------------------编程问答-------------------- 不管从几计数,递推式都不变,高兴地话从10开始数都行
但是C#的数组是从0开始的
楼主从1计数,就需要每次对下标做转换
检查一下是否存在数组的边界问题吧 --------------------编程问答--------------------
什么叫把下标做变换，能不能举个例子~谢谢 --------------------编程问答--------------------
import java.util.Scanner;
public class Yu {
public static void main(String[] args){
int count, num;
int tmp = 0;
int i, killed = 0;
Scanner read = new Scanner(System.in);
System.out.print("请输入总人数:");
count = read.nextInt();
int[] person = new int[count];
for(i = 0; i < count; ++i)
person[i] = 1;
System.out.print("每次数多少人:");
num = read.nextInt();
i = 0;
while(killed != count){
if(i == count)
i = 0;
tmp += person[i];
if(tmp == num){
person[i] = 0;
++killed;
System.out.println((i+1) + " is killed");
tmp = 0;
}
++i;
}
System.out.println("剩下: " + i);
}
}
--------------------编程问答--------------------
比如你的下标是 a1,a2,a3,a4
数组下标从0开始,用数组存放就是b[0],b[1],b[2],b[3]
下标转换就是说你想从数组中取ai,就得把下标变成b[i-1],思路不清晰的话,容易产生边界问题 --------------------编程问答--------------------
这个貌似有错误，一次不能数一个人 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- 我这儿有C语言的http://blog.csdn.net/flyfeifei66/article/details/5382455
大学学数据结构的时候写的 --------------------编程问答-------------------- --------------------编程问答--------------------
public class JosephusTest {
public static void main(String[] args) {
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);
}
}
补充：Java , Java SE
