黑马程序员技术交流社区

标题: 关于入学测试耶稣的那道题，求思路 [打印本页]
作者: 冰儿    时间: 2015-5-1 12:36
标题: 关于入学测试耶稣的那道题，求思路
耶稣有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，
要是按这种排除法算得话是剩下两个人，为什么题中说的是剩下一个人，
作者: xiniuniu    时间: 2015-5-1 13:57
本帖最后由 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时退出循环  大体思路是这样吧.  细节还需仔细斟酌
作者: 流风124    时间: 2015-5-1 14:30
首先，我要说，你理解的不对，并不是当前所有的人报完后重新开始报数，而是接着报数。
举个例子：第二次报数后，【5】和【11】应该被删除，但是【14】这个时候的报数应该是1，然后开始下一圈报数，也就是【1】报数2，【2】报数3，【2】被删除，依次类推（跟我们平常玩游戏一样，并不是你理解的从【1】开始重新报数），最后只剩下1个人，结果应该是【5】。
注：上述说明中【】代表人
下面有我写的一段代码，按照我上面的思路来的，你可以看一下
  1. /*

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


  7. #include <stdio.h>


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

  47.     for (int i = 0;i < count;i++)
  48.     {
  49.         printf("%d",person[i]);
  50.     }
  51.     printf("\n");
  52.    
  53.     return 0;
  54. }
复制代码


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

  int count = sizeof(person)>>2;   是什么意思
作者: 流风124    时间: 2015-5-1 16:44
初楠 发表于 2015-5-1 16:16
int count = sizeof(person)>>2;   是什么意思

右移2位，相当于除以4
作者: 87526845    时间: 2015-5-1 16:48
可以使用余数循环  相当于让所有人在一个圈内头和尾可以相接
作者: 流风124    时间: 2015-5-1 16:54
87526845 发表于 2015-5-1 16:48
可以使用余数循环  相当于让所有人在一个圈内头和尾可以相接

可以给个具体实现吗？有点兴趣
作者: 87526845    时间: 2015-5-1 17:10
余数循环就像一个圈 然后 一个圈一直在里面转  最后只剩一个人就行了 代码就自己想吧:D
作者: 初楠    时间: 2015-5-1 19:33
流风124 发表于 2015-5-1 16:44
右移2位，相当于除以4

知道是右移    为什么要这么做呢
作者: 流风124    时间: 2015-5-1 20:05
初楠 发表于 2015-5-1 19:33
知道是右移    为什么要这么做呢

只是为了求数组元素个数，其实不用也可以
作者: 嗨灬小凯    时间: 2015-5-1 21:43
第四次后,第一人报1,第二人报2,第三人再报1
作者: wusanzhong    时间: 2015-5-1 22:17
思考中……
作者: ios专用    时间: 2015-5-1 22:26
学习了   
作者: kailee    时间: 2015-5-1 22:56
首先，耶稣有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
谢谢各位的解答
作者: 仰望的繁华    时间: 2015-5-1 23:07
论坛有各种解法，还有最简洁的数学公式。
可惜都缺少 引导的思路，知道这样，却不知道为什么会想到这些。
直到我后来看到这个：
http://v.ku6.com/show/TXV_tn2WisSr2H2s4k7jEw...html
终于理解了这个问题。
作者: 冬天的章鱼烧    时间: 2015-5-1 23:12
一种是用13个 元素的数组装,存1到13,每次报3的元素删掉再让数组集体向前缩进直到只剩下一个元素.另一种就是引入flag标记的思想循环遍历,用i%13来实现循环,遇到报3的元素改标记,直到只剩一一个元素的标记没改.我大致就想到这两张做法
作者: wodeheimalife    时间: 2015-5-2 08:39
好复杂的赶脚啊、。。。
作者: shenxian88    时间: 2015-5-2 15:11
kailee 发表于 2015-5-1 22:56
首先，耶稣有15个弟子吗？呵呵
其次，楼主理解有误啊，报数应该是循环的（15个门徒围成一个圈，报到最后的 ...

大神啊，拜服
作者: ydy96315    时间: 2015-5-3 06:01
好难好难～～
作者: 卖报的小画家    时间: 2015-5-16 12:21
网上可以找到的



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