一道和循环链表相关的算法题

有100人按编号从1到100围成一个圈,从第一个人开始报数,报道数字5的时候把报数字3的人踢出去,然后从报数字5的下一个人继续报数字1,在这个圈子里一直报下去,最后报到剩下一个人结束报数。那么最后剩下的那个人的编号是多少?

2个回答

约瑟夫环问题,网上搜一下,会有很多代码的

qq_36562999
Martin-wwh 嗯,谢谢大佬提示
大约 2 年之前 回复

用Java实现的代码,仅供参考

 LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < 100; i++) {//初始化100个人
            list.add(i+1);
        }
        int count = 1;//报数1-5,从1开始报
        int curIndex = 0;//当前报数人下标,从第一个人开始报数
        int removeIndex = 0;//要移除的报数人下标
        while(list.size() > 1){//剩下最后一个人的时候退出
            if(count == 3)//报到3时,记录当前报数人下标,用于移除
                removeIndex = curIndex;
            if(count == 5){//报到5时
                count = 0;//重新报数
                list.remove(removeIndex);//移除报数3的人
                if(removeIndex <= curIndex)//移除的人在报数5的前面时,报数5的下标往前移一位
                    curIndex--;
            }
            count++;//下一个要报的数
            curIndex++;//下一位报数人下标
            if(curIndex >= list.size()){//最后一位报数完,回到第一位继续报数
                curIndex = 0;
            }
        }
        System.out.println(list.element());//输出剩下的最后一位的编号
qq_36562999
Martin-wwh 谢谢你的代码,我用循环链表也实现出来了
大约 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问