黑马程序员技术交流社区

标题: 基础测试中用排除法找出环形数组中的目标数字的问题。 [打印本页]
作者: gxppq    时间: 2014-12-18 11:22
标题: 基础测试中用排除法找出环形数组中的目标数字的问题。
这是我的基础测试中的一道题目：耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（C语言）
    这道题困扰了我半个多小时。最后用计数器把它做出来了。但我感觉这个方法有些麻烦，应该还有更好的方法。麻烦那位大神给出一个好的简便的方向。多谢了~
  1. #include <stdio.h>

  3. int main()
  4. {
  5.         int i,j,n,m,temp,step;
  6.         printf("Please input the number of person(within 100):n=");
  7.         scanf("%d",&n);          /*Input the number of person.*/
  8.         printf("Output the number of person:");
  9.         int a[101];
  10.         for(i=1;i<=n;i++){a[i]=i;printf("%d ",a[i]);}
  11.         temp=0;               /*'temp' is a counter of the figure person uttering.*/
  12.         step=0;               /*'step' counter the number of person which don't betray Jesus.*/
  13.         m=0;                  //'m' is a counter of circle.
  14.         while(step<n-1)
  15.         {
  16.                 for(i=1;i<=n;i++)
  17.                 {
  18.                         if(a[i]!=0)
  19.                         {
  20.                                 temp=temp+1;
  21.                                 if(temp==3)
  22.                                 {a[i]=0;
  23.                                 temp=0;}
  24.                         }
  25.                 }
  26.                 step=0;
  27.                 m++;printf("\nThe leaving persons after %dth circle:",m);
  28.                 for(i=1;i<=n;i++)
  29.                 {
  30.                         if(a[i]==0)step++;
  31.                         else {j=i;printf("%d ",a[i]);}
  32.                 }
  33.         }
  34.         printf("\nThe person who betray Jesus is %d.\n",a[j]);
  35.         return 0;
  36. }
复制代码
作者: 。烊了    时间: 2014-12-18 12:43
本帖最后由 。烊了 于 2014-12-18 12:45 编辑

int i, s = 0;
   
    for (i = 2; i <= 15; i++)
    {
        s = (s + 3) % i;
    }
    printf("叛徒是 %d\n", s + 1);


即可
作者: 从今以后    时间: 2014-12-18 13:39
思路基本都这样= =楼上那种太过牛逼
  1. #import <Foundation/Foundation.h>

  3. #define NUM 15
  4. int main(int argc, const char * argv[]) {
  5.     @autoreleasepool {
  6.         
  7.         int man[NUM];
  8.         for (int i = 0; i < NUM; ++i)
  9.             man[i] = i + 1;
  10.         
  11.         int manNum = NUM;
  12.         int count = 0;
  13.         for (int i = 0; manNum > 1; ++i) {
  14.             
  15.             if (man[i])
  16.                 if (++count % 3 == 0) {
  17.                     man[i] = 0;
  18.                     --manNum;
  19.                 }
  20.             
  21.             if (i == NUM - 1)
  22.                 i = -1;
  23.         }
  24.         
  25.         int j = -1;
  26.         while (!man[++j]) ;
  27.         printf("叛徒是第%i个门徒\n", man[j]);
  28.     }
  29.     return 0;
  30. }
复制代码
作者: computer    时间: 2014-12-18 14:08
。烊了 发表于 2014-12-18 12:43
int i, s = 0;
   
    for (i = 2; i

大师，您简直是神人！:funk:
作者: weizhang00    时间: 2014-12-18 14:29
。烊了 发表于 2014-12-18 12:43
int i, s = 0;
   
    for (i = 2; i

求教思路:(
作者: wangxiaoit    时间: 2014-12-18 15:34
这貌似是 约瑟夫环  算法。。
作者: gxppq    时间: 2014-12-19 21:41
刚刚按照6楼说的去查了一下，这个题考的确实是约瑟夫环。在百度百科上也能找到约瑟夫环算法各种编程语言的实现代码，基本思路有递归，也有像我和三楼的那种思路。但2楼的思路我确实看不懂。2楼能给详细解释一下你的思路吗？那怕加一下注释也好呀。



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