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

Eil.tea 发表于 2015-7-28 12:16
由于现在在公司，就用C#写了一个模拟的双向链表的代码，回头用C再写一遍。这里的编号是从0开始的，最后 ...

完全不明白链表

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. 
   
7. namespace 约瑟夫杀人问题
   
8. {
   
9.     class Program
   
10.     {
    
11.         static void Main(string[] args)
    
12.         {
    
13.             int[,] p=new int[15,3];
    
14.             int N=13,q=3;//N个人，喊道q的被杀死
    
15.          
    
16.             for (int i = 0; i < 13; i++)
    
17.             {
    
18.                 p[i,0] = i - 1;
    
19.                 p[i,1] = i;
    
20.                 p[i,2] = i + 1;
    
21.             }
    
22.             p[0,0] = N - 1;
    
23.             p[N - 1,2] = 0;
    
24.             //链表的初始化
    
25. 
    
26.             int num= 0;//当前喊的人的编号
    
27.             for (int i = 1; i < 13; i++)
    
28.             {
    
29.                 for (int j = 1; j < q; j++)
    
30.                 {
    
31.                     num = p[num,2];
    
32.                 }
    
33.                 p[p[num,0],2] = p[num,2];
    
34.                 p[p[num,2],0] = p[num,0];
    
35.                 num = p[num, 2];
    
36.             }
    
37.             //最后一个人就是活着的
    
38.             Console.WriteLine("The num is "+(num+1));
    
39.             Console.ReadKey();
    
40.         }
    
41.     }
    
42. }
    

复制代码

由于现在在公司，就用C#写了一个模拟的双向链表的代码，回头用C再写一遍。这里的编号是从0开始的，最后的num需要+1，有什么错误请指教

再补充一点，关于数组和链表的实现效率。因为用数组存储的话，没循环一次，都需要枚举每个数组的值，（包括已经死的人），假设100个人，喊道99的死。那么剩下两个人的时候，两个人报数，会检索整个数组50次，100*50=5000次。而使用双向链表剩下的两个人的下一个地址指向对方，这样只需要检索100次就可以了，大大提高的代码效率。

Eil.tea 发表于 2015-7-28 09:01
两个代码都是用的数组做的循环，链表的话，每个元素有三个值，第一个指向前边的元素的地址，第二个，指向 ...

上面两个的思路是一样的，链表的话有没有详细的代码啊，注释多多的:)看不太懂

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 就可以了

感觉有点难

Zeus-S 发表于 2015-7-27 22:26

这个也是链表吗，都看不太懂，明天研究下

wowthe1st 发表于 2015-7-27 22:17

明天有时间学习下

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

复制代码

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. }
    

复制代码

还真是如你所说的，我没有考虑到是个环

13号额，要实现的代码么～～

hccgk 发表于 2015-7-27 21:11
数组就可以了，1...15然后去掉对3取余数的位置，然后把这些存到一个新的数组里，然后再做相同的，最后存储 ...

。。。你去试试，我实践过，没有你想的那么简单，他是环的，15个人结束之后是从16开始的啊，并且你还要输出他的最开始的位置，并且循环也不好实现，，，

数组就可以了，1...15然后去掉对3取余数的位置，然后把这些存到一个新的数组里，然后再做相同的，最后存储的元素就是了