A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,凡是报到“3”就退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
个人分析:用数组定义,int person[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
报数报1,2,3,那第一次报数后就剩下 1,2,4,5,7,8,10,11,13,14
第二次在重新报数后剩下 1,2,5,7,10,11,14
第三次在重新报数后剩下 1,2,7,14
第四次在重新报数后剩下 1,2,14
第四次在重新报数后剩下 1,2,
要是按这种排除法算得话是剩下两个人,为什么题中说的是剩下一个人,

21 个回复

倒序浏览
本帖最后由 xiniuniu 于 2015-5-1 14:06 编辑

最后两个人,  第一个报1, 第二个报2, 接着第一个再报3, 第一个人出局, 第二个留下...我是用链表做的. 有点麻烦  ,  前几天也看到有同学用数组做的
思路大体是这样   如 int  arr[6] = {1, 2, 3, 4, 5, 6}; 数组中存放每个人的编号
报到3的人出局, 那么后边的编号前移, 空出来的位置设置为0, 每次循环到0则从头开始

第一个 {1, 2, 4, 5, 6, 0}
第二个{1, 2, 4, 5, 0, 0}
第三个{1, 2, 5, 0, 0, 0};
第四个{1, 5, 0, 0, 0, 0};
......

当数组中只有一个不为0时退出循环  大体思路是这样吧.  细节还需仔细斟酌
回复 使用道具 举报
首先,我要说,你理解的不对,并不是当前所有的人报完后重新开始报数,而是接着报数。
举个例子:第二次报数后,【5】和【11】应该被删除,但是【14】这个时候的报数应该是1,然后开始下一圈报数,也就是【1】报数2,【2】报数3,【2】被删除,依次类推(跟我们平常玩游戏一样,并不是你理解的从【1】开始重新报数),最后只剩下1个人,结果应该是【5】。
注:上述说明中【】代表人
下面有我写的一段代码,按照我上面的思路来的,你可以看一下
  1. /*

  2. 耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,凡是报到“3”就退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
  3. */


  4. #include <stdio.h>


  5. int main()
  6. {
  7.    
  8.     int person[15];
  9.     //初始人数
  10.     int count = sizeof(person)>>2;
  11.     //赋值
  12.     for (int i =1;i<=count;i++)
  13.     {
  14.         person[i-1]=i;
  15.     }
  16.     //报数
  17.     int baohao = 0;
  18.     //循环调用,直到剩下1个人的时候停止
  19.     while(count > 1)
  20.     {
  21.         //从第一个开始报号
  22.         for(int i = 0;i < count;i++)
  23.         {
  24.             baohao++;
  25.             //报到3的人从数组中删除
  26.             if(baohao == 3)
  27.             {
  28.                 for(int j = i;j < count;j++)
  29.                 {
  30.                     person[j] = person[j+1];
  31.                 }
  32.                 //数组中剩余的人数-1
  33.                 count--;
  34.                 //下一次报号从删除数据后这个位置开始
  35.                 i--;
  36.                 //报号清零,从新报号
  37.                 baohao = 0;
  38.             }
  39.         }
  40.     }

  41.     for (int i = 0;i < count;i++)
  42.     {
  43.         printf("%d",person[i]);
  44.     }
  45.     printf("\n");
  46.    
  47.     return 0;
  48. }
复制代码


当然,这道题还有很多更好的思路,这只是最简单易于理解的一种,还可以有递归,循环链表(这个会更好),这里不具体说了,有兴趣可以自己研究一下,希望上面的思路对你有帮助
回复 使用道具 举报
谢谢楼上的朋友,看来是我理解有误了,我在研究一下多谢:lol
回复 使用道具 举报
流风124 发表于 2015-5-1 14:30
首先,我要说,你理解的不对,并不是当前所有的人报完后重新开始报数,而是接着报数。
举个例子:第二次报 ...

  int count = sizeof(person)>>2;   是什么意思
回复 使用道具 举报
初楠 发表于 2015-5-1 16:16
int count = sizeof(person)>>2;   是什么意思

右移2位,相当于除以4
回复 使用道具 举报
可以使用余数循环  相当于让所有人在一个圈内头和尾可以相接
回复 使用道具 举报
87526845 发表于 2015-5-1 16:48
可以使用余数循环  相当于让所有人在一个圈内头和尾可以相接

可以给个具体实现吗?有点兴趣
回复 使用道具 举报
余数循环就像一个圈 然后 一个圈一直在里面转  最后只剩一个人就行了 代码就自己想吧:D
回复 使用道具 举报
流风124 发表于 2015-5-1 16:44
右移2位,相当于除以4

知道是右移    为什么要这么做呢
回复 使用道具 举报
初楠 发表于 2015-5-1 19:33
知道是右移    为什么要这么做呢

只是为了求数组元素个数,其实不用也可以
回复 使用道具 举报
第四次后,第一人报1,第二人报2,第三人再报1
回复 使用道具 举报
思考中……
回复 使用道具 举报
学习了   
回复 使用道具 举报
首先,耶稣有15个弟子吗?呵呵
其次,楼主理解有误啊,报数应该是循环的(15个门徒围成一个圈,报到最后的时候会跳到第一个),而不是你理解的那种。所以,这个题目用循环单链表来做的话会比较轻松。
解决思路:
1、把门徒定义为一个结构体,包含两个成员,一个存储原来的序号(这也是题目要问的),另一个属性存每次更新的报号。
2、然后是链表的事儿了:设定一个单链表存放序号和每次更新的报号;将单链表设置为循环单链表;遍历单链表设置每个门徒报号(1、2、3)同时监控报数为3的门徒剔除掉,剩下的门徒继续报数;一直到自己指向自己就表示只剩他自己了,叛徒出来了。

/*耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,
*请用排除法找出这位叛徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,
*凡是报到“3”就退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
*/
#include <stdio.h>
typedef   struct menTu{
    int startNo;
    int endNo;
    struct menTu *next;
} Mt;

Mt *initMt(int n){

    // 表头h,指向当前节点next的指针p,当前节点s
    Mt *h,*p,*s;

    // 为h分配内存
    if ((h=(Mt *)malloc(sizeof(Mt)))==NULL) {
       exit(0);
    }
    // 把h置空
    h->next = NULL;

    // p移到h
    p = h;

    //循环赋值初始序号

    int i = 1;
    for (; i<n+1; i++) {

        // 为s分配内存
        if ((s=(Mt *)malloc(sizeof(Mt)))==NULL) {
            exit(0);
        }

        // s的序号为依次+1,endNo初始化均为0
        s->startNo = i;
        s->endNo = 0;

        // 置空s
        s->next = NULL;

        // p所在节点的next指向s
        p->next = s;

        // 将指针移到s节点上
        p = s;
    }

    // 返回表头h
    return h;
}

void findTraitor(Mt *h)
{
    // 定义指针temp,以前指向next的指针p
    Mt *temp,*p;

    // p所在的节点为表头h的next
    p = h->next;

    // 开始遍历,报数,给每个人的endNo赋值1,2,3
    int i = 0;
    for (; i<50; i++)
    {
        // 设置p所在节点的报数endNo为1,2,3
        p->endNo = i%3+1;

        // 判断,当p所在节点报数为3时,剔除
        if (p->endNo==3)
        {
            // 判断该节点是否为最后一个节点
            while (p->next==NULL) {
                //如果是最后一个节点,将该节点的next指向表头的next
                p->next = h->next;
            }
            // 输出剔除了的门徒的初始序号
            printf("剔除%d:\n",p->startNo);

            // 将之前节点与之后节点相链接
            temp->next = p->next;

            // 打印输出剔除了后,next节点的初始序号
            printf("剔除后next节点是%d:\n",p->next->startNo);

            // 将p移动到p所在节点的next链节
            p = p->next;

        }else
        {
            // p所在节点的当前报数不为3
            // 将p所在节点保存到temp
            temp = p;

            // 如果p的next节点不是p自己,那就是还剩下至少2个人,就继续报数,当只剩1人退出
            if (p->next!=p)
            {
                //将p移动到next节点
                p = p->next;

            }else
            {
                // next是自己,表示只剩下1个,输出叛徒
                printf("叛徒是%d:\n",p->startNo);

                // 跳出循环,结束游戏
                break;
            }
        }
    }
}

int main()
{
    Mt *p = initMt(15);   
    findTraitor(p);
    return 0;
}
最后,仅供参考,不对的地方请指正,谢谢!
回复 使用道具 举报
我叫顺子 来自手机 中级黑马 2015-5-1 23:01:04
16#
谢谢各位的解答
回复 使用道具 举报
论坛有各种解法,还有最简洁的数学公式。
可惜都缺少 引导的思路,知道这样,却不知道为什么会想到这些。
直到我后来看到这个:
http://v.ku6.com/show/TXV_tn2WisSr2H2s4k7jEw...html
终于理解了这个问题。
回复 使用道具 举报
一种是用13个 元素的数组装,存1到13,每次报3的元素删掉再让数组集体向前缩进直到只剩下一个元素.另一种就是引入flag标记的思想循环遍历,用i%13来实现循环,遇到报3的元素改标记,直到只剩一一个元素的标记没改.我大致就想到这两张做法
回复 使用道具 举报
好复杂的赶脚啊、。。。
回复 使用道具 举报
kailee 发表于 2015-5-1 22:56
首先,耶稣有15个弟子吗?呵呵
其次,楼主理解有误啊,报数应该是循环的(15个门徒围成一个圈,报到最后的 ...

大神啊,拜服
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马