求解一个java小程序
求解“约瑟夫问题”：12个人排成一圈，从1号报数，凡是数到5的人就走出队列（出局），然后继续报数，试问最后一个出局的是谁？ 问题点数：20、回复次数：19Top
1 楼fang830422（）回复于 2006-11-16 09:23:36 得分 0
最后一个出局的是6号,最后只留下1号自己!Top
2 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:18:14 得分 0
package org.luyang;
import java.util.ArrayList;
import java.util.List;
public class Circus {
public static void main(String[] args) {
String[] str = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K",
"L" };
List arrays = new ArrayList();
for (int i = 0; i < str.length; i++) {
arrays.add(str[i]);
}
deleteElement(arrays);
}
private static void deleteElement(List arr) {
int index = 0;
while (arr.size() != 1) {
for (int i = 0; i < arr.size(); i++){
if (index == 4) {
System.out.println((String)arr.get(i));
arr.remove(i);
index = 0;
}
index++;
}
}
System.out.println("the lucky man is " + (String)arr.get(0));
}
}
结果：
delete E
delete J
delete C
delete I
delete D
delete L
delete G
delete F
delete H
delete A
delete B
the lucky man is KTop
3 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:22:30 得分 0
好像有点问题。Top
4 楼Matthiola（Matthiola）回复于 2006-11-16 10:34:02 得分 0
public class Test {
/**
* @param args
* @throws MyException
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//求解“约瑟夫问题”：12个人排成一圈，从1号报数，凡是数到5的人就走出队列（出局），然后继续报数，试问最后一个出局的是谁？
//第一次为12人 读到5的时候 就 变成11人
//第2次是11人 读到5的时候 变成10人
//第3次是10人 读到5的时候变成 9人
// 5 9 5 8
// 6 8 5 7
//7 7 5 6
// 8 6 5 5
// 9 5 5 4
//此时 循环结束
//由此 可见 报数最多只能报 7圈 那么就是求 第7圈 出局的哪个人；
int nRound = 8;
//外层 循环是 7 圈，分析可得 每循环一次 就少一个人
//初始第1圈的人 为 12人
int nPeople = 12;
String str = "ABCDEFGHIJKL";
StringBuffer buffer = new StringBuffer();
String strTemp ="";
for(int i = 1; i < nRound + 1; i++)
{
for(int j = 0; j < nPeople; j++)
{
if(i == 1)
{
if(j==4)
{
System.out.println("第"+i+"次出局的哪个人是："+str.charAt(j));
}else{
buffer.append(str.charAt(j));
}
}else{
if(j==4)
{
System.out.println("第"+i+"次出局的哪个人是："+strTemp.charAt(j));
}else{
buffer.append(strTemp.charAt(j));
}
}
}
strTemp = buffer.toString();
nPeople--;
buffer = new StringBuffer();
}
}
}
Top
5 楼Matthiola（Matthiola）回复于 2006-11-16 10:37:11 得分 0
恩 你好想题目理解和我不一样
根据这句话 "从1号报数，凡是数到5的人就走出队列（出局），然后继续报数"
的意思 好象是 数完1圈 在从1 开始报 数到 5
否则 就会出现 (逢5才出列) 个人认为那是错的,.....Top
6 楼Matthiola（Matthiola）回复于 2006-11-16 10:41:15 得分 0
上面 注释有点问题 不是 7圈 是 8圈Top
7 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:44:50 得分 20
package org.luyang;
import java.util.ArrayList;
import java.util.List;
public class Circus {
public static void main(String[] args) {
String[] str = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K",
"L" };
List arrays = new ArrayList();
for (int i = 0; i < str.length; i++) {
arrays.add(str[i]);
}
deleteElement1(arrays);
}
private static void deleteElement1(List arr) {
int index = 0;
while (arr.size() != 1) {
for (int i = 0; i < arr.size(); i++){
if (index == 4) {
if (i != arr.size() - 1) {
System.out.println("delete " + (String)arr.get(i));
arr.remove(i);
index = 0;
} else {
System.out.println("delete " + (String)arr.get(i));
arr.remove(i);
index = -1;
}
}
index++;
}
}
System.out.println("the lucky man is : " + (String)arr.get(0));
}
}Top
8 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:45:09 得分 0
delete E
delete J
delete C
delete I
delete D
delete L
delete H
delete G
delete K
delete B
delete F
the lucky man is : ATop
9 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:46:17 得分 0
经过上面的改造，发现好像对了，刚才考虑的时候忘记了
如果被删除的正好是最后一个的 case。Top
10 楼Matthiola（Matthiola）回复于 2006-11-16 10:50:54 得分 0
你的做法好象是 逢5的倍数 出啊 ?Top
11 楼luyang1016（闭月羞花猫）回复于 2006-11-16 10:52:47 得分 0
lz 的意思应该就是这样的吧。Top
12 楼Matthiola（Matthiola）回复于 2006-11-16 10:57:38 得分 0
哦 ~~
Top
13 楼guwei1986（）回复于 2006-11-16 11:17:48 得分 0
闭月羞花猫,问一下,为什么最后一个时要将index设为-1呢?Top
14 楼xianggang101（tanjun）回复于 2006-11-16 11:47:23 得分 0
public class Ysf
{
private int[] p={1,2,3,4,5,6,7,8,9,10,11,12};
private int interval=5;
private int leave=1,index=-1,count=12;
public static void main(String[] args)
{
Ysf y=new Ysf();
y.x();
}
void x()
{
while (true)
{
for (int i=0;i<interval;)
{
index=(index+1)%count;
if(p[index]!=0)
i++;
}
if(leave==count)
{
break;
}
System.out.println(p[index]);
p[index]=0;
leave++;
}
}
}Top
15 楼luyang1016（闭月羞花猫）回复于 2006-11-16 12:37:20 得分 0
闭月羞花猫,问一下,为什么最后一个时要将index设为-1呢?
==================================================
看起来似乎有点乱，呵呵。
index++ 之后，-1 就变成 0 了阿。正好是从 0 开始数 A。Top
16 楼luyang1016（闭月羞花猫）回复于 2006-11-16 12:43:50 得分 0
个人觉得还是
xianggang101(tanjun) ( ) 信誉：100 Blog
更好。Top
17 楼luyang1016（闭月羞花猫）回复于 2006-11-16 12:54:00 得分 0
while (arr.size() != 1) {
System.out.println("the " + count + " round : ");
for (int i = 0; i < arr.size(); i++){
if (index++ == 4) {
System.out.println("delete " + (String)arr.get(i));
arr.remove(i);
if (i != arr.size() - 1) {
index = 1;
} else {
index = 0;
}
}
}
count++;
}
==============================================
to： guwei1986() ( ) 信誉：100 Blog
这样就明确了。Top
18 楼fangfang1985（）回复于 2006-11-16 15:41:50 得分 0
完美解决，题目简单
结果：
the 1 man is:5
the 2 man is:10
the 3 man is:3
the 4 man is:9
the 5 man is:4
the 6 man is:12
the 7 man is:8
the 8 man is:7
the 9 man is:11
the 10 man is:2
the 11 man is:6
the 12 man is:1
//程序
public void main()
{
int time=1;
int index=0;
int data =1;
int who =99;
int num =12;
int people[]={1,2,3,4,5,6,7,8,9,10,11,12};
while(!(num==1))
{
index=(index+1)%people.length;
data++;
if(data==5)
{
who=people[index];
System.out.println("the "+time+" man is:"+who);
num--;
time++;
data=1;
int temp[]=new int [num];
for(int i=0;i<index;i++)
{
temp[i]=people[i];
}
for(int i=index+1;i<people.length;i++)
{
temp[i-1]=people[i];
}
people=null;
System.gc();
people=new int[num];
for(int i=0;i<temp.length;i++)
{
people[i]=temp[i];
}
}
}
who=people[0];
System.out.println("the "+time+" man is:"+who);
}Top
19 楼xianggang101（tanjun）回复于 2006-11-19 20:27:14 得分 0
我是从C++的经典写法翻译过来的。Top
