约瑟夫环,一个简单的acm题目
问题如下：
有一只狡猾的老鼠，在一个环形的田埂上挖了n个老鼠洞，这些洞也是连接为一个环状，我们要用泥土填满这些鼠洞，老鼠从第0号洞开始出现(第0号洞不填)，然后依次按每间隔m个洞出现一次。我们要跟在老鼠后面，当老鼠出现后填补上刚刚出现的洞。我们需要计算出老鼠最后出现那个洞（即剩下最后一个洞没有被我们填上时，这个洞的序号）。
Input
输入的第一行为了两个整数n、m，n表示一共有n个老鼠洞，m表示老鼠每隔m个洞出现。
Output
输出老鼠最后出现的那个洞的序号。
Sample Input
5 2
我的思路是建立一个数组，给他赋初值，从0开是到n；将没有填补的洞重新建立新的数组，但是新数组是链接到原来数组的。直到最后只剩下一个数为止！输出这个数就是想要的最后的那个洞，例如：
第一个原始数组a[0]=0 a[1]=1 a[2]=2 a[3]=3 a[4]=4
建立的新数组a[5]=0 a[6]=1 a[7]=3
新数组 a[8]=0 a[9]=3
新数组 a[10]=3
最后结果为3
[code=C/C++][/code]#include "stdio.h"
int main()
{
int m,n,cot=0,mind=0,i,j,a[10000];
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
a[i]=i;
for(i=0;;i++)
{

for(j=mind;j<n;j++)
{
if(j%m!=0||j==0)
{
cot++;
a[n-1+cot]=a[j];
}
}
if(cot==1)
{
printf("%d\n",a[j]);
break;
}
mind=n;
n=n+cot;
cot=0;
}
return 0;
}
各位大神勿喷！小弟暂时自学还没有学过算法课，连这个题是约瑟夫环我都不知道，是后来Google才知道的。但是我讲这个代码提交过后！答案错误！我下载了其他人的代码
[code=C/C++][/code]#include<stdio.h>
int main()
{
int i,n,m;
scanf("%d%d",&n,&m);
int r=0;
for(i=2;i<=n;i++)
r=(r+m)%i;
printf("%d\n",r+1);
return 0;
}
我用这两个代码比较，答案是一样的啊，输入输出都一样！为什么我的就是错的！求大神们接答，不胜感激啊！

[解决办法]
其实你的想法还是能得到正确的值的。但是从空间复杂度和事件复杂度来说不够好。而且你用数组来存放数据，那么你将面临的是数组空间够用吗？？

[解决办法]
这是个数学问题，跟约瑟夫环没啥关系吧，而且题目并没有说m、n值的上限，你那样肯定会出问题
[解决办法]
同一个问题，从不同的角度思考有不同的解。约瑟夫环可以看一下百度百科http://baike.baidu.com/view/717633.htm
[解决办法]
才知道有这种解法，受教了
[解决办法]

C/C++ code

//假设有n个人团团围做，从第1个人开始数数，数到第m个人时候，第m个人出列，//然后继续从1开始数数，数到第m个人退出#include <stdio.h>#include <conio.h>int i,k,t;int n,m;static char f[1001];//0该座位未出圈,1该座位已出圈void main() {    while (1) {        printf("Input n m(1000>=n>=m>=1):");        fflush(stdout);        rewind(stdin);        if (2==scanf("%d%d",&n,&m)) {            if (1000>=n && n>=m && m>=1) break;        }    }    t=0;//已出圈总人数    i=1;//座位编号    k=1;//当前要数的数    while (1) {        if (0==f[i]) {            if (m==k) {                t++;                f[i]=1;                printf("%3d ",i);                if (0==t%10) printf("\n");                if (t>=n) break;            }            k++;if (k>m) k=1;        }        i++;if (i>n) i=1;    }    cprintf("Press any key ...");    getch();}
[解决办法]
楼主，你的算法就是一个搜索队列，如果搜索太大就会溢出，改成循环队列试试。
[解决办法]
你问的是ＪＡＶＡ还是Ｃ啊，给你个JAVA的参考一下：package com.tim4lover.test.service;  
    
import java.util.ArrayList;  
import java.util.List;  
    
class Node {  
   private int index;  
   private Node next;  
   public Node(int index) {  
       this.index = index;  
   }  
   public int getIndex() {  
       return index;  
   }  
   public void setIndex(int index) {  
       this.index = index;   
 
   }  
   public Node getNext() {  
       return next;  
   }  
   public void setNext(Node next) {  
       this.next = next;  
   }  
   @Override 
   public String toString() {  
       return String.valueOf(index);  
   }  
}  
    
public class Josephus {  
   private List<Node> nodes = new ArrayList<Node>();  
   public Josephus(int n) {  
       for(int i=1; i<=n; i++) {  
           Node node = new Node(i);  
           push(node);  
       }  
   }  
   public void push(Node node) {  
       if(nodes.size()== 0) {  
           node.setNext(node);  
           nodes.add(node);  
       }else {  
           nodes.get(nodes.size()-1).setNext(node);  
           node.setNext(nodes.get(0));  
           nodes.add(node);  
       }  
   }  
   public void pull(Node node) {  
       if(nodes.size()>1) {  
           int pre = nodes.indexOf(node);  
           if(pre==0) {  
               pre = nodes.size();  
           }  
           Node node_pre = nodes.get(pre-1);  
           node_pre.setNext(node.getNext());  
           nodes.remove(node);  
       }else {  
           nodes.remove(node);  
       }  
       System.out.println(nodes);  
       System.out.println(node);  
   }  
   public List<Integer> output(int m) {  
       List<Integer> result = new ArrayList<Integer>();  
       Node node = null;  
       if(nodes.size()!=0) {  
           node = nodes.get(0);  
       }  
       while(nodes.size()!= 0) {  
           for(int i=0; i<m; i++) {  
               node = node.getNext();  
           }  
           pull(node);  
           result.add(node.getIndex());  
       }  
       return result;  
   }  
   public static void main(String[] args) {  
       Josephus jos = new Josephus(10);  
       List<Integer> result = jos.output(2);  
       System.out.println(result);  
   }