黑马程序员技术交流社区

标题: 有100个人围成一个圈，从1开始报数，报到14的这个人就要... [打印本页]

作者: ye361571404 时间: 2014-10-9 14:59
标题: 有100个人围成一个圈，从1开始报数，报到14的这个人就要...
有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？这道题你们的结果是多少？代码我写完了，我的结果是剩下的是100人中的第75个人。

作者: 水竹 时间: 2014-10-9 15:07
我和好多人的答案都是92

作者: 杨佳名 时间: 2014-10-9 16:06
可以贴出代码让潜伏的大神们修改一下

作者: ye361571404 时间: 2014-10-9 17:09

杨佳名发表于 2014-10-9 16:06
可以贴出代码让潜伏的大神们修改一下

这道题我是看完韩顺平的这个视频做出来的：循序渐进学 java 从入门到精通第11讲-约瑟夫问题.avi

package com.itheima;
/**
* 第十题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
* 修改时间：2014-10-9 上午01:23:57
*/
public class Test10 {
public static void main(String[] args) {
CycLink cycLink = new CycLink(); //1.定义链表对象
cycLink.setLen(100); //2.设置总人数
cycLink.setK(0); //3.设置从哪个人开始数
cycLink.setM(14); //4.设置数到第14的这个人退出
cycLink.createLine(); //5.创建链表
// cycLink.show(); //6.打印链表
cycLink.play(); //7.找出剩下的最后一个人是谁
}
}
/**
* 定义Person类
* 修改时间：2014-10-9 上午04:15:03
*/
class Person{
public int no; //1.人的编号
public Person nextPerson = null; //2.下一个人
public Person previousPerson = null; //3.上一个人
//构造函数
public Person(int no){
this.no = no;
}
}
/**
* 环形链表
* 修改时间：2014-10-9 上午03:19:43
*/
class CycLink{
Person firstPerson = null; //1.先定义一个指向链表第一个人的引用
Person temp = null;
int len = 0; //2.表示有几个人
int k = 0; //3.从第几个人开始数
int m = 0; //4.设置数第m下的人退出
//设置数第m下的人退出
public void setM(int m){
this.m = m;
}
//设置从第几个人开始数
public void setK(int k){
this.k = k;
}
//设置链表大小
public void setLen(int len){
this.len = len;
}
//5.初始化环形链表
public void createLine(){
for(int i=1;i<=len;i++){
if(i==1){
//1.创建第一个人
Person person = new Person(i);
this.firstPerson = person;
this.temp = person;
}else {
//2.创建最后一个人
if(i==len){
Person person = new Person(i);
person.previousPerson = temp;
temp.nextPerson = person;
temp = person;
//指定最后一个人的下一个是第一个
temp.nextPerson = this.firstPerson;
temp.nextPerson.previousPerson = person;
}else {
//创建完第二个的时候指定上一个的对象是谁，也指定上一个的下一个对象是谁
Person person = new Person(i);
person.previousPerson = temp;
temp.nextPerson = person;
temp = person;
}
}
}
}
//6.游戏开始
public void play(){
Person temp = this.firstPerson;
//1.先找到开始数数的人
for(int i=1;i<k;i++){
System.out.println(temp.nextPerson.no+"开始数");
temp = temp.nextPerson;
}
while(this.len != 1){
//2.找到数第m下的人
for(int i=1;i<m;i++){
temp = temp.nextPerson;
}
//3.将数到m的人，退出;将数到第m下的人上一个人的nextPerson指定为数到第m下的人的nextPersono
temp.previousPerson.nextPerson = temp.nextPerson;
System.out.println(temp.no+"退出");
//4.temp就变成下一轮开始数数的人
temp = temp.nextPerson;
//5.然后减少一个人玩游戏，
this.len--;
}
//6.现在temp就是退出的那个人，它的nextPerson就是最后一个人
System.out.println("剩下的是100人中的第"+temp.no+"个人");
}
//7.打印链表
public void show(){
Person temp = this.firstPerson;
do{
System.out.println(temp.no);
temp = temp.nextPerson;
}while(temp != this.firstPerson);
}
}

复制代码

作者: 十万一千 时间: 2014-10-9 17:13
http://bbs.itheima.com/forum.php ... p;page=2#pid1018015

作者: 贾浩田 时间: 2014-10-18 17:26

ye361571404 发表于 2014-10-9 17:09
这道题我是看完韩顺平的这个视频做出来的：循序渐进学 java 从入门到精通第11讲-约瑟夫问题.avi

请问“其他人重新开始”是从那个人开始啊，是原来的1,？？还是接下来要开始报数的15啊？

作者: 贾浩田 时间: 2014-10-18 17:28

十万一千发表于 2014-10-9 17:13
http://bbs.itheima.com/forum.php?mod=viewthread&tid=147049&page=2#pid1018015

请问“其他人重新开始”是从那个人开始啊，是原来的1,？？还是接下来要开始报数的15啊？

作者: ye361571404 时间: 2014-10-18 20:02

贾浩田发表于 2014-10-18 17:26
请问“其他人重新开始”是从那个人开始啊，是原来的1,？？还是接下来要开始报数的15啊？ ...

接下来开始报数的15

作者: 哈达洋 时间: 2014-10-18 20:43
结果为92吧。

import java.util.*;
class test110
{
public static void main(String[] args)
{
//定义一个arraylist集合存储元素
ArrayList<Integer> al = new ArrayList<Integer>();
//向集合中添加100个元素（1-100数字）
for(int i=1;i<=100;i++)
{
al.add(i);
}
method_1(al);
}
public static void method_1(ArrayList<Integer> al)
{
//此处定义一个集合，是为了方便后面删除元素用。
ArrayList<Integer> buf = new ArrayList<Integer>();
//定义一个计数器，记录大家的报数。
int count=0;
//一直循环报数（1-100转完一圈再继续转的意思），删除元素，直到只剩下一个元素
while(true)
{
//判断元素是否为1
if(al.size()>1)
{
//100个人内部1-14循环报数
for(int index=0;index<al.size();index++)
{
//进入循环一次，计数器+1
count++;
//判断判断报的数是否为14的倍数，这里对1-14循环报数稍微做了下转换，应该不难理解
if(count%14==0)
{
//如果该角标的报数为14的倍数，则将该元素添加到上面定义好的buf集合。
buf.add(al.get(index));
}
}
//一次性删除al集合中包含的buf集合中的元素。
al.removeAll(buf);
//清空buf集合
buf.clear();
}
else
break;
}
System.out.println(al);
}
}

复制代码

作者: 十万一千 时间: 2014-10-18 21:36

贾浩田发表于 2014-10-18 17:28
请问“其他人重新开始”是从那个人开始啊，是原来的1,？？还是接下来要开始报数的15啊？ ...

http://bbs.itheima.com/forum.php ... p;page=5#pid1025567
你看下这个页面吧。。。退出一个人以后，当然是从退出的那个人的后一个人开始重新报数啦，从1开始报。

作者: 贾浩田 时间: 2014-10-18 22:44
我怎么觉得最后一个移除的元素肯定是14的整数被啊，应该是98（14x7）啊

作者: 贾浩田 时间: 2014-10-18 22:54

十万一千发表于 2014-10-18 21:36
http://bbs.itheima.com/forum.php?mod=viewthread&tid=147049&page=5#pid1025567
你看下这个页面吧。。 ...

谢谢，请问最后说“最后剩下的是100人中的第几个人？”这句话是什么意思啊，在问什么啊？我有点没读懂题意？什么叫最后剩下的啊，最后一个被移除的元素应该是a98啊，总共移除了7个元素，那最后一个人应该是第100-7=93的那个啊？怎么会是92呢？

作者: 十万一千 时间: 2014-10-18 23:20

贾浩田发表于 2014-10-18 22:54
谢谢，请问最后说“最后剩下的是100人中的第几个人？”这句话是什么意思啊，在问什么啊？我有点没读懂题 ...

最后剩余的当然是从来也没有自己报14的那个人啊如果有100个人围成一个圈，那么经过不断报数后，总共移除了100-1个人了。最后在100个人中第几个人是指初始状态下这个人的编号。

作者: 贾浩田 时间: 2014-10-18 23:28

十万一千发表于 2014-10-18 23:20
最后剩余的当然是从来也没有自己报14的那个人啊如果有100个人围成一个圈，那么经过不断报数后，总共移除 ...

哦意思是说所有人围城一个圈啊？那就是说要连续不断的持续报数喽？那看来有点深度

作者: 臭和尚 时间: 2014-10-23 12:18
class Test{
public static void main(String[] args){
int N = 100;
int s = 0;
int m = 14;
for(int i=2; i<=N; i++) {
s = (s+m)%i;
}
System.out.println("最终会留下的人的编号为:" + (s+1));
}
}

作者: 臭和尚 时间: 2014-10-23 12:19

class Test{
public static void main(String[] args){
int N = 100;
int s = 0;
int m = 14;
for(int i=2; i<=N; i++) {
s = (s+m)%i;
}
System.out.println("最终会留下的人的编号为:" + (s+1));
}
}

复制代码

作者: MeryStyle 时间: 2014-12-23 12:20

贾浩田发表于 2014-10-18 17:26
请问“其他人重新开始”是从那个人开始啊，是原来的1,？？还是接下来要开始报数的15啊？ ...

同问啊！！！“其他人重新开始”到底是从哪里重新开始（下一个？从头？）题目根本没有说明白啊！！
------从下一个开始是92，从头开始是2.。。。。。。

作者: 米家小九 时间: 2014-12-23 20:26
先瞅瞅，继续学习中

作者: lgc黑马 时间: 2014-12-27 21:41
顶顶顶顶顶

作者: 農邨尛夥兒 时间: 2015-1-2 22:51

package com.itheima;
import java.util.ArrayList;
import java.util.List;
/*
*10、有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
*然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
*
* 思路：
* 集合元素的角标从0开始要删除第14个人就是删除13角标
* 删除之后其他人继续重新报数那么就是在原来角标上+13 —— +14的话删除的是报15的人
* 由于当集合的长度<14时会循环报数故做%size操作
*
*/
public class Test10 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
//添加100人到集合
for (int i = 1; i < 101; i++) {
list.add(i);
}
System.out.println(list);
//删除所有报14的人
remove(list);
}
private static void remove(List<Integer> list) {
// TODO Auto-generated method stub
//确定集合长度
int size = list.size();
//设置被删除的角标因为集合角标从0开始所以第一次删除13
//如果集合的长度<要删除的角标数要做取余操作
int index = 13%size;
while(size>1){
//长度大于1 删除指定位置的元素
list.remove(list.get(index));
//删除一个元素集合长度-1
size--;
//重新确定角标
index = (index+13)%size;
}
//集合只剩下一个元素
System.out.println("100人中剩下的是第-"+list.get(0)+"-个人");
}
}

复制代码

兄弟我写了一个看我的是不是另类有这么写的么

作者: Catface 时间: 2015-4-8 17:16

public class Test10 {
public static void main(String[] args) {
for(int i=1;i<=10000;i++){
if(i%14==0 && i>9900){
System.out.println(i-9900);
}
}
}
}难道这么暴力算出的答案还不对吗？

复制代码

作者: lmcci 时间: 2015-4-18 00:23
import java.util.LinkedList;

public class Count {
public static void main(String[] args) {

LinkedList<Integer> i = new LinkedList<Integer>();

for (int x = 1; x < 101; x++) {
i.add(x);
}

while (i.size() != 1) {
for (int x = 0; x < 13; x++) {
i.add(i.removeFirst());
}
i.removeFirst();
}

System.out.println(i);

}
}

作者: 安日成 时间: 2015-5-3 18:08
谢谢分享

作者: zl074081027_hm 时间: 2015-5-12 16:34
我直接用数组做的，可参考。

package com.itheima;
/**
* 第10题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
* 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
* @author zl
*思路：
*一，可以定义一个数组，数组的索引表示每个人的id，元素大小可以设为0和1，0表示数到14的出圈的人，1表示还在圈里；
*二，定义count，表示当前报的数，具有累加性，定义在循环外；num表示在圈里剩下的人数；
*三，定义嵌套循环，内循环表示遍历数组并进行判断剩余的人数；外循环一直执行直到剩余人数为1就跳出。
*/
public class Test10_ArrayCount {
public static void main(String[] args) {
int[] arr = new int[100];
for(int i=0; i<arr.length; i++) {
arr[i] = 1;
}
//定义当前应该报的数
int count = 1;
//循环报数，报数一圈（遍历一次数组）为一次循环，得到剩余的人数和报数，并判断；
while(true) {
//定义圈里剩下的人数；由于出圈的人在仍在数组里，所以每次遍历前都需要先假定其没有出圈并进行判断；
int num = arr.length;
for(int i=0; i<arr.length; i++) {
//判断当前人数是否出圈，如果出圈则报数不改变而人数减1；如果在圈内，则先判断当前报数大小
if(arr[i]==0) {
//如果当前人早已经出圈，则num---
num --;
} else {
//如果当前人没有出圈，则判断报数大小
if(count !=14) {
//如果当前报数不等于14则下一个报数增1
count ++;
} else {
//如果当前报数为14，则当前元素值设为0，即出圈；重设count =1；圈里的人数变为num-1
arr[i] = 0;
count =1;
num --;
}
}
}
// System.out.println(num);
//如果循环一圈后，圈内人数为1，则跳出循环
if(num==1) {
break;
}
}
//遍历并选出元素为1的索引
for(int i=0; i<arr.length; i++) {
if(arr[i] == 1) {
//数组的索引是从0开始的，因此需要加1才表示实际的人的次序。不能说第0个人吧！
int left = i+1;
System.out.println("最后剩下的是第"+ left+"人");
}
}
}
}

复制代码

作者: zl074081027_hm 时间: 2015-5-13 16:29

臭和尚发表于 2014-10-23 12:19

嘿，哥们，能够对这个程序做点解释？这个简洁、高效的代码（我所见过的几种方法中最简洁最高效的），如果看不懂真是可惜啊！！！

作者: zhujunlin0108 时间: 2015-5-27 23:09
学习下！

作者: 王沙龙 时间: 2015-6-11 18:41
学习了，呵呵

作者: xxz 时间: 2015-7-6 02:06

public static void main(String[] args){
//创建链表集合 LinkedList
LinkedList<Integer> link=new LinkedList<Integer>();
for(int i=1;i<=100;i++){
plink.add(i);
}
int start=0,count=1;
int link_size=link.size();
while(link_size>1){
//循环移除链表集合元素的方式得到最后一个元素
System.out.println("第"+ count++ +"个退出的人的编号："+link.remove(start=(start+13)%link_size).intValue());
link_size=link.size();
}
//最后剩下的一个元素的order属性就是答案
System.out.println("\n"+"最后剩下的人的编号是："+link.peek().intValue());
}

复制代码

作者: chenyannna 时间: 2015-9-18 17:01
我怎么感觉这题会用递归呢？

作者: hnxtzouyuxi 时间: 2015-9-18 21:40
本帖最后由 hnxtzouyuxi 于 2015-9-18 21:43 编辑

package com.yuxi.day20;
import java.util.ArrayList;
public class Test2 {

/**
   * 需求:2、有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
   * 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
   *
   */
public static void main(String[] args) {
// TODO Auto-generated method stub
//建立一个集合分别把握1-100的数字存入
ArrayList<Integer> al =new ArrayList<Integer>();
for(int i=0;i<100;i++)
{
al.add(i+1);
}
method(al);
System.out.println(al.get(0));
}
public static void method(ArrayList<Integer> arr)
{
//报的数字开始值为1
int number=1;
while(true)
{
//确定集合中至少有一元素
if(arr.size()>1)
{
//循环遍历当number等入14的时候,删除集合相对应的为元素
for(int i=0;i<arr.size();i++,number++)
{
//当报到14的数就删除集合对应的元素
if(number==14)
{
//对number重新置0
number%=14;
arr.remove(i);
//删除后要使集合指向减1
i--;
}
}
}
//当最集合中只有一个元素的时候就是最后留下的那个人
else break;
}
}
}

作者: hnxtzouyuxi 时间: 2015-9-18 21:41
package com.yuxi.day20;
import java.util.ArrayList;
public class Test2 {

/**
   * 需求:2、有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
   * 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
   *
   */
public static void main(String[] args) {
// TODO Auto-generated method stub
//建立一个集合分别把握1-100的数字存入
ArrayList<Integer> al =new ArrayList<Integer>();
for(int i=0;i<100;i++)
{
al.add(i+1);
}
method(al);
System.out.println(al.get(0));
}
public static void method(ArrayList<Integer> arr)
{
//报的数字开始值为1
int number=1;
while(true)
{
//确定集合中至少有一元素
if(arr.size()>1)
{
//循环遍历当number等入14的时候,删除集合相对应的为元素
for(int i=0;i<arr.size();i++,number++)
{
//当报到14的数就删除集合对应的元素
if(number==14)
{
//对number重新置0
number%=14;
arr.remove(i);
//删除后要使集合指向减1
i--;
}
}
}
//当最集合中只有一个元素的时候就是最后留下的那个人
else break;
}
}
}

作者: zjingwen 时间: 2015-11-8 16:03

臭和尚发表于 2014-10-23 12:19

代码是对的。完全看不懂。。

作者: 865547883 时间: 2015-12-11 09:38
本帖最后由 865547883 于 2015-12-11 09:40 编辑

/*
* 10、有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
* 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
*/
public class Test10 {

      public static void main(String[] args) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            // 循环存储 1-100
            for (Integer i = 1; i <= 100; i++) {
                     al.add(i);
            }
            // 计数器
            int num = 0;
            // 外层循环当集合长度为1时结束循环
            for (; !(al.size() == 1);) {
                     // 内层循环遍历集合
                     for (int i = 0; i < al.size(); i++) {
                              // 每循环一次计数器 +1
                              num++;
                              // 判断当计数器为14的倍数时
                              if (num % 14 == 0) {
                                    // 删除这个元素
                                    al.remove(i);
                                    // 因为删除了1个元素，所以这个删去元素的索引上，是这个删去元素的后一个
                                    // 让索引减一重新遍历该索引上的元素
                                    i--;
                              }
                     }
            }
            System.out.println(al.toString());
      }
}

作者: renkuo023 时间: 2016-2-17 06:57
题目就不怎么清楚

作者: 青争心 时间: 2016-4-3 18:39
我刚做完不客气幸运数字
-

作者: dreamwork 时间: 2016-4-11 22:56
新人路过，努力学习中

作者: qq365616276 时间: 2016-4-14 20:17
啊啊发生的公司的分公司答复

作者: keyingchang0909 时间: 2016-5-22 18:12
代码呢,写出来啊

作者: SQQ 时间: 2016-6-10 18:23
学习了。。。

作者: zk小罗 时间: 2016-7-19 00:32

臭和尚发表于 2014-10-23 12:19

好牛 o.O
int k = 100;

LinkedList list = new LinkedList<Integer>();
for(int i=1;i<=k;i++)
list.add(i);

Iterator it = list.iterator();

while(list.size()!=1) {
for(int i=0;i<14;i++) {
if(!it.hasNext())
it = list.iterator();
it.next();
}
it.remove();
}
System.out.println(list.get(0));

这是我的代码，我想过用数组的，但是不知道怎么解决，你这个好简洁啊

作者: zk小罗 时间: 2016-7-19 00:35

臭和尚发表于 2014-10-23 12:18
class Test{
public static void main(String[] args){
int N = 100;

循环里面的 s = (s+m)%i; 代表什么呢

作者: qinye 时间: 2016-8-30 00:48

ye361571404 发表于 2014-10-9 17:09
这道题我是看完韩顺平的这个视频做出来的：循序渐进学 java 从入门到精通第11讲-约瑟夫问题.avi

这个代码，基本接近API 的链表源码了吧。。。。我这个菜鸟只能望洋兴叹了

作者: qinye 时间: 2016-8-30 01:02

ye361571404 发表于 2014-10-9 17:09
这道题我是看完韩顺平的这个视频做出来的：循序渐进学 java 从入门到精通第11讲-约瑟夫问题.avi

这个代码，基本接近API 的链表源码了吧。。。。我这个菜鸟只能望洋兴叹了

作者: sfb749277979 时间: 2016-9-9 15:07
package 练习; import java.util.ArrayList; public class Test2 { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 1; i < 101; i++) { list.add(i); } int count=0; while(true){ if(list.size()>1){ for (int i = 0; i < list.size(); i++) { count++; if(count==14){ list.remove(i); count=0; i--; } } }else{ break; } } System.out.println(list); } }

作者: 15520102030 时间: 2017-8-13 16:02
其实这题还是比较简单的啦,主要还是思路问题,我的思路是当14个人退出后从15个人开始重新数,当然此时的第15人在这个圈中是14,因为他取代了原来退出的14的那个人的位置!    思路:我们可以定义两个变量,一个用于记录报数的人是第几个人,另一个记录报数的总次数
   步骤:  A:定义count 记录次数,当count%14==0的时候,说明有人该退出了
               B:定义一个循环用于记录那个人在报数,当这个报数的人报到最后一个人的时候,又从第一个人开始报数
               C:一直重复上面的步骤,直到只有一个人的时候就输出这个人就行了.
语言表达能力比较差,直接上代码吧!
ArrayList<Integer> list=new ArrayList<>();
for (int i = 1; i <= 100; i++) {
list.add(i);
}
int count=0;//记录报数的次数
for (int j = 1; j <= list.size(); j++) {//j就表示是第几个人在报数
count++;
if (count%14==0) {
int a=list.get(j-1);
list.remove(j-1);
j--;
}
if (j>=list.size()&&list.size()!=1) {//当只有一个人的时候就不需要再回去了
j=0;//因为是围成一个圈所以当每个人都报数完后回到第一个人报数,因为这里放在循环的末尾,结束后j会马上自增一次
}
                     syso输出这个身下的数就行了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2