黑马程序员技术交流社区

标题: 约瑟夫环经典算法个人剖析 [打印本页]

---

作者: shicuf    时间: 2015-1-7 02:00
标题: 约瑟夫环经典算法个人剖析


班级群有人发了一个约瑟夫环的经典算法，超级简单，没人能给出解释，经过几小时熬战，整理出解题思路，现将问题分析如下，若有错误请指正！
问题描述：耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛 徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3......,凡是报到“3”就 退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
解析：为了方便推理，现把题目改为编号为1，2，3...n的n个人，报数到m则出列。
        （1）.从编号为1的人开始报数，第一个要出列的编号应该是m，考虑到环无越界，所以第一个出列的准确表达应该是m%n，令k = m%n（此处无任何逻辑意义，只是为了方便描述）。
        （2）.接下来是问题的关键，m出列之后，从编号为m+1的人开始重新组成了一个新的约瑟夫环，编号为m+1，m+2，…，n，0，1，…，m-1,此时的总人数变为n-1。因为当前问题变为n-1个人报数，报数为m的人出列。
        （3）.假设原始问题的叛徒编号为x’，第二步的叛徒编号为x,则第（2）步中所得到的n-1个人的叛徒编号与那个人的叛徒编号的对应关系应是x’ = x+k，考虑到环无越界的问题，所以准确表达应该为(x+k)%n。
        （4）.由第一步的k = m%n，带入第三步的结果，可得x’ = (x + m%n)%n = (x + m)%n。
        综上四步分析，得到递推关系，如想知道那个人时的叛徒编号，需要知道n-1个人时的叛徒编号，以此类推，需要知道2个人时的叛徒编号（为什么从2开始，应该不用解释了吧。），两个人的情况即为初始条。加入初始条件，重新整合递推公式为x = (x + m - 1) % n + 1。倒推，即可得到最终答案。

代码如下：
- (NSInteger)traitorIndex: (NSInteger)totalNum with: (NSInteger)maxValue
{
    // totalNum和maxValue必须是正整数
    NSAssert((totalNum > 0 && maxValue > 0), @"输入参数必须为正整数！")
    int i = 0;
    NSInteger traitorIndex = 1;
   
    for (i = 2; i <= totalNum; i++) {
        traitorIndex = (traitorIndex + maxValue - 1) % i + 1;
    }
   
    return traitorIndex;
}

---

作者: 郭文飞    时间: 2015-1-7 07:48
这个 我刚好不会 谢谢分享

---

作者: 张文文    时间: 2015-1-7 08:27
有质量，群里很少有这种好帖子了，谢谢分享。

---

作者: 邓明    时间: 2015-1-7 09:34
"需要知道2个人时的叛徒编号（为什么从2开始，应该不用解释了吧。），两个人的情况即为初始条件，且此时叛徒编号为2。"
为什么那么确定叛徒编号一定是2而不是1？

---

作者: shicuf    时间: 2015-1-7 10:00

邓明 发表于 2015-1-7 09:34
"需要知道2个人时的叛徒编号（为什么从2开始，应该不用解释了吧。），两个人的情况即为初始条件，且此时叛 ...

笔误，谢谢提醒！

---

作者: zx413331474    时间: 2015-1-7 11:34
大神，那个不是从2开始，是从（报数-1）开始的，如果报道三退出就是2，如果报到4退出就是3

---

作者: shicuf    时间: 2015-1-7 17:27

zx413331474 发表于 2015-1-7 11:34
大神，那个不是从2开始，是从（报数-1）开始的，如果报道三退出就是2，如果报到4退出就是3 ...

不明白，详细说说！

---

作者: 浅听    时间: 2015-1-7 19:29
大神啊，好厉害

---

作者: 我的速度    时间: 2015-1-7 23:28
学习了 T

---

作者: shicuf    时间: 2015-1-7 23:36

张文文 发表于 2015-1-7 08:27
有质量，群里很少有这种好帖子了，谢谢分享。

费工夫的事，其实我也不想写！:Q

---

作者: 张传宾    时间: 2015-1-7 23:51
受教了！

---

作者: shicuf    时间: 2015-1-8 00:26

张传宾 发表于 2015-1-7 23:51
受教了！

今晚我们在群里有讨论了一晚上，发现还有很多细节当时我并没有说清楚。在这就大题看个思想吧，推理说实话不是很严谨。

---

作者: frozen    时间: 2015-1-8 08:44
#include <stdio.h>
int count = 1;                        //用于循环：判定当前的人所报的数是否为3的倍数

int main()
{
        int i,j = 15;                //i 用于数据循环  //j 记录人数
        int a[15];

        for(i = 0; i<j;i++)  // 为每个人赋值  1   目的是判定出去的人  a[i] = 0
                a[i] = 1;

        // 循环方式为i  0~15  环形循环，结束条件j==1,即只剩一人

       
        for(i = 0; j>1 ;i++)  
        {
                if(i>14)                        // i大于数据界限,从零重新开始
                        i -= 15;
                if(a[i])                        //  a[i]!=0 ,则a[i]继续参与判定
                {
                       
                        if(count%3==0)        // 若报数为3的倍数  
                        {
                                a[i] =0;        //使他下一轮不参与判定
                                j--;                //判定人数-1
                        }
                count++;                        //报数+1
                }
       
        }

        //只有叛徒的a[i]值任然为1，若在数组中的位置i,则他的真实位置是i+1
        for(i=0;i<15;i++)
                if(a[i])
                        printf("叛徒是%d\n",i+1);

        return 0;
}

---

作者: frozen    时间: 2015-1-8 08:45
希望多多指点~~

---

作者: shicuf    时间: 2015-1-8 10:04

frozen 发表于 2015-1-8 08:44
#include
int count = 1;                        //用于循环：判定当前的人所报的数是否为3的倍数

普通方法，不是最优！

---

作者: frozen    时间: 2015-1-8 10:30
#include <stdio.h>
#include<malloc.h>
#define LEN sizeof(struct Defect)        // 计算结构体大小
struct Defect                                                // 定义叛徒结构体
{
        int number;                                                // 为每个人自己的号码牌
        struct Defect *next;                        // 指针，下面用它链接形成环体
};
void def(int n,int m)                                // 传入人数n和报数为m时退出
{
        int i = 2,count = 2;                        //i 记录人数，count记录报数
        struct Defect *head,*p,*q;                // 设置三个结构体指针
        q = head= (struct Defect *)malloc(LEN);                // 为第一个人申请结构体
        head->number = 1;                                // 定义第一个结构体的号码为1
        while(i<=n)                                                // 用循环申请n个人的结构体，并为每个人的号码赋值
        {
                p = (struct Defect *)malloc(LEN);        // 申请
                p->number = i++;                                        //赋值
                q->next = p;                                                //链接
                q = p;                                                                //定位
        }
        i = n;                                                                        //记录当前人数
        p->next = head;                                                        //最后的人和第一个人链接
        q = head;                                                                ////指定开始位置，由于设定为一个换   需要的话可以设定任意位置为开始位置
       
        while(i>1)                                                                //人数大于1执行循环
        {        p = q->next;                                                //p指向下一个人
                if(count%m == 0)                                        //如果报数为m的倍数
                {
                        q->next = p->next;                                //删除当前的结构体
                        p->next = 0;
                        i--;                                                        //人数减一
                }
                else
                        q = p;                                                        //不满足条件，移动判定人
        count++;                                                                //报数加1
        if(count>3)                                                                //报数大于三时，换为1  其实可以没有这个判定，为了题目设计的123,123,123~~
                count = 1;
        }
       
        printf("%d\n",q->number);                                //输出剩下的那个人


}
int main()
{
        int n,m;                                                                //设置人数，和报数退出条件
        printf("请输入总人数:\n");
        scanf("%d",&n);
        if(n<2)
        {       
                printf("游戏无意义！！");
                return 0;
        }       
        printf("请输入退出者的报数：\n 提示：若为1，则失去游戏的意义\n");
        scanf("%d",&m);
        if(n<2)
        {       
                printf("游戏无意义！！");
                return 0;
        }       
        def(n,m);
        return 0;
}

---

作者: frozen    时间: 2015-1-8 10:33
帮我看看这个。有的注释超出界限了，编译前 把注释调一下

---

作者: shicuf    时间: 2015-1-8 11:35

frozen 发表于 2015-1-8 10:33
帮我看看这个。有的注释超出界限了，编译前 把注释调一下

497796601,加一下这个QQ

---

作者: haojuncong    时间: 2015-1-12 09:54
。。。这个是我基础测试的第十题。。。

---

作者: shicuf    时间: 2015-1-13 00:08

haojuncong 发表于 2015-1-12 09:54
。。。这个是我基础测试的第十题。。。

搞明白没有呢？

---

作者: shicuf    时间: 2015-1-14 21:52
呵呵，多逛论坛

---

作者: liu1170486003    时间: 2015-1-16 00:35
其实我也很有意向仔细探究一下约瑟夫环的，将来我会把约瑟夫环写进博客。但是现在要专心准备流程。

---

作者: shicuf    时间: 2015-1-17 00:38

liu1170486003 发表于 2015-1-16 00:35
其实我也很有意向仔细探究一下约瑟夫环的，将来我会把约瑟夫环写进博客。但是现在要专心准备流程。 ...

期待你突破时间复杂度的极限！

---

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

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