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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© xiaochongzi 中级黑马   /  2015-7-27 20:47  /  1198 人查看  /  14 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

这是我的基础测试的最后一道题,完全算不出,好像都用的链表内容,不太明白,求解
耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:13人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,凡是报到“3”就退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。

14 个回复

倒序浏览
数组就可以了,1...15然后去掉对3取余数的位置,然后把这些存到一个新的数组里,然后再做相同的,最后存储的元素就是了
回复 使用道具 举报
hccgk 发表于 2015-7-27 21:11
数组就可以了,1...15然后去掉对3取余数的位置,然后把这些存到一个新的数组里,然后再做相同的,最后存储 ...

。。。你去试试,我实践过,没有你想的那么简单,他是环的,15个人结束之后是从16开始的啊,并且你还要输出他的最开始的位置,并且循环也不好实现,,,
回复 使用道具 举报
13号额,要实现的代码么~~
回复 使用道具 举报
还真是如你所说的,我没有考虑到是个环
回复 使用道具 举报
  1. #define LEN 13 //设置13个使徒
  2. int main()
  3. {
  4.        
  5.        
  6.         char cary[LEN]={0};//初始化为0,0为还在列,1为出列
  7.         int index,count;
  8.         for(index=0,count=0;count<3*LEN;index++)
  9.         {
  10.                 //count=3*LEN时则是已经出列了13个了,即已经全部出列,结束循环
  11.                 if(cary[index%LEN]==0)//只计算未出列的,即等于0的才计数
  12.                 {
  13.                         count++;
  14.                         if(count%3==0)//数到3出列,出列即设置值为1
  15.                                 cary[index%LEN]=1;
  16.                 }
  17.                
  18.         }
  19.         //打印最后一个出列的的下标,因为最后执行了一次index++,所以真正最后一个下标是index-1
  20.         printf("index is %d\n",(index-1)%LEN);
  21.                
  22.        
  23.         return 0;
  24. }
复制代码
回复 使用道具 举报
Zeus-S 中级黑马 2015-7-27 22:26:08
7#
  1. #define ALL_NUM 15
  2. #define OUT_NUM 3

  3. #include <stdio.h>

  4. int main(int argc, const char * argv[]) {
  5.   
  6.     int people_num = ALL_NUM,step = 0,pos;//people_num代表参与报号的人数,step表示报的号码,pos代表下标
  7.     int people[ALL_NUM];
  8.     for(pos = 0 ;pos < ALL_NUM;pos++) //for 循环把编号放进数组
  9.     {
  10.         people[pos] = pos + 1;
  11.     }
  12.     pos = 0;
  13.    
  14.     while(people_num > 0)
  15.     {
  16.         if (people[pos]) { // 编号不为0参与报号
  17.             step++;
  18.         }
  19.         if (step == OUT_NUM && people[pos]) { //报号报到3而且本身编号不为0就排除
  20.             printf("%d out\n",people[pos]);
  21.             people[pos] = 0;
  22.             people_num--;
  23.         }
  24.         pos++;
  25.         if (pos == ALL_NUM) { //下标等于13,从第一个开始重新报号
  26.             pos = 0;
  27.         }
  28.         if (step == OUT_NUM) { //报号报到3,就从1重新开始报号
  29.             step = 0;
  30.         }
  31.    
  32.     }
  33.    
  34.     return 0;
  35. }
复制代码
回复 使用道具 举报

明天有时间学习下
回复 使用道具 举报

这个也是链表吗,都看不太懂,明天研究下
回复 使用道具 举报
感觉有点难
回复 使用道具 举报
xiaochongzi 发表于 2015-7-27 22:51
这个也是链表吗,都看不太懂,明天研究下

两个代码都是用的数组做的循环,链表的话,每个元素有三个值,第一个指向前边的元素的地址,第二个,指向本身的值(自己的编码),第三个指向右边元素的地址。链表的第一个元素的第一个值指向链表最后一个元素的地址,链表的第三个元素指向第一个元素的地址,形成链表。
思想:每杀死一个人,只需要讲这个元素的前一个元素的第三个值,指向当前元素的第三个值,这个元素的第三个值的第一个值指向当前元素的第一个值,形成新的链表。
伪代码    p[p[killnum].left].right=p[killnum].left; p[p[killnum].right].left=p[killnum].right;
这样的好处是,我知道我下次数的人的编码了,因为换链中的数值都是没被杀死的人,所以报下一个的时候,只需要访问 p[kilnum].reght 就可以了
回复 使用道具 举报
Eil.tea 发表于 2015-7-28 09:01
两个代码都是用的数组做的循环,链表的话,每个元素有三个值,第一个指向前边的元素的地址,第二个,指向 ...

上面两个的思路是一样的,链表的话有没有详细的代码啊,注释多多的:)看不太懂
回复 使用道具 举报
再补充一点,关于数组和链表的实现效率。因为用数组存储的话,没循环一次,都需要枚举每个数组的值,(包括已经死的人),假设100个人,喊道99的死。那么剩下两个人的时候,两个人报数,会检索整个数组50次,100*50=5000次。而使用双向链表剩下的两个人的下一个地址指向对方,这样只需要检索100次就可以了,大大提高的代码效率。
回复 使用道具 举报
xiaochongzi 发表于 2015-7-28 11:07
上面两个的思路是一样的,链表的话有没有详细的代码啊,注释多多的看不太懂 ...
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;

  6. namespace 约瑟夫杀人问题
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             int[,] p=new int[15,3];
  13.             int N=13,q=3;//N个人,喊道q的被杀死
  14.          
  15.             for (int i = 0; i < 13; i++)
  16.             {
  17.                 p[i,0] = i - 1;
  18.                 p[i,1] = i;
  19.                 p[i,2] = i + 1;
  20.             }
  21.             p[0,0] = N - 1;
  22.             p[N - 1,2] = 0;
  23.             //链表的初始化

  24.             int num= 0;//当前喊的人的编号
  25.             for (int i = 1; i < 13; i++)
  26.             {
  27.                 for (int j = 1; j < q; j++)
  28.                 {
  29.                     num = p[num,2];
  30.                 }
  31.                 p[p[num,0],2] = p[num,2];
  32.                 p[p[num,2],0] = p[num,0];
  33.                 num = p[num, 2];
  34.             }
  35.             //最后一个人就是活着的
  36.             Console.WriteLine("The num is "+(num+1));
  37.             Console.ReadKey();
  38.         }
  39.     }
  40. }
复制代码

由于现在在公司,就用C#写了一个模拟的双向链表的代码,回头用C再写一遍。这里的编号是从0开始的,最后的num需要+1,有什么错误请指教
回复 使用道具 举报
Eil.tea 发表于 2015-7-28 12:16
由于现在在公司,就用C#写了一个模拟的双向链表的代码,回头用C再写一遍。这里的编号是从0开始的,最后 ...

完全不明白链表
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马