黑马程序员技术交流社区

标题: 我脑袋想破了，C编程题求解答？（仅使用c语言视频中所学... [打印本页]
作者: 无尽可能    时间: 2014-5-22 14:17
标题: 我脑袋想破了，C编程题求解答？（仅使用c语言视频中所学...
题目： 耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（用C语言）
备注：
c语言的视频我已经看完了，仅用视频中的c语言知识我实在想不出来答案，
网上我已经搜到过不少答案，可那些用的算法和方法我都看不懂。
要求如下：
1，一定要写好注释，要能看懂每一步
作者: 欧翔    时间: 2014-5-22 14:52
本帖最后由 欧翔 于 2014-5-22 17:52 编辑

大概这样吧
  1. #include<stdio.h>

  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 17:25
欧翔 发表于 2014-5-22 14:52
大概这样吧

大哥，你运行后的结果是什么？
我的这边怎么是这样？
出卖耶稣的叛徒的序号是:124578101112131415
作者: 欧翔    时间: 2014-5-22 17:53
本帖最后由 欧翔 于 2014-5-22 17:55 编辑
无尽可能 发表于 2014-5-22 17:25
大哥，你运行后的结果是什么？
我的这边怎么是这样？
出卖耶稣的叛徒的序号是:124578101112131415 ...

之前想改成for语句后面不想改忘记删了，现在可以了，但是我的:'(我交上去了
作者: 无尽可能    时间: 2014-5-22 19:41
本帖最后由 无尽可能 于 2014-5-22 19:49 编辑
欧翔 发表于 2014-5-22 17:53
之前想改成for语句后面不想改忘记删了，现在可以了，但是我的我交上去了 ...

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


作者: 董月峰    时间: 2014-5-23 23:07
这题是中学算法竞赛题，多想想就行，不会也不必太纠结
作者: 完美世界    时间: 2014-6-24 22:09
虽然时间不赶趟，我也做了下你看看。

#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++;
        }
    }
}
作者: 秋水红林    时间: 2014-9-19 18:47
我只能说，这道题我也遇到了，晕了，感觉就靠c的基础，做不出来
作者: lanwen963    时间: 2014-11-1 14:00
取余循环真是妙用,顶起!谢谢指导
作者: zsling    时间: 2014-12-16 16:21
取余循环真厉害，还有i的计数的运用，也好巧妙啊
作者: 墓笙    时间: 2014-12-18 16:35
看到这个题感觉不难，但是自己编起来才发现没有头绪！！！！！！！！！！！！！！！收下了
作者: 墓笙    时间: 2014-12-25 14:54
董月峰 发表于 2014-5-23 23:07
这题是中学算法竞赛题，多想想就行，不会也不必太纠结

现在回复你，不会很严重，我听了你的，然后面试编程就是这个题。。。。。。。。。。。。。
作者: 13hoop    时间: 2015-1-25 16:49
这是典型的的约瑟夫问题
楼主初学
建议采用模拟的方式
按照题意模拟就是
作者: Lbabywei1988    时间: 2015-3-12 22:04
我能说我也一样吗！！！我实在是做不出来！看到俺都看不懂！！！:'(
作者: whymerain    时间: 2015-3-13 21:52
  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.    

  35. }
复制代码

约瑟夫环的问题。如果采用模拟环依次的方法，重点是如何开始新的一圈循环，代码的靠后部分 if (i == M)  i = 0;使得报号一遍后重新报号。约瑟夫环的问题，还可以采用递归公式，代码简洁，需要能够推到公式。下面是模拟的方法。
作者: moresurui0308    时间: 2015-4-1 17:37
我想知道最后的答案是多少。。
作者: 葛先生    时间: 2015-4-12 22:59
moresurui0308 发表于 2015-4-1 17:37
我想知道最后的答案是多少。。

最后的答案是5
作者: 葛先生    时间: 2015-4-13 23:21
#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);

   
   }
}
作者: 15578797612    时间: 2015-5-29 15:08
  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. }
复制代码
作者: 马贺飞    时间: 2015-8-11 13:58
先标记一下
作者: tangbinbin    时间: 2015-8-16 17:58
这个问题有点难额，，，
作者: 丿白衬衫    时间: 2015-9-22 20:00
这个题好难



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