V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sunshinel
V2EX  ›  Java

求解决( Java )

  •  
  •   sunshinel · 2018-04-19 10:13:52 +08:00 via Android · 5457 次点击
    这是一个创建于 2170 天前的主题,其中的信息可能已经有所发展或是发生改变。
    20 个人围成一圈,每个人背上都贴有一个编号,依次为 1、2、...、20,现在从编号为 1 的人开始,从 1 依次递增报数,凡是报的数是 3 的倍数人离开圈子,剩下的人继续往下报数,问最后留下的那个人的编号是多少?请编写程序解决此问题。
    34 条回复    2018-04-20 09:23:00 +08:00
    stevenbipt
        1
    stevenbipt  
       2018-04-19 10:25:11 +08:00 via Android
    怎么感觉和约瑟夫环差不多
    sunshinel
        2
    sunshinel  
    OP
       2018-04-19 10:27:07 +08:00 via Android
    是差不多,但好像不一样
    neosfung
        3
    neosfung  
       2018-04-19 10:27:14 +08:00 via iPhone
    用模拟的方法也搞不定么
    zjp
        4
    zjp  
       2018-04-19 10:28:36 +08:00 via Android
    sunshinel
        5
    sunshinel  
    OP
       2018-04-19 10:29:40 +08:00 via Android
    我是初学者,解决不了这个问题,求大神赐教。😭
    sunshinel
        6
    sunshinel  
    OP
       2018-04-19 10:30:47 +08:00 via Android
    @zjp 一个 JAVA 作业
    yag
        7
    yag  
       2018-04-19 10:32:29 +08:00
    就是约瑟芬杀人游戏, 我写过一篇这个的博客,但是找不到了,很烦
    nita22
        8
    nita22  
       2018-04-19 10:33:52 +08:00
    不考虑复杂度的话,只考虑完成问题,还是不难的吧
    yag
        9
    yag  
       2018-04-19 10:34:16 +08:00   ❤️ 1
    https://www.cnblogs.com/yangshuo-w/p/6928637.html 找到了,这是在我贼鸡儿中二的时候写的。自己看着都尬
    Luckyray
        10
    Luckyray  
       2018-04-19 10:35:13 +08:00
    先写个循环链表,然后 remove remove remove...空间 O(n)时间额...不太会算,也是 O(n)?
    ech0x
        11
    ech0x  
       2018-04-19 10:35:54 +08:00 via iPhone   ❤️ 1
    刚刚做完这个作业
    这个很简单啊。20 个元素的数组都设置 1,每过两个 1,第三个 1 设置成 0,弄个计数器记录出局的人数,然后不断循环这个数组就好了,直到计数器为 19,然后扫描一遍数组,剩下的 1 就是胜利的人。
    huiyifyj
        12
    huiyifyj  
       2018-04-19 10:36:59 +08:00
    上学期数据结构有看到,用的就是#10 说的循环链表。
    skyFuture
        13
    skyFuture  
       2018-04-19 10:37:23 +08:00
    for 循环呗,顺便有个记录剩下多少人的值就行
    OpenJerry
        14
    OpenJerry  
       2018-04-19 10:42:33 +08:00 via Android
    循环链表,我以前也写过这道题
    binbinyouliiii
        15
    binbinyouliiii  
       2018-04-19 10:43:49 +08:00
    LinkList
    SorcererXW
        16
    SorcererXW  
       2018-04-19 11:03:20 +08:00   ❤️ 1
    直接用一维数组模拟一下循环即可

    public static int solve(int n, int interval) {
    boolean killed[] = new boolean[n];
    int next = interval, cnt = 0;
    for (int i = 0; i < n; i = (i == n - 1 ? 0 : i + 1)) {
    if (killed[i]) continue;
    if (cnt == n - 1) return i + 1;
    next--;
    if (next == 0) {
    killed[i] = true;
    next = interval;
    cnt++;
    }
    }
    return 0;
    }
    xiangyuecn
        17
    xiangyuecn  
       2018-04-19 12:01:09 +08:00   ❤️ 1
    学习了,处理 1 万个要进行 22 轮报数,处理 10 万个要 28 轮报数,你问我怎么知道的

    看 Java script(滑稽 代码:
    ```
    console.time(1);

    var n=10000;
    var arr=[];
    for(var i=1;i<=n;i++){
    arr.push("第"+i+"个家伙");
    };

    var num=0,loop=0;
    while(arr.length>1){
    loop++;
    console.log("***"+loop+"轮***");
    for(var i=0;i<arr.length;i++){
    num++;
    var debugMsg=arr[i]+"报"+num;
    if(num%3==0){
    debugMsg+="踢掉";
    arr.splice(i,1);
    i--;
    num=0;
    }
    //console.log(debugMsg);
    }
    if(arr.length<2){
    console.log("结果闪亮登场:"+arr[0]);
    break;
    };
    }

    console.timeEnd(1);
    ```

    js 处理大点的数组比较吃力,改 java 试试

    easylee
        18
    easylee  
       2018-04-19 13:20:52 +08:00
    算法经典入门题。
    一般称猴子选大王问题,百度可以找到很多种解法。
    如下贴出:
    https://paste.ubuntu.com/p/RGvbvSPtxd/( Java 实现)
    ieiayaobb
        19
    ieiayaobb  
       2018-04-19 13:27:43 +08:00
    约瑟夫环,考查的是循环链表的实现
    picasso2501
        20
    picasso2501  
       2018-04-19 13:52:50 +08:00
    你们这些愚蠢的人类,根本不知道 PHP 的威力
    <?php

    // 20 个人围成一圈,每个人背上都贴有一个编号,依次为 1、2、...、20,现在从编号为 1 的人开始,从 1 依次递增报数,凡是报的数是 3 的倍数人离开圈子,剩下的人继续往下报数,问最后留下的那个人的编号是多少?请编写程序解决此问题。

    $s = new Solv(20);
    for ($i=0; $s->count()!=1; $i++) {
    if ((($i+1)%3)==0) {
    $s->remove($i);
    }
    }
    echo $s->get(0),"\n";

    class Solv
    {
    public $arr = [];
    public function __construct($len) {
    for ($i=0; $i < $len; $i++) {
    $this->arr[] = $i+1;
    }
    }

    public function get($index) {
    return $this->arr[$index%count($this->arr)];
    }
    public function remove($index) {
    print_r($this->arr);
    $index = $index%count($this->arr);
    echo "remove $index {$this->arr[$index]}\n";
    array_splice($this->arr, $index, 1);
    print_r($this->arr);
    }
    public function count() {
    return count($this->arr);
    }
    }
    picasso2501
        21
    picasso2501  
       2018-04-19 13:54:45 +08:00
    @xiangyuecn 22 轮会杀掉 22 个人。( 1 万个?)
    georgetso
        22
    georgetso  
       2018-04-19 14:31:41 +08:00
    lyusantu
        23
    lyusantu  
       2018-04-19 15:21:18 +08:00   ❤️ 1
    ```
    import java.util.ArrayList;
    import java.util.List;

    public class Test {

    public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 20; i++) {
    list.add((i + 1));
    }
    numberOff(list);
    System.out.println(list.get(0));
    }

    public static List<Integer> numberOff(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
    list.set(i, list.get(i) + 1);
    if (list.get(i) % 3 == 0) {
    list.remove(i);
    if (list.size() == 1)
    break;
    else
    --i;
    }
    }
    return list.size() > 1 ? numberOff(list) : list;
    }
    }

    ```
    lyusantu
        24
    lyusantu  
       2018-04-19 15:23:08 +08:00
    从 1 开始递增报数,最大数为 20,最后剩下的数结果也是 20
    xiangyuecn
        25
    xiangyuecn  
       2018-04-19 15:40:53 +08:00
    @picasso2501 #21 我那设定的 n=10000,需要循环报数 22 轮。如果 n=20 跟楼主一样的初始条件的话,是 7 轮,结果是 20
    Windsooon
        26
    Windsooon  
       2018-04-19 16:14:00 +08:00   ❤️ 1
    别想太多,循环计算一下就好( python3 )

    class solution:
    def josephus(self, n, k):
    last = 0
    for i in range(1, n+1):
    last = (last+k) % i
    return last
    Andiry
        27
    Andiry  
       2018-04-19 16:18:39 +08:00
    一个摆明了作业不会做想偷懒的人,你们上来直接贴答案,这样好吗?
    sunjiayao
        28
    sunjiayao  
       2018-04-19 16:21:30 +08:00   ❤️ 1
    package main

    import (
    "strconv"
    )

    type People struct {
    index int64
    next *People
    parent *People
    }

    func initPeople(first *People,people *People){
    nextPeople := new(People)
    nextPeople.index = people.index+1
    nextPeople.parent = people
    people.next = nextPeople

    if nextPeople.index==20{
    nextPeople.next = first
    first.parent = nextPeople
    return
    }
    initPeople(first,nextPeople)
    }


    func main() {

    people := new(People)
    people.index = 1
    initPeople(people,people)
    var count int64 = 0
    for people.next != people{
    count ++
    if count % 3 ==0{
    people.next.parent = people.parent
    people.parent.next = people.next
    }
    people = people.next
    }
    println("finally number :"+strconv.FormatInt(people.index,10)+"; for count is :"+strconv.FormatInt(count,10))

    }



    //没用 java,不过思路是一样的。结果是 20 吗?
    feeeeeef
        29
    feeeeeef  
       2018-04-19 16:21:45 +08:00   ❤️ 1
    Let's begin!
    I am 3,killed by 3
    I am 6,killed by 6
    I am 9,killed by 9
    I am 12,killed by 12
    I am 15,killed by 15
    I am 18,killed by 18
    The 1 round end.
    I am 1,killed by 21
    I am 5,killed by 24
    I am 10,killed by 27
    I am 14,killed by 30
    I am 19,killed by 33
    The 2 round end.
    I am 4,killed by 36
    I am 11,killed by 39
    I am 17,killed by 42
    The 3 round end.
    I am 7,killed by 45
    I am 16,killed by 48
    The 4 round end.
    I am 8,killed by 51
    The 5 round end.
    I am 2,killed by 54
    The 6 round end.
    I am 13,killed by 57
    The 7 round end.
    Game over!
    I am 20,winner!
    58
    unforgiven
        30
    unforgiven  
       2018-04-19 16:21:46 +08:00
    这题我在一家公司面试做过,我当时的解决思路是将 1-n 放到一个 list 里面,建一个 while 循环,再建一个 for 循环,每当 i 除以 3 的余数为零的时候,list 里面删除这个 index 的元素,直到剩最后一个元素
    sunshinel
        31
    sunshinel  
    OP
       2018-04-19 17:07:32 +08:00 via Android
    @Andiry 实在是能力有限,初学 JAVA。也想了做不出来呀!
    lyusantu
        32
    lyusantu  
       2018-04-19 17:17:17 +08:00   ❤️ 1
    @sunshinel 上一个回复的解答是不对的,问题是“问最后留下的那个人的编号”而非最后留下的数字,所以更正后的代码 如下:

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

    public class Test {

    public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 20; i++) {
    list.add((i + 1));
    }
    numberOff(list);
    System.out.println("最后留下的人的编号为:" + numberOff(list));
    }

    public static Integer numberOff(List<Integer> list) {
    int start = 0;
    while (list.size() > 1) {
    for(int i = 0; i < list.size(); i++){
    if (++start % 3 == 0)
    list.remove(i);
    if(list.size() == 1)
    break;
    --i;
    }
    }
    return list.get(0);
    }
    }
    jinhan13789991
        33
    jinhan13789991  
       2018-04-20 08:54:09 +08:00
    @lyusantu 为什么 留下来的是始终是最后一个 你的代码
    lyusantu
        34
    lyusantu  
       2018-04-20 09:23:00 +08:00
    @jinhan13789991 因为其他数字都被淘汰掉了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1964 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:22 · PVG 00:22 · LAX 09:22 · JFK 12:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.