题目： 耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（用C语言）
备注：
c语言的视频我已经看完了，仅用视频中的c语言知识我实在想不出来答案，
网上我已经搜到过不少答案，可那些用的算法和方法我都看不懂。
要求如下：
1，一定要写好注释，要能看懂每一步

大概这样吧

1. #include<stdio.h>
   
2. 
   
3. int main(){
   
4. //    15门徒的标记数组
   
5.     int person[15]={0};
   
6. //    剩余人数
   
7.         int n=15;
   
8.     //    方便用余数循环遍历数组，所以从15开始
   
9.         int j=15;
   
10.         int i=1;
    
11.         while(n>1）{
    
12. //            当标记为0且报数没有到3，继续下一人报数
    
13.             if(person[j%15]==0&&i!=3)
    
14.                 i++;
    
15. //            当标记为0且报数为3时，把报数的人赋值1为标记，重置报数，剩余人数减1
    
16.             else if(person[j%15]==0&&i==3){
    
17.                 person[j%15]=1;
    
18.                 i=1;
    
19.                 n--;
    
20.             }
    
21. //            遍历标记数组
    
22.                 j++;
    
23.         }
    
24.         printf("出卖耶稣的叛徒的序号是:");
    
25.         for(i=0;i<15;i++)
    
26.             if(person[i]==0)
    
27.                 printf("%d",i+1);
    
28.    
    
29.            return 0;
    
30. }

复制代码

欧翔 发表于 2014-5-22 14:52
大概这样吧

大哥，你运行后的结果是什么？
我的这边怎么是这样？
出卖耶稣的叛徒的序号是:124578101112131415

无尽可能 发表于 2014-5-22 17:25
大哥，你运行后的结果是什么？
我的这边怎么是这样？
出卖耶稣的叛徒的序号是:124578101112131415 ...

之前想改成for语句后面不想改忘记删了，现在可以了，但是我的:'(我交上去了

欧翔 发表于 2014-5-22 17:53
之前想改成for语句后面不想改忘记删了，现在可以了，但是我的我交上去了 ...

{:3_46:}，没关系的，一道题不影响，{:3_57:}，现在是对的！，我后用了其它的方法，最开始没弄太懂你的求余循环，现在发现求余在这里是妙用啊，嘿嘿。

这题是中学算法竞赛题，多想想就行，不会也不必太纠结

虽然时间不赶趟，我也做了下你看看。

#include <stdio.h>
struct Person
{
    int s;//存储这个人报出得数
    int count;//存储这个人得序号
    int k;//用作标记，当no=1时，说明这个人离开了圈子，用不再报数
}per[15]={0};
int main()
{
    int y=0;
    for (int i=0; i<15; i++)//分配每个人得序号
    {
        per[i].count=i+1;
    }
    for (int i=0,out=0; ; i++)//变量out存储离开圈子的人数
    {
        if (i==15)
        {
            i=0;
        }
        if(per[i].k!=1)//没有被标记离开的人报数
        {
            y++;
            per[i].s=y;
            if (out==14)//当离开了14个人，剩下的最后一个人
            {
                printf("这个人得序号是%d\n",per[i].count);
                break;
            }
        }
        if (per[i].s%3==0&&(per[i].k!=1))//标记离开的人
        {
            per[i].k=1;
            out++;
        }
    }
}

我只能说，这道题我也遇到了，晕了，感觉就靠c的基础，做不出来

取余循环真是妙用,顶起!谢谢指导

取余循环真厉害，还有i的计数的运用，也好巧妙啊

看到这个题感觉不难，但是自己编起来才发现没有头绪！！！！！！！！！！！！！！！收下了

董月峰 发表于 2014-5-23 23:07
这题是中学算法竞赛题，多想想就行，不会也不必太纠结

现在回复你，不会很严重，我听了你的，然后面试编程就是这个题。。。。。。。。。。。。。

这是典型的的约瑟夫问题
楼主初学
建议采用模拟的方式
按照题意模拟就是

我能说我也一样吗！！！我实在是做不出来！看到俺都看不懂！！！:'(

1. #include <stdio.h>
   
2. #define M 15   //M表示人数，N表示报号退出的数字
   
3. #define N 3
   
4. int main()
   
5. {
   
6.         int  str[M];
   
7.         for(int a = 0;a<M;a++)   //for循环赋值
   
8.     {
   
9.         str[a]=a+1;
   
10.     }
    
11.    
    
12.     int number = M,count = 0,i =0;
    
13.     while (number > 1)  //直到只剩一人退出循环
    
14.         {
    
15.         if (str[i] != 0)  count++;
    
16.                
    
17.         if (count == 3) {
    
18.             str[i] = 0;//退出圈子的人数值改为0
    
19.             count = 0;//count重新赋值为0，重新报号
    
20.             number--;//人数减1
    
21.         }
    
22.         i++;
    
23.         if (i == M)  i = 0; //M人报号一遍后重新报号
    
24.         
    
25.     }
    
26.    
    
27.     for (int i = 0; i< 13; i ++)
    
28.     {
    
29.         if (str[i] > 0) printf("出卖耶稣叛徒的序号为:%d\n",str[i]);
    
30.   
    
31.      }
    
32.         return 0;
    
33.    
    
34. 
    
35. }

复制代码

约瑟夫环的问题。如果采用模拟环依次的方法，重点是如何开始新的一圈循环，代码的靠后部分 if (i == M)  i = 0;使得报号一遍后重新报号。约瑟夫环的问题，还可以采用递归公式，代码简洁，需要能够推到公式。下面是模拟的方法。

我想知道最后的答案是多少。。

moresurui0308 发表于 2015-4-1 17:37
我想知道最后的答案是多少。。

最后的答案是5

#include <stdio.h>

int main()
{
  int a[15];  //定义数组
  for(int i=0;i<15;i++)  //给数组成员编号复值；
  {
    a[i]=i+1;
  }
  
prinf("出卖耶稣的是%d\n",test(sizeof(a)));
return 0;
}
int test(int a)  //利用递归。
{
int sum=15; //剩余人数。
int num=a;   //需要报数的人数。
int t=1;   //第一个人报的数


  for(int i=t;i<num+1;i++) //int i=t主要是后面如果最后一个人报数不是3时，第一个人接着报数的号数为t。
   {
   if(num==1);//只剩下一个人时，结果出来了。
   {  
    return a[i];  
   }      
   
   if(a[i]==num) //遍历到最后一个人，
   {
    if(i!=3)  //圆圈循环报数，使下次循环第一个人报数接着前面一个人的数报。
    {
      t==i+1;
    }
    int test(num=count);

   
   }
}

1. #include<stdio.h>
   
2. int main(void)
   
3. {
   
4.         char s[100];
   
5.         int i ;
   
6.         int k = 1 ;
   
7.         int h = 0 ;
   
8.         int n = 15 ;
   
9.         int j;
   
10.         s[0]='A';
    
11.        
    
12.         for(i=1;i<15;i++)
    
13.         {
    
14.                 s[i] = s[i-1]+1;
    
15.         }
    
16.         s[15]='\0';
    
17.        
    
18.         while(s[1]!='\0')
    
19.         {
    
20.                 for(i=0;i<3;i++)
    
21.                 {
    
22.                         if(k==3)
    
23.                         {
    
24.                                 j = h;
    
25.                                 while(s[j]!='\0')
    
26.                                 {
    
27.                                         s[j] = s[j+1];
    
28.                                         j++;
    
29.                                 }
    
30.                                 k=1;
    
31.                                 if(h+1==n)
    
32.                                 {
    
33.                                         k=k-1;
    
34.                                        
    
35.                                 }
    
36.                                 n=n-1;
    
37.                 //用来打印每次删除完的数组元素，答案是“E”
    
38.                                 printf("%s\n",s);
    
39.                                
    
40.                         }
    
41.                         k++;
    
42.                         h++;
    
43.                         if(h>n-1)
    
44.                         {
    
45.                                 h=0;
    
46.                         }
    
47.                        
    
48.                 }
    
49.                
    
50.         }
    
51.         printf("%c",s[0]);
    
52.         return 0 ;
    
53. }

复制代码

先标记一下