黑马程序员技术交流社区

标题: 50个人围成一圈数到三和三的倍数时出圈，问剩下的人是谁... [打印本页]

作者: void 时间: 2014-10-22 11:50
标题: 50个人围成一圈数到三和三的倍数时出圈，问剩下的人是谁...
50个人围成一圈数到三和三的倍数时出圈，问剩下的人是谁？在原来的位置是多少？

作者: 紫薰iy 时间: 2014-10-22 11:50
package com.ming.test.test9999;

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

public class Test1 {
static int num;
//B  记录每个人叫到的数字
static List<Integer> a;
//记录第一圈初始1-50的数字
static List<Integer> b;
//记录每一圈的数字为3的倍数的  下角标
static List<Integer> c;

public static void main(String[] args) {
init();
int i = 0;
print(a, "a");
print(b, "b");
print(c, "c");
while (a.size() != 1) {
System.out.println(i);

find();
print(c, "c");
delete();
resetA();

print(a, "a");
print(b, "b");

i++;
}
}
//重置A的数字
public static void resetA() {
for (int i = 0; i < b.size(); i++) {
a.add(++num);
}
}
//找到A中数字为3的倍数
public static void find() {
for (int i = 0; i < a.size(); i++) {
if (a.get(i) % 3 == 0) {
//添加记录到C中
c.add(i);
}
}
}
//初始化
public static void init() {
a = new ArrayList<Integer>();
b = new ArrayList<Integer>();
c = new ArrayList<Integer>();
for (int i = 0; i < 50; i++) {
a.add(i + 1);
b.add(i + 1);
}
num = 50;
}
//删除  B中的数字。清空A和C
public static void delete() {
//从B的最后的值开始删除。否则B的长度会发生变化，导致后面的值删除的位置会发生错误
for (int i = c.size() - 1; i > -1; i--) {
int ii = c.get(i);

/////////////////////
/*
   * 其中的方法在这里耽误的时间比较多
   * 因为，remove(5)；
   * 之前没有解决好，会把B中的5删除，而不是删除下角标为5的元素
   */
b.remove(ii);
/////////////////////
}
a.clear();
c.clear();
}
//打印
public static void print(List<Integer> i, String str) {
System.out.println(str);
for (int j = 0; j < i.size(); j++) {
System.out.print(i.get(j) + " ");
}
System.out.println();
}
}

还望共同讨论更好的方法。楼主5个黑马币给我吧

作者: 勇闯黑马 时间: 2014-10-22 19:19
菜鸟撸过看看

作者: ganjx 时间: 2014-10-22 23:31
本帖最后由 ganjx 于 2014-10-22 23:33 编辑

package com.testthree;
public class TestThree {
public static void main(String[] args) {
// TODO Auto-generated method stub
TestThree tt =new TestThree();
tt.Test();
}
//数数的方法
public void Test()
{
//创建1-50的数组
int[]three = new int[50];
for(int i =1;i<51;i++)
{
three[i-1]=i;
}
//
int flag =50;//初始总共有50个数
int number =0;
//只要数量大于3就要一直数下去
while(flag>=3)
{
for(int i =1;i<51;i++)
{
if(three[i-1]!=0)//将数过3或3的倍数的跳过
{
number++;
if(number%3==0)//数过3或3的倍数时将基标为0
{
flag-=1;//每数一次，总数少一个
three[i-1]=0;
}
}
}
}
for(int i =1;i<51;i++)
{
if(three[i-1]!=0)
{
System.out.println(i);
}
}
}
}

复制代码

<p style="line-height: 30px; text-indent: 2em;"></p>

复制代码

此题主要还是考查我辈的基本功了，我就直接贴代码，最后打印出11，43；

TestThree.zip

617 Bytes, 下载次数: 328

相应的实现代码

作者: 十指紧扣 时间: 2014-10-23 12:41
厉害…………………………

作者: qinjingbo 时间: 2014-10-24 22:08
菜鸟飞过，欣赏一下。

作者: maralbertlee 时间: 2014-10-26 11:17
约瑟夫算法：

public static void main(String[] args) {
int n = 50, m = 3;
int index = 0;
for (int i = 2; i <= n; i++) {
index = (index + m) % i;
}
System.out.println(index + 1);
}

复制代码

其实这个我也不大懂，数学成绩不咋地啊

作者: 未来就在那 时间: 2014-10-28 12:33
欣赏一下。

作者: 计算机小菜鸟 时间: 2014-10-31 22:05
菜鸟路过看看！！！

作者: chenhuan_ccit 时间: 2014-11-1 13:29

#include <stdio.h>
int main(int argc, const char * argv[])
{
// insert code here...
int p[15]={0}; // 初始化数组
int n=15; // 剩余人数;
int i=1; // 报号
int j=0; // 下标
while(n>1){
if(p[j]==0&&i==3){ // 判断报号是否为3,且没有出列的人
p[j]=1; // 将其出列
i=1; // 报号初始化为1
n--; // 剩余人数减1
}else if(p[j]==0&&i!=3){ // 判断报号不为3,且没有出列的人
i++; // 报号+1
}
if(++j==15){ // 数组下标+1,并判断是否越界
j=0; // 下标越界,初始化为0
}
}
for(i=0;i<15;i++){
if(p[i]==0){
printf("出卖耶稣的叛徒序号：%d\n",i);
}
}
return 0;
}

复制代码

作者: chenhuan_ccit 时间: 2014-11-1 13:33
上面是我的方法，你看看怎么样

作者: 邵起 时间: 2014-11-2 09:09

ganjx 发表于 2014-10-22 23:31
此题主要还是考查我辈的基本功了，我就直接贴代码，最后打印出11，43； ...

楼主的意思不是只剩一个人吗。。。

作者: ganjx 时间: 2014-11-2 17:30

邵起发表于 2014-11-2 09:09
楼主的意思不是只剩一个人吗。。。

谢谢指出问题，第二十二行改为下面的即可，最后输出11

while(flag>=2)

复制代码

作者: 银河雨 时间: 2014-11-3 21:23

#include <stdio.h>
#include <stdlib.h>
typedef struct LinkNode linkNode;
//创建一个结构体，用来表示每个节点
struct LinkNode {
//每个节点的编号
int id;
//这个节点的下一个的地址
linkNode *next;
};
int main()
{
//初始化第一个节点。设置变量当前节点和下一个节点
linkNode *head = NULL , *tempCurrent,*tempNext;
//创建节点
//创建第一个节点
tempCurrent = (linkNode *)malloc(sizeof(linkNode));
head = tempCurrent;
head -> id = 1;
//创建之后的节点
for (int i = 2; i <= 50; i ++) {
//分配节点大小
tempNext = malloc(sizeof(linkNode));
tempNext -> id = i;
tempCurrent -> next = tempNext;
tempCurrent = tempNext;
}
//循环链表
tempCurrent -> next= head ;
linkNode *replace = head,*temp = NULL;
//查找要去除的点,直到还剩最后一个点
while (replace -> next != replace) {
//设置间隔数量，不是间隔数就直接跳过，直到找到间隔数的节点
for (int j = 1; j < 3; j ++) {
temp = replace;
replace = replace -> next;
}
//去除满足要求的点
temp -> next = replace -> next;
printf("出局的是 %d\n",replace -> id);
//释放节点内存
free(replace);
//临时变量向后移
replace = temp -> next;
}
//找出最后剩下的点
printf("最后还剩下的是 %d\n",replace -> id);
return 0;
}

复制代码

C语言写的，望采纳

作者: 渐行渐远 时间: 2014-11-3 22:43
本帖最后由渐行渐远于 2014-11-3 22:46 编辑

import java.util.ArrayList;
import java.util.List;
public class ZhuanQuan {

      public static void main(String[] args) {
            //创建数组型队列
            ArrayList<Integer>al=new ArrayList<Integer>();
            for(int i=1;i<=50;i++){
                     al.add(i);//添加元素
            }
            while(al.size()>1){    //剩最后一人时停止
                     for(int j=0;j<3;j++){
                           int x=al.remove(0);//将点到的人取出
                           if(j%3!=2){
                                    al.add(x); //不是3的倍数再加到队尾
                              }
                     }

            }
            System.out.println("最后一个人是"+al.get(al.size()-1));
      }

}

作者: 梦与现实 时间: 2014-11-4 01:55
/*
根据你的需求这里用到了一个关于数组的古典游戏“猴子选大王”的算法
参选的人按1 2 3......n编号并按顺序围成一圈,由第K人（这里K可以根据个人要求指定）开始从1报数
报数到达P时跳出圈外，再由下一个人从1开始如此循环知道剩下最后一人这人也就是（猴子选大王算法中的王）我们所需要的人
*/
import javax.swing.JOptionPane

public class PersonKing{
public static void main(String[] args){
String s;
int n, k, p,n1;

s=JOptionPane.showInputDialog("请输入人数的总数");
n=Integer.parseInt(s);
n1=n+1;
s=JOptionPane.showInputDialog("请输入起始报数人的编号");
k=Integer.parseInt(s);
s=JOptionPane.showInputDialog("请输入出局数字: ");
p=Integer.parseInt(s);
int a[]=new int[n+1];
a[0]=0;
System.out.println("\t 出局人的编号： ");
for(int i=1;i<a.length;i++)
a[i]=1;
for(int i=1;i<=p;i++){
if(n==1)
break;
else if(i==p||i/3==0){
n--;
i=0;
a[k]=0;
System.out.print(k+" ");

}
do{
k++;
k=k%n1;
}where(a[k]!=1);
}

System.out.println("\n 最后剩余的人的编号为:"+k);

}
}

作者: 梦与现实 时间: 2014-11-4 02:09
请楼主仔细看16楼中我想这个应该是最标准的算法了（猴子选大王算法）
里面你要求是50人我这里都没规定死我是基于算法本身，变量不写死。这个方法就可以单独做成类。方便以后调用。也就是说以后遇到不是人数是50 第3人或3的倍数（也就是被3整除=0）出局的时候可以套用。。这是个公式。。就跟真理是已经经过多代人验证过一样，与其说是帮你解决这问题不如说是教你认识一种前人验证好了的方法，我们要记住以后遇到类似的问题不用去研究新算法改怎么实现，直接拿过来套用笔着葫芦画瓢，节省时间久是节省金钱

作者: 计算机小菜鸟 时间: 2014-11-7 23:35
路过看看

作者: yuanlingqi 时间: 2014-11-8 13:42
本帖最后由 yuanlingqi 于 2014-11-8 13:49 编辑

50个人围成一圈，形成一个闭环，这个一个典型的链表结构，每次出圈，只要把出圈人的左右对接即可，链表最后剩下的那个人，就是你想要的。不多说上代码：

//先要有个用户，包含三个属性
package cn.csdn.test;
public class User {
/**
* 用户id
*/
private int userId;
/**
* 下个用户
*/
private User next;
/**
* 上个用户
*/
private User pre;
public User(int no) {
this.userId = no;
}
public int getUserId() {
return userId;
}
public void setUserId(int userId) {
this.userId = userId;
}
public User getNext() {
return next;
}
public void setNext(User next) {
this.next = next;
}
public User getPre() {
return pre;
}
public void setPre(User pre) {
this.pre = pre;
}
}

复制代码

2.游戏开始

package cn.csdn.test;
import cn.csdn.test.User;
public class GamePlay {
/**
* 出圈数数
*/
private static int OUTNUMBER = 3;
/**
* 玩游戏的人数
*/
private static int USERCOUNT = 5;
public static void main(String[] args) {
if(USERCOUNT <= 0 || OUTNUMBER <= 0) {
System.out.println("你逗我？");
System.exit(-1);
}
//1.将50个人围成一圈，构成单向链表结构
User firstUser = null,curUser = null,newUser = null;
for(int i=1; i<=USERCOUNT;i++){
newUser = new User(i);
if(firstUser == null){
firstUser = newUser;
curUser = newUser;
}else{
newUser.setPre(curUser);
curUser.setNext(newUser);
curUser = newUser;
}
}
//形成闭环
curUser.setNext(firstUser);
firstUser.setPre(curUser);
//2.从头开始遍历链表，数到3的人出链表，再将出圈人的左右两人对接
User temp = firstUser;
int i = 1;
do{
if(temp != null && i % OUTNUMBER == 0){
User pre = temp.getPre();
User next = temp.getNext();
if(next == pre) {
temp = next;
break;
}
pre.setNext(next);
next.setPre(pre);
temp = next;
i=1;
}else{
temp = temp.getNext();
i++;
}
}while(true);
System.out.println("共有"+ USERCOUNT + "玩家,最后留在圈的人是 " + temp.getUserId());
}
}

复制代码

作者: yuanlingqi 时间: 2014-11-8 13:53

yuanlingqi 发表于 2014-11-8 13:42
50个人围成一圈，形成一个闭环，这个一个典型的链表结构，每次出圈，只要把出圈人的左右对接即可，链表最后 ...

从1开始编号和数数，50人最后剩下的是11号

作者: wingtheu 时间: 2014-11-8 22:19
//此算法可以求出剩下的那个人的位置和序号
import java.util.LinkedList;
import java.util.List;
//测试类
public class Cycle {
public static int cycle(int total, int k) {  //功能方法
      List<Integer> dataList = new LinkedList<Integer>();//创建链表对象
      for (int i = 0; i < total; i++)  //添加数据元素
         dataList.add(new Integer(i + 1));
      int index = -1;  //定义下标，模拟已经去掉一个元素，因此从-1开始
while (dataList.size() > 1) { //一直循环去除数据，直到只剩下一个元素
         index = (index + k) % dataList.size();//得到应该出局的下标
         dataList.remove(index--);  //去除元素
      }
      return ((Integer) dataList.get(0)).intValue();//返回它的值
}
  //主方法
public static void main(String[] args) {
      System.out.println("该数字原来的位置是："+cycle(50, 3));
}
}

作者: zsfy 时间: 2014-11-9 22:28
#include <stdio.h>
int main()
{
int k=0,j=0;
int name[50];
for (int m=0;m<50;m++)          //给数组编号，1~50 此时m=50
{
name[m]=m+1;
}
for (int i=m;i>1;)                               //i 表示人数,此时m=50
{
if (name[j]!=0)
{
k++;
}
if (k==3)                               //k为报数值，
{
name[j]=0;                //此时将此人的值赋值为0,表示此人已经排除
k=0;                               //重新赋值给k
i--;                               //人数减1
}
j++;
if(j==m)
{
j=0;             //由于是围成一圈,当j的值等于15时，将其设置为0
}
}
for (int n= 0; n< m; n++)
{
   if (name[n] > 0)             //最后一个不为0的数字编号即为叛徒的编号
{
         printf("出卖耶稣的叛徒的原来序号是%d\n",name[n]);
      }
}
return 0;
}

作者: 暴君 时间: 2014-11-12 19:18
不是很懂，但是个人感觉猴子那个更好点，毕竟没有写死，可以套用

作者: 18643116874 时间: 2014-11-17 23:19
菜鸟路过，学习下。

作者: Smart_lll 时间: 2014-11-18 09:31

ganjx 发表于 2014-10-22 23:31
此题主要还是考查我辈的基本功了，我就直接贴代码，最后打印出11，43； ...

N，厉害，赞一个！！！

作者: 郑飞 时间: 2014-11-21 15:02
本帖最后由郑飞于 2014-11-21 15:04 编辑

原创;P 就用了1个for2个if 还算比较简便思路也不难咱新手就图个思路并不是为解题而解题希望对楼主有帮助

class Test
{
/*
*50长度元素值全1的数组1个
*count不断循环数组并累加所有元素值;
*count逢3时,元素值改为0(为了下次count访问并累加该元素时不计数,count的存在就是为了逐步把每个元素值都改为0);
*这时update++(因为count遇到3的倍数了,update记录);
*当update为50的时候说明找到最后一个元素,返回角标+1;
**/
public static void main(String[] args)
{
int[] arr = new int[50];
for(int i = 0;i<50;i++)
arr[i] = 1;//定义一个长度50,元素值都为1的数组;
for(int i =0,count = 0,update = 0;;i++)//上面说的很清楚了
{
i = i==50?0:i;//从角标0开始不断循环访问数组所有元素(i=50就重置为0);
//如果上次count值不能被3整除,并且本次count能被3整除,说明该位置是1(0代表);
if(count%3!=0&(count+=arr[i])%3==0)
{
arr[i]=0;//元素值改为0,让count无视它
update++;//记录本次被3整除时事件
}
if(update==50)//当遇到50次被3整除后,说明最后一次访问的就是数组最后一个值为1的元素
{
System.out.println(i+1);//放回角标+1(位置)
break;
}
}
}
}

复制代码

作者: 刘隽哲 时间: 2014-11-25 23:05
学习了膜拜大神感觉自己好菜呀

作者: 致美丽的你 时间: 2014-12-5 21:11
这是纯粹的数学问题，11和43

作者: lwh316658735 时间: 2014-12-8 15:57
ArrayList 在迭代时，判断，使用递归比较方便

作者: win_top1 时间: 2014-12-13 11:55
顶一个:)

作者: JiangHG 时间: 2015-3-14 11:42
本帖最后由 JiangHG 于 2015-3-14 11:43 编辑

此问题可用循环链表模拟，节点的num存储信徒的序号,用一个变量暂存所报的序号，如果是3则将这个节点从链表中下链。
#include <stdio.h>
#include <malloc.h>
#define MAX 50 //人数

typedef struct student {
int num;
struct student *next;
}s_list;
/* 创建循环链表 */
s_list *creat_list()
{

s_list *head = NULL;
      s_list *p = NULL;
      s_list *q = NULL;
int i = 0;
      /* 申请头节点的存储空间 */
head = p = (s_list *)malloc(sizeof(s_list));
      if (NULL == head)
      {
            printf ("malloc error!");
            return;
      }
p->num = 1;// 序号
      /* 初始化第二到最后面的序号*/
for (i = 2;i <= MAX; i++)
      {
      q = (s_list *) malloc(sizeof(s_list));
            if (NULL == q)
            {
                     printf ("malloc error!");
                     return;
            }
      q->num = i;
      p->next = q;
            p = q;
}
      /* 由于循环链表将最后一个节点的next指向头*/
p->next = head;

return(head);
}
/* 执行报数的流程 */
s_list *del_people(s_list* head)
{

s_list *p1 = head;
      s_list *p2 = head;
      s_list *del_node = NULL;
int k = 1; //用于记录当前所报的数

while(p1->next != p1) //只有一个人
      {
      if(k == 3) /* 报到三则下链 */
            {
         del_node = p1; //标记要删除的节点
                     /* 下链并释放 */
         p1 = p1->next;
         p2->next = p1;
         free(del_node);
         del_node = NULL;
         k = 0;
      }
            else
            {
         p2 = p1;
         p1 = p1->next;
      }
      k++;
}
p1->next = NULL;
return(p1);
}
/* 打印最后的叛徒序号 */
void print_alive_pelple(s_list *head)
{
      s_list *p = NULL;
      if (NULL == head )
      {
            return;
      }
printf("alive num is %d\n",head->num);

}
/* 主函数 */
int main()
{
s_list *head = NULL;
      s_list *alive_node = NULL;
/* 创建并初始化一个循环链表 */
head  = creat_list();
      /* 报号并退出出的执行 */
alive_node = del_people(head);
      /* 输出最后的叛徒 */
print_alive_pelple(alive_node);
      /* 释放链表防止内存泄漏 */
free(alive_node);
      alive_node =  NULL;
return 0;
}

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

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