求解决( Java )

2018-04-19 10:13:52 +08:00
 sunshinel
20 个人围成一圈,每个人背上都贴有一个编号,依次为 1、2、...、20,现在从编号为 1 的人开始,从 1 依次递增报数,凡是报的数是 3 的倍数人离开圈子,剩下的人继续往下报数,问最后留下的那个人的编号是多少?请编写程序解决此问题。
5699 次点击
所在节点    Java
34 条回复
picasso2501
2018-04-19 13:54:45 +08:00
@xiangyuecn 22 轮会杀掉 22 个人。( 1 万个?)
georgetso
2018-04-19 14:31:41 +08:00
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
@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 因为其他数字都被淘汰掉了

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

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

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

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

© 2021 V2EX