有n个人围成一圈,顺序排号。从第一个人开始报数...

请输入昵称023 发布于 2013/08/26 08:57
阅读 11K+
收藏 1

有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。

最后把思路和代码都发一下,小妹在此谢过了。

加载中
0
inuxor
inuxor

这是经典问题了,俗名猴子选大王,学名约瑟夫环。

搜一下吧,遍网都是

请输入昵称023
请输入昵称023
好专业啊。
0
dreamers
dreamers
我见过最简单的理解就是:设置一个变量(即凡是数到3的人),就将该数组的位置的值设置为-1(或其他标志值),即此循环,即可得出最后一个人的位置了。
0
瓦兰吉卫队
瓦兰吉卫队
只发思路哦--用队列,数到3的出列,其余的出列并入列;用数组,数到3的删除,后面的前移即可。
瓦兰吉卫队
瓦兰吉卫队
回复 @苏婉婷 : 用队列的话,可以理解成所有人排成一条长队,最前面的人报数,报到1,2的就跑到队尾去,报到3的就离开,如此循环
请输入昵称023
请输入昵称023
能说的直白点儿吗?
0
0
情天大圣
情天大圣

代码:

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Main {

    public static void main(String[] args) {
        final int n = 10;
        final int flag = 3;

        List<Integer> mans = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            mans.add(i + 1);
        }
        System.out.println("初始化编号为" + mans + "的" + mans.size() + "个人围成一圈");

        ListIterator<Integer> iter = null;
        int k = 1;
        do {
            iter = mans.listIterator();
            while (iter.hasNext()) {
                int i = iter.next();
                if (k++ % flag == 0) {
                    System.out.println("编号" + i + "的人退出圈子");
                    iter.remove();
                    k = 1;
                }
            }
        } while (mans.size() > 1);

        System.out.println("剩下编号为" + mans + "的" + mans.size() + "个人");
    }

}

运行结果:

情天大圣
情天大圣
回复 @苏婉婷 : 好吧,当我没发过
请输入昵称023
请输入昵称023
运行不了。你这个好像不是吧。
情天大圣
情天大圣
回复 @liangtee : 您别矫情了,来点实际的!
liangtee
liangtee
容我矫情的说一句:这种题目用list就失去意义了
0
醪糟儿蛋
醪糟儿蛋

c 可以自己写链表实现,算法楼上都有人说了

c++ 可以用 std的 list 实现,算法楼上已给出

java 楼上已经楼上已贴代码了

sxgkwei
sxgkwei
回复 @小耶果 : 。。。。百度百科还真有c代码啊。。服了。
小耶果
小耶果
回复 @醪糟儿蛋 : 这你都没看明白,人家明显问的都是C的问题,而且野鬼似乎也很来劲.最近又在写书,这种问题都是C书中应该给出的,可以说野鬼回答这种问题都是手到擒来,都是现成的.这么看都比我回来要来得更合适更权威嘛.
醪糟儿蛋
醪糟儿蛋
回复 @小耶果 : 我记得此故事上一节是 @苏婉婷 请你做私人辅导,你貌似没有拒绝。本节开头你没出现,天气这么热,太阳这么大,色狼这么多,你也忍心让人家小姑娘家在门外等你半天,, @中山野鬼 都看不下去了
小耶果
小耶果
回复 @中山野鬼 : 对于这种标准国际问题,百度百科都给出代码了,还有什么好回答的呢? http://baike.baidu.com/view/717633.htm
中山野鬼
中山野鬼
回复 @苏婉婷 : 可以@小耶果 哈。。。
下一页
0
雨翔河
雨翔河
很简单,循环链表就能搞定,大一就搞定了这题目。遇到了3就断开该结点释放它,前后连接上去就ok了。
0
王瑞平
王瑞平
循环链表
0
狄仁傑
狄仁傑

引用来自“php_by”的答案

不过你tm真是小妹么
不过你tm的真是小妹么+1
请输入昵称023
请输入昵称023
不是。我是大姐。
0
我不说话
我不说话

给你一个我10年的思路:初始化一个有N个元素的数组,然后循环遍历赋值,1、2……m,赋值之前,判断是否为m,如果为m,继续判断下一个元素,这里赋值,也是循环赋值的,不能漏掉。如此这般,直到n-1个元素都是m,剩下的那个不是m的元素的下标,就是你要找的!看明白的+1吧!

算法,要考虑时间复杂度和空间复杂度的!

网上有最简单的算法,4、5行代码搞定,什么数组啊,集合啊,统统不需要,只需要计算。

返回顶部
顶部