php 试着解决约瑟夫问题，各位大牛还有更好的处理方法么？

0 0

php 试着解决约瑟夫问题，各位大牛还有更好的处理方法么？

问题描述：有以下故事由来
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
我自己模拟了一个10人，逢3死亡的结果，有没有更好的算法来解决呢

  /*试着用数组解决约瑟夫问题*/
  

  $a=10;//总人数
  

  $arr=array(); //10人数组
  

  for ($i=1;$i<=10;$i++){
  

  $arr[]=$i;
  

  }
  

  $num=3; //当数到3时个人死亡，数从1开始
  

  

  $c=0;//当前的数
  

  $b=0;//数组的键
  

  

  while (($count=count($arr))>1){
  

  $c++;
  

  if(!isset($arr[$b])){
  

  $b++;
  

  }
  

  if($b>=10){
  

  $b=0;
  

  }
  

  if($c==$num){
  

  unset($arr[$b]);
  

  $c=0;
  

  }
  

  $b++;
  

  if($b>=10){
  

  $b=0;
  

  }
  

  }
  

  var_dump($arr);

趣味 php

11 years, 7 months ago

BE丨LA

BE丨LA 11 years, 7 months ago

  function king($n,$m) {
  

  //模拟建立一个连续数组
  

  $arr = range(1,$n);
  

  $i = 0;
  

  while(count($arr) > 1) {
  

  $i += 1; // 开始查数
  

  //循环列出最前面的人
  

  $head = array_shift($arr);
  

  if($i % $m != 0) {
  

  // 如果没数到m或m的倍数,则把人放回尾部去. 否则就干掉
  

  array_push($monkey,$head);
  

  }
  

  }
  

  return $arr[0];
  

  }
  

  var_dump(10,3);

查找资料看到一个更牛逼的

  function joseph($n,$m) {
  

  $r = 0;
  

  for ($i=2; $i <= $n; $i++) {
  

  $r = ($r+$m)%$i;
  

  }
  

  return $r+1;
  

  }
  

  

  var_dump(joseph(10,3));

answered 11 years, 7 months ago

第一排抱树

第一排抱树 answered 11 years, 7 months ago