求解决( Java )

2018-04-19 10:13:52 +08:00
 sunshinel
20 个人围成一圈,每个人背上都贴有一个编号,依次为 1、2、...、20,现在从编号为 1 的人开始,从 1 依次递增报数,凡是报的数是 3 的倍数人离开圈子,剩下的人继续往下报数,问最后留下的那个人的编号是多少?请编写程序解决此问题。
5699 次点击
所在节点    Java
34 条回复
stevenbipt
2018-04-19 10:25:11 +08:00
怎么感觉和约瑟夫环差不多
sunshinel
2018-04-19 10:27:07 +08:00
是差不多,但好像不一样
neosfung
2018-04-19 10:27:14 +08:00
用模拟的方法也搞不定么
zjp
2018-04-19 10:28:36 +08:00
sunshinel
2018-04-19 10:29:40 +08:00
我是初学者,解决不了这个问题,求大神赐教。😭
sunshinel
2018-04-19 10:30:47 +08:00
@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
刚刚做完这个作业
这个很简单啊。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
循环链表,我以前也写过这道题
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);
}
}

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/448050

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX