Chinaunix首页 | 论坛 | 博客
  • 博客访问: 243590
  • 博文数量: 253
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 3
  • 用 户 组: 普通用户
  • 注册时间: 2014-09-21 12:29
文章分类

全部博文(253)

文章存档

2014年(253)

我的朋友

分类: C/C++

2014-09-21 12:54:19

说明据说着名犹太历史学家  Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹
太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了
一个自杀方式,41个人排成一个圆圈,由第1个人  开始报数,每报数到第3人该人就必须自杀,
然后再由下一个重新报数,直到所有人都自杀身亡为止。 
 
然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排
在第16个与第31个位置,于是逃过了这场死亡游戏。 

解法约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与m个朋友不幸参
与了这个游戏,您要如何保护您与您的朋友?只要画两个圆圈就可以让自己与朋友免于死亡游
戏,这两个圆圈内圈是排列顺序,而外圈是自杀顺序,如下图所示:

使用程式来求解的话,只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到三
个无资料区就填入一个计数,直而计数达41为止,然后将阵列由索引1开始列出,就可以得知每
个位置的自杀顺序,这就是约瑟夫排列,41个人而报数3的约琴夫排列如下所示: 
14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 
22 33 13 29 23 
 
由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的
人都死光了,所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。 


代码实现

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define N 41
  4. #define M 3
  5.  
  6. int main(void) 
  7. {
  8.     int man[N] = {0};
  9.     int count = 1;
  10.     int i = 0, pos = -1;
  11.     int alive = 0;
  12.  
  13.     while(count <= N) 
  14.     {
  15.         do 
  16.         {
  17.             pos = (pos+1) % N; // 环状处理
  18.             if(man[pos] == 0)
  19.                 i++;
  20.  
  21.             if(i == M) 
  22.             { // 报数为3了
  23.                 i = 0;
  24.                 break;
  25.             }
  26.         } while(1);
  27.  
  28.         man[pos] = count;
  29.         count++;
  30.     }

  31.     printf("\n约琴夫排列:");
  32.     for(i = 0; i < N; i++)
  33.         printf("%d ", man[i]);

  34.     printf("\n\n您想要救多少人?");
  35.     scanf("%d", &alive);

  36.     printf("\nL表示这%d人要放的位置:\n", alive);
  37.     for(i = 0; i < N; i++) 
  38.     {
  39.         if(man[i] > alive) 
  40.              printf("D");
  41.         else printf("L");
  42.             if((i+1) % 5 == 0) 
  43.                  printf(" ");
  44.     }
  45.     
  46.     printf("\n");

  47.     return 0;
  48. }






阅读(361) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~