认为自己很聪明的请进

Question

题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。 关于这样的题目我有一个程序，可是似乎逻辑有问题，谁能看懂程序意思并找出问题？（程序写的不好所以比较难看明白）
public class Test37 { public static void main(String[] args) {
int i,y,m=0;
i = Integer.parseInt(args[0]);
for(int x=1;x<i+1;x++){
y = x;
while(i!=2&&x%3!=0){
x = i%3+x;
i = i-i/3;
if(i==2&&(x+2)%3!=0)
System.out.println(y);
}
}
}}

Answer 1

public class Count3Quit {
public static void main(String[] args) {
boolean[] arr = new boolean[500];
for(int i=0; i<arr.length; i++) {
arr[i] = true;
}

int leftCount = arr.length;
int countNum = 0;
int index = 0;

while(leftCount > 1) {
if(arr[index] == true) {
countNum ++;
if(countNum == 3) {
countNum = 0;
arr[index] = false;
leftCount --;
}
}

index ++;

if(index == arr.length) {
index = 0;
}
}

for(int i=0; i<arr.length; i++) {
if(arr[i] == true) {
System.out.println(i);
}
}
}
}
看看这个吧

Answer 2

还有一种思路：
public class Count3Quit2 {
public static void main(String[] args) {
KidCircle kc = new KidCircle(500);
int countNum = 0;
Kid k = kc.first;
while(kc.count > 1) {
countNum ++;
if(countNum == 3) {
countNum = 0;
kc.delete(k);
}
k = k.right;
}

System.out.println(kc.first.id);
}
}class Kid {
int id;
Kid left;
Kid right;
}class KidCircle {
int count = 0;
Kid first, last;

KidCircle(int n) {
for(int i=0; i<n; i++) {
add();
}
}

void add() {
Kid k = new Kid();
k.id = count;
if(count <= 0) {
first = k;
last = k;
k.left = k;
k.right = k;
} else {
last.right = k;
k.left = last;
k.right = first;
first.left = k;
last = k;
}
count ++;
}

void delete(Kid k) {
if(count <= 0) {
return;
} else if (count == 1) {
first = last = null;
} else {
k.left.right = k.right;
k.right.left = k.left;

if(k == first) {
first = k.right;
} else if( k == last) {
last = k.left;
}
}
count --;
}
}

Answer 3

他NND，到现在我还是不知道怎么回复排版后的程序，寒自己一个！

Answer 4

这个。。用数学方法比较好做的。。int Josephus ( int n , int k ) // n个人，数到k退出
{
int s = 0;
for ( int i = 2 ; i <= n ; i++ )
s = (s+k)%i ;
return s+1 ;
}

Answer 5

看看concrete mathematics的第一章吧,這個問題有個很簡單的做法,但其得來的過程郤很不容易

Answer 6

把數字以bitwise shifting就求到解了

Answer 7

public class TestCircle {
public static void to(int total, int number) {
List<Integer> list = new ArrayList<Integer>(total);
/*
 * 先把这N个人加到list里边来
 */
for (int i = 1; i <= total; i++) {
list.add(i);
}
int begin = -1;
while (total > 0) {
begin += number;
/*
 * list的remove方法是从下标为0的位置开始删除
 */
System.out.println(list.remove(begin % total));
begin = (begin % total) - 1;
total--;
}
} public static void main(String[] args) {
TestCircle.to(8, 3);
}
}
研究研究

Answer 8

我比较笨，但还是写了个方法。public int int Josephus ( int n , int k ){ // n个人，数到k退出
  int i=0,m=1;
  int num [] = new int [n];
  while(true){
    if(num[i++]==k)continue;
    num[i-1]=m++;
    if(m>k+1){
      p++;m=1;
    }
    if(p==k-1)return i;
    if(i>=num.length)i=0;
  }
}

Answer 9

public class Count3Quit {
public static void main(String[] args) {
boolean[]  arr = new boolean[500];

for (int i = 0; i < arr.length;i++) {
arr[i] = true;
}

int leftCount = arr.length;
int countNum = 0;
int index = 0;

while (leftCount > 1) {
if (arr[index] ==true) {
countNum ++;
if (countNum == 3) {
countNum = 0;
arr[index] = false;
leftCount --;
}
}
index ++;

if (index == arr.length) {
index = 0;
}
}
for (int i = 0;i < arr.length;i++) {
if (args[i] == true) {
System.out.println("最后剩下的是第" + i+1  + "个人！");
}
}
}
}

Answer 10

public class TestString {
public static void main(String []args)
{
TestString.repl(3,3);
}
public static void repl(int n,int c)
{
int k=0;
Tes tes = new Tes();
Tes first,e;
tes.num=1;
first=tes;
first.next=first;
for(int i=2;i<=n;i++){
e = new Tes();
e.num=i;
first.next=e;
first=e;
}
first.next=tes;
first=tes;
while(first.next!=first){
k++;
if(k==c-1){
first.next=first.next.next;
k=0;
}
first=first.next;
}
System.out.println(first.num);
}
}public class Tes {
public int num;
public Tes next;
public Tes(){next=null;}
}

Answer 11

用java 不是很难吧：
-------------人的号，与名字在Map中------------------------ public void TestQ(Map<Integer,String> man){
int n =0;
//如果只有两个人，打出来
if(man.size()<=2) {
Iterator<Integer> ite = man.keySet().iterator();
        while (ite.hasNext()) {
            n = ite.next();
            System.out.println(n);
        }
    //超过2人，T掉第三个
}else{
Iterator<Integer> ite = man.keySet().iterator();
        while (ite.hasNext()) {
            n = ite.next();
            if(n==2) {
             //退出的人，打出编号
             System.out.println(n);
             man.remove(n);
             TestQ(man);
             break;
            }
        }
}
}

Answer 12

=====================================下面这个正确===========================
//把人放在map里,有编号，有名称
HashMap a = new HashMap();
a.put("a", "a");
a.put("b", "b");
a.put("c", "c");
a.put("d", "d");
a.put("e", "e");
a.put("f", "f");
a.put("g", "g");
a.put("h", "h");
a.put("i", "i");
a.put("j", "j");
a.put("k", "k");

bird b = new bird();
b.TestQ(a);//游戏部分
public void TestQ(Map<Object,String> man){
int n =1;
Object o;
//如果只有两个人，打出来
if(man.size()<=2) {
Iterator<Object> ite = man.keySet().iterator();
        while (ite.hasNext()) {
            o = ite.next();
            System.out.println("最后的人:"+o);
        }
    //超过2人，T掉第三个
}else{
Iterator<Object> ite = man.keySet().iterator();
        while (ite.hasNext()) {
         n++;
            o = ite.next();
            if(n==3) {
             //退出的人，打出编号
             System.out.println(o);
             man.remove(o);
             TestQ(man);
             return;
            }
        }
}
}
=================================结果=====================
T掉的人:
k
a
h
c
f
j
g
b
最后的人:d
最后的人:e

Answer 13

　约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
　　假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。
　　C++代码示例:
　　#include<iostream>
　　using namespace std;
　　void main()
　　{
　　int n,m,a[101],k,i,j,num; //计数器是从1开始的,所以100个人用101
　　cout<<"请输入参加游戏的玩家人数(不超过100人):";
　　cin>>n;
　　cout<<"----------------------------------------"<<endl;
　　if(n>100)
　　{
　　cout<<"玩家太多,请重新登陆此程序!"<<endl;
　　return;
　　}
　　cout<<"输入游戏中要玩的数字:";
　　cin>>m;
　　cout<<"----------------------------------------"<<endl;
　　for(i=1;i<=n;i++)
　　{
　　a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，
　　}
　　j=0;
　　k=0;
　　for(i=1;i<=n;i++){
　　if(a【i】==1){
　　j=j+a【i】;
　　if(j==m)
　　{
　　j=0;
　　a【i】=0;
　　k++;
　　}
　　if(k==n){
　　num=i;
　　break;
　　}
　　}
　　if(i==n)
　　i=0;
　　}
　　cout<<"最后获胜的玩家是第 "<<num<<" 号玩家!"<<endl;
　　cout<<"----------------------------------------"<<endl;
　　}
　　Pascal代码示例：
　　program YSF;
　　var n,m,k,i,j,num:longint;
　　a:array[1..100] of longint;
　　begin
　　readln(n,m);
　　for i:=1 to n do
　　a:=1;
　　j:=0;
　　k:=0;
　　for i:=1 to n do
　　begin
　　if a=1 then
　　begin
　　j:=j+a;
　　if (j=m) then
　　begin
　　j:=0;
　　a:=0;
　　inc(k);
　　end;
　　if k=n then
　　begin
　　num:=i;
　　writeln(num);
　　halt;
　　end;
　　end;
　　if i=n then i:=0;
　　end;
　　writeln(num);
　　end.

Answer 14

我觉得我应该解释一下意思，不需要围成一圈，因为我用的是排除法，不符合条件的数字会在while(i!=2&&x%3!=0)中被过滤掉，每个数字加上上次总数的余数然后再被3除那么就可以得到这一轮是否被排除的结论，最后剩下2个数字是没有办法通过上面的while得到于是使用if(i==2&&(x+2)%3!=0) 得到最后答案，唉，不知道还有没有人能看到我说的，那些喜欢鬼叫的人你们真该去死！

Answer 15

如果是josephsus環,不用那麼長的代碼,concrete mathematics上有詳細介紹...
public static void josephsus(int n) {
int re = 1;
for (int i = 0; i < Integer.bitCount(n) ; ++i) {
re <<= 1;
}
System.out.println(re - 1 + " survived.");
}
但樓主的意思好像不是josephsus