求解决( Java )

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2408 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

编号

报数

依次

贴有

34 条回复 • 2018-04-20 09:23:00 +08:00

stevenbipt

2018-04-19 10:25:11 +08:00 via Android

怎么感觉和约瑟夫环差不多

sunshinel

2018-04-19 10:27:07 +08:00 via Android

是差不多，但好像不一样

neosfung

2018-04-19 10:27:14 +08:00 via iPhone

用模拟的方法也搞不定么

zjp

2018-04-19 10:28:36 +08:00 via Android

算法课程作业吗
https://zh.wikipedia.org/zh-hans/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98

sunshinel

2018-04-19 10:29:40 +08:00 via Android

我是初学者，解决不了这个问题，求大神赐教。😭

sunshinel

2018-04-19 10:30:47 +08:00 via Android

@zjp 一个 JAVA 作业

yag

2018-04-19 10:32:29 +08:00

就是约瑟芬杀人游戏，我写过一篇这个的博客，但是找不到了，很烦

nita22

2018-04-19 10:33:52 +08:00

不考虑复杂度的话，只考虑完成问题，还是不难的吧

yag

2018-04-19 10:34:16 +08:00

https://www.cnblogs.com/yangshuo-w/p/6928637.html 找到了，这是在我贼鸡儿中二的时候写的。自己看着都尬

Luckyray

2018-04-19 10:35:13 +08:00

先写个循环链表，然后 remove remove remove...空间 O(n)时间额...不太会算，也是 O(n)?

ech0x

2018-04-19 10:35:54 +08:00 via iPhone

刚刚做完这个作业
这个很简单啊。20 个元素的数组都设置 1，每过两个 1，第三个 1 设置成 0，弄个计数器记录出局的人数，然后不断循环这个数组就好了，直到计数器为 19，然后扫描一遍数组，剩下的 1 就是胜利的人。

huiyifyj

2018-04-19 10:36:59 +08:00

上学期数据结构有看到，用的就是#10 说的循环链表。

skyFuture

2018-04-19 10:37:23 +08:00

for 循环呗，顺便有个记录剩下多少人的值就行

OpenJerry

2018-04-19 10:42:33 +08:00 via Android

循环链表，我以前也写过这道题

binbinyouliiii

2018-04-19 10:43:49 +08:00

LinkList

SorcererXW

2018-04-19 11:03:20 +08:00

直接用一维数组模拟一下循环即可

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

2018-04-19 12:01:09 +08:00

学习了，处理 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

2018-04-19 13:20:52 +08:00

算法经典入门题。
一般称猴子选大王问题，百度可以找到很多种解法。
如下贴出：
https://paste.ubuntu.com/p/RGvbvSPtxd/（ Java 实现）

ieiayaobb

2018-04-19 13:27:43 +08:00

约瑟夫环，考查的是循环链表的实现

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

2018-04-19 13:54:45 +08:00

@xiangyuecn 22 轮会杀掉 22 个人。（ 1 万个？）

georgetso

2018-04-19 14:31:41 +08:00

https://baike.baidu.com/item/约瑟夫问题

lyusantu

2018-04-19 15:21:18 +08:00

```
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

2018-04-19 15:23:08 +08:00

从 1 开始递增报数，最大数为 20，最后剩下的数结果也是 20

xiangyuecn

2018-04-19 15:40:53 +08:00

@picasso2501 #21 我那设定的 n=10000，需要循环报数 22 轮。如果 n=20 跟楼主一样的初始条件的话，是 7 轮，结果是 20

Windsooon

2018-04-19 16:14:00 +08:00

别想太多，循环计算一下就好（ python3 ）

class solution:
def josephus(self, n, k):
last = 0
for i in range(1, n+1):
last = (last+k) % i
return last

Andiry

2018-04-19 16:18:39 +08:00

一个摆明了作业不会做想偷懒的人，你们上来直接贴答案，这样好吗？

sunjiayao

2018-04-19 16:21:30 +08:00

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

2018-04-19 16:21:45 +08:00

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

2018-04-19 16:21:46 +08:00

这题我在一家公司面试做过，我当时的解决思路是将 1-n 放到一个 list 里面，建一个 while 循环，再建一个 for 循环，每当 i 除以 3 的余数为零的时候，list 里面删除这个 index 的元素，直到剩最后一个元素

sunshinel

2018-04-19 17:07:32 +08:00 via Android

@Andiry 实在是能力有限，初学 JAVA。也想了做不出来呀！

lyusantu

2018-04-19 17:17:17 +08:00

@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

2018-04-20 08:54:09 +08:00

@lyusantu 为什么留下来的是始终是最后一个你的代码

lyusantu

2018-04-20 09:23:00 +08:00

@jinhan13789991 因为其他数字都被淘汰掉了