问个经典的算法。。大家来动动脑筋

Question

 n个人围成一圈,从第一个人开始依次从1到m循环报数,当报到m的时候此人出圈,然后从下一个人开始重新报数，直到圈中只剩一人为止.打印出最后一个人的原始编号和出圈序列

Answer 1

#define   m   20   
  #define   n   3   
  struct   person   
  {   int   number;   
      int   nextp;   
  }link[m+1];   
  main()   
  {   int   i,count,h;   
      for(i=1;i<=m,i++)   
      {     if(i==m)   
              link[j].nextp=1;   
              else   
                link[i].nextp=1;   
            link[i].number=1;   
      }   
      printf("\n");   
      count=0;   
      h=m;   
      printf("出圈成员及顺序：");   
      while(count<m-1)   
      {   i=0;   
          while(i<>n)   
          {     h=link[h].nextp;   
                if(link[h].number)   
                    i++;   
            }   
            printf("%6d",link[h].number);   
            link[h].number=0;   
            count++;   
    }   
      printf("\n   最后的成员是     ");   
      for(i=1;i<=m;i++)   
      if(link[i].number)   
          printf("%6d",link[i].number);   
  }

Answer 2

import java.util.ArrayList;
import java.util.List;public class TestCircle {
  public static void to(int total, int number) {
    List<Integer> list = new ArrayList<Integer>(total);
    for(int i=1;i<=total;i++) {
      list.add(i);
    }    
    int begin=-1;
    while(total>0) {
      begin+=number;
      System.out.println(list.remove(begin%total));
      begin--;
      total--;
    }
  }  /**
   * @param args
   */
  public static void main(String[] args) {
    TestCircle.to(5, 2);
  }
}

Answer 3

一个"出圈算法",网上一搜一大堆,以前用C写过,现在没时间写了,在网上贴过来一个,楼主先看着,有时间再写一个出来.
楼主看的时候注意一下,他这里说到指针,Java没有指针这个概念,这里可能是计数器,或什么的,不影响阅读.import java.util.*;
public class Test
{public   final   void outc(int len,int cnum)//len是这个圈里的总人数，cnum是当这个圈里的人数到这个数就出圈
   {
    if(cnum<1)cnum=1;//修证，因为报数是从正数开始的
    int []a=new int [len];//生成有这样一个有这些人的圈子
    for(int i=0;i<len-1;i++)
    {
     a[i]=i+1;//生成连表
    }
    a[len-1]=0;//形成了一个圈有指针的作用
    int count=len;
    int num=0;
    int p=len-1;//用作指针
    int []b=new int[len];
    while(count>=1)//当为一个人时，就说明人游戏结束
    {
     num++;//报数加一
  
     if(num==cnum)//如果到了报的数
     {
      num=0;//重新报数
      count--;//圈子里的人数减一
      b[len-count-1]=a[p]+1;//修改指针再次形成圈
      a[p]=a[a[p]];
   
     }
     else
     {
      p=a[p];//得到下一个指针
     }
    }
    System.out.println ("最后一个出圈的人："+(p+1));//输出结果
    for(int j=0;j<len;j++)
    {
     System.out.println ("第"+(j+1)+"个人的出圈编号:"+b[j]);//遍历输出
    }
   }
public static void main (String[] args) {
   Test t=new Test();
   t.outc(100,10);
}  
}

Answer 4

一个小错误，呵呵，修正了
import java.util.ArrayList;
import java.util.List;public class TestCircle {
  public static void to(int total, int number) {
    List<Integer> list = new ArrayList<Integer>(total);
    for (int i = 1; i <= total; i++) {
      list.add(i);
    }
    int begin = -1;
    while (total > 0) {
      begin += number;
      System.out.println(list.remove(begin % total));
      begin = (begin % total) - 1; // 这里修正了一下
      total--;
    }
  }  /**
   * @param args
   */
  public static void main(String[] args) {
    TestCircle.to(5, 2);
  }
}

Answer 5

能解释下不？写点注释。我写的 挺傻import java.util.ArrayList;
import java.util.*;public class Test1{
  public static void to(int total, int number) {
    List<Integer> list = new ArrayList<Integer>(total);
    for(int i=1;i<=total;i++) {
      list.add(i);
    }
    int j = 1;
    int l = 1;
    while(total > 0)
{
     int k = list.size();
     if(k==1)
     {
     System.out.println(list.get(0));
     break;
     }else{
     if(l <=k )
     {
     if(j == number)
         {
     Integer in = (Integer)list.get(l-1);
     System.out.println(in);
     list.remove(in);
     j = 1;
     total--;
         }else{
         l++;
         j++;
         }
     }else{
     l = 1;
     if(j == number)
         {
     Integer in = (Integer)list.get(l-1);
     System.out.println(in);
     list.remove(in);
     j = 1;
     total--;
         }else{
         l++;
         j++;
         }
     }
     }
}
  }  /**
   * @param args
   */
  public static void main(String[] args) {
    Test1.to(10, 5);
  }
}

Answer 6

嗬嗬，约瑟夫环问题。贴个能算最后一个人编号的程序，很短。public class  Test{
 public static void josephus(int N,int M){
  int s=0;
  for(int i=2;i<=N;i++){
   int k=M%i;
   s=(s+k)%i;
  }
  System.out.println(s);
 }
 public static void main(String[] args){
     josephus(5,2);
 }
}打印出圈序列的话，应该会变复杂一点，不过也可以在O(N)的时间内实现。

Answer 7

这个题目用一个数组就足够了。
被轮到的就置数为其相反数。要善用数据本身结构。这样做的效果是最快的，特别是注意代码中使用的技巧。 public static void main(String[] args) { int a[] = { 1, 2, 3, 4, 5, 6 };
int i = 0;
int c = 0;
int M = 2;
int count = 0;
boolean has = true;
while (has) { i++;
i %= a.length;
int ad = i - 1 < 0 ? a.length - 1 : i - 1; 
if (a[ad]  < 0) {
continue;
}
c++;
c %= M;
if (c == 0) {
has = ++count < a.length;
a[ad] = -a[ad];
System.out.println(-a[ad]);
} } }

Answer 8

//算法思想：m为人数，n为步长，所有人出列要进行m轮，每轮过后已经出列的人，不在新的一轮的判断之内（过滤掉）public class CycleMan {

public static void main(String[] args) {
play(10000, 137);
}
//用于过滤
private static boolean same(int[] p,int m,int n){
for(int i=0;i<m;i++){
if(p[i]==n){
return true;
} 
}  
return false;
}  
//算法执行体
public static void play(int playerNum, int step){
int[] p=new int[playerNum];
int counter = 1;//走过步数：counter
while(true){

if(counter > playerNum*step){//退出while，根据走过的步数
break;
}  
for(int i=1;i<=playerNum;i++){
                //过滤
while(true){
if(same(p,playerNum,i)==false) 
break;
else 
i=i+1; 
}
if(i > playerNum)break;//退出for
//根据走过的步数和步长判断此人是否应该出列，若是则输出此人，并将其存入出列队列中，若不是继续走下去
if(counter%step==0){//counter代表已经走过的步数
System.out.print(i+"  ");
p[counter/step-1]=i;
}
counter+=1;
}
}
System.out.println();
}    
}

Answer 9

19楼说的对，有数学解法的
循环就可以了，具体BAIDU

Answer 10

#include <stdio.h>#define N 10
#define M 5int
main(void)
{
    int people[N] = {0};    int i = 0;    //give the number for people from 1 to N
    for (; i<N; i++)
    {
        people[i] = i+1;
    }    int tmp = 1;
    i = 0;
    int num = 0;    while (num < N)
    {
        if (tmp == M)
        {
            printf("%d\n", people[i]);
            tmp = 0;
            people[i] = 0;
            num ++;
        }
        i++;
        if (i == N) i = 0;
        if (people[i] != 0)tmp ++;
    }    return 0;
}
输入n=10, m=5. 输出为：
5
10
6
2
9
8
1
4
7
3

Answer 11

呵呵using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ysfh
{
    class Program
    {
        public const int m = 23;
        static void Main(string[] args)
        {
            int r = m,a=1,s=1;
            List<int> poped=new List<int>();            List<int> n = new List<int>{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            while (n.Count > 1)
            {
                for (int j = s; j <= n.Count;j++ )
                {
                    if (a != r)
                    {
                        s = 1; 
                        a++; 
                    }
                    else
                    {
                        poped.Add(n[j-1]);
                        n.Remove(n[j-1]);
                        s = j;
                        a = 1;
                        break;
                    }
                }
            }            Console.WriteLine("出圈序列");
            foreach (int ss in poped)
            {
                Console.WriteLine(ss);
            }
            Console.WriteLine("最後一個人");
            foreach (int w in n)
            {
                Console.WriteLine(w);
            }
            Console.ReadLine();
        }
    }
}

Answer 12

循环双向链表解决如下：
class TPerson {
    String no;    TPerson pre;    TPerson next;    public TPerson(String no, TPerson pre, TPerson next) {
        this.no = no;
        this.pre = pre;
        this.next = next;
    }    public TPerson(String no) {
        this(no, null, null);
    }}
class TPersonList {
    TPerson first;    TPerson last;    public synchronized void insertAtFront(String no) {
        if (isEmpty()) {
            first = last = new TPerson(no);
        }
        else {
            TPerson addItem = new TPerson(no, last, first);
            first.pre = addItem;
            last.next = addItem;
            first = addItem;
        }
    }    public synchronized void insertAtBack(String no) {
        if (isEmpty()) {
            first = last = new TPerson(no);
        }
        else {
            TPerson addItem = new TPerson(no, last, first);
            first.pre = addItem;
            last.next = addItem;
            last = addItem;
        }
    }    public synchronized String removeAtFront() throws RemoveException {
        if (isEmpty()) {
            throw new RemoveException("the list is empty!");
        }        String no = first.no;
        if (first == last) {
            first = last = null;
        }
        else {
            last.next = first.next;
            first = first.next;
        }        return no;
    }    public synchronized String removeAtBack() throws RemoveException {
        if (isEmpty()) {
            throw new RemoveException("the list is empty!");
        }        String no = last.no;
        if (first == last) {
            first = last = null;
        }
        else {
            first.pre = last.pre;
            last = last.pre;
        }        return no;
    }    public boolean isEmpty() {
        return first == null;
    }    public String toString() {
        if (isEmpty()) {
            return "a empty list!";
        }        String result = first.no;
        TPerson curr = first.next;
        if (curr != null) {
            while (curr != first) {
                result += ", " + curr.no;
                curr = curr.next;
            }
        }        return result;
    }
}public class LoopCounter {    public void count(int n, int m) {
        TPersonList list = new TPersonList();
        for (int i = 1; i <= n; i++ ) {
            list.insertAtBack("" + i);
        }        if (m < 1) {
            throw new RuntimeException("invalid argument!");
        }
        else if (m == 1) {
            System.out.println(list);
        }
        else {
            TPerson curr = list.first;
            int count = 1;
            String no = null;
            int quitNo = 0;
            while (list.first != list.last) {
                if (count == m) {
                    count = 1;
                    quitNo++ ;
                    no = curr.no;
                    System.out.println("no: " + no);
                    System.out.println("quitNo: " + quitNo);
                    list.first = curr.next;
                    list.first.pre = curr.pre;
                    list.last = curr.pre;
                    list.last.next = list.first;
                    curr = list.first;
                }
                curr = curr.next;
                count++ ;
            }            quitNo++ ;
            System.out.println("the last person no: " + list.first.no + ", quitNo: " + quitNo);
        }
    }    public static void main(String[] args) throws RemoveException {
        LoopCounter counter = new LoopCounter();
        counter.count(3, 5);
    }
}