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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© shicuf 中级黑马   /  2015-1-7 02:00  /  3742 人查看  /  25 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 shicuf 于 2015-1-7 10:11 编辑

班级群有人发了一个约瑟夫环的经典算法,超级简单,没人能给出解释,经过几小时熬战,整理出解题思路,现将问题分析如下,若有错误请指正!
问题描述:耶稣有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;
}

点评

就一个问题,你有把1--15在纸上写出来验算吗?  发表于 2015-2-3 14:03
啊,刚交的测试题,这道题没做。哭啊  发表于 2015-1-14 19:13

25 个回复

倒序浏览
这个 我刚好不会 谢谢分享
回复 使用道具 举报
有质量,群里很少有这种好帖子了,谢谢分享。
回复 使用道具 举报
"需要知道2个人时的叛徒编号(为什么从2开始,应该不用解释了吧。),两个人的情况即为初始条件,且此时叛徒编号为2。"
为什么那么确定叛徒编号一定是2而不是1?
回复 使用道具 举报
本帖最后由 shicuf 于 2015-1-7 10:09 编辑
邓明 发表于 2015-1-7 09:34
"需要知道2个人时的叛徒编号(为什么从2开始,应该不用解释了吧。),两个人的情况即为初始条件,且此时叛 ...

笔误,谢谢提醒!
回复 使用道具 举报
大神,那个不是从2开始,是从(报数-1)开始的,如果报道三退出就是2,如果报到4退出就是3
回复 使用道具 举报
zx413331474 发表于 2015-1-7 11:34
大神,那个不是从2开始,是从(报数-1)开始的,如果报道三退出就是2,如果报到4退出就是3 ...

不明白,详细说说!
回复 使用道具 举报
大神啊,好厉害
回复 使用道具 举报
学习了 T
回复 使用道具 举报
张文文 发表于 2015-1-7 08:27
有质量,群里很少有这种好帖子了,谢谢分享。

费工夫的事,其实我也不想写!:Q
回复 使用道具 举报
受教了!
回复 使用道具 举报

今晚我们在群里有讨论了一晚上,发现还有很多细节当时我并没有说清楚。在这就大题看个思想吧,推理说实话不是很严谨。
回复 使用道具 举报
#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;
}

点评

你的是对的  发表于 2015-2-3 14:06
回复 使用道具 举报
希望多多指点~~
回复 使用道具 举报
frozen 发表于 2015-1-8 08:44
#include
int count = 1;                        //用于循环:判定当前的人所报的数是否为3的倍数

普通方法,不是最优!
回复 使用道具 举报
#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
帮我看看这个。有的注释超出界限了,编译前 把注释调一下

497796601,加一下这个QQ
回复 使用道具 举报
。。。这个是我基础测试的第十题。。。
回复 使用道具 举报
haojuncong 发表于 2015-1-12 09:54
。。。这个是我基础测试的第十题。。。

搞明白没有呢?
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马