Analysis of the method of implementing Joseph's ring problem in PHP

This article describes the method of PHP to implement the Joseph ring problem. Share it for your reference, as follows:

1. Overview

Let’s first look at the description of the Joseph ring problem on the Internet: The Joseph ring (Joseph problem) is a mathematical application problem: n people (denoted by numbers 1, 2, 3...n respectively) are known to sit around a round table. The person with the number k starts to count, and the person who counts to m is out of the list; his next person starts to count from 1, and the person who counts to m is out of the list; repeat according to this rule until all the people around the round table are out of the list. Usually when solving this type of problem, we turn the number from 0~n-1, and the final result +1 is the solution to the original problem.

2. Implement code

1. Loop

function circle($arr,$idx,$k){
  for($i=0;$i<$idx;$i++){
    $tmp = array_shift($arr);
    array_push($arr,$tmp);
  }
  $j = 1;
  while(count($arr) > 0){
    $tmp = array_shift($arr);
    if($j++%$k == 0){
      echo $tmp."\n";
    }else{
      array_push($arr,$tmp);
    }
  }
}
$arr = array(1,2,3,4,5,6,7,8,9,10,11,12);
$idx = 3;
$k = 4;
circle($arr,$idx,$k);

Running results:

7 11 3 8 1 6 2 10 9 12 5 4 

2. Recursion

function circle($arr,$idx,$k){
  $len = count($arr);
  $i = 1;
  if($len == 1){
    echo $arr[0]."\n";
    return ;
  } else {
    while($i++ < $k){
      $idx++;
      $idx = $idx%$len;
    }
    echo $arr[$idx]."\n";
    array_splice($arr,$idx,1);
    circle($arr,$idx,$k);
  }
}
$arr = [1,2,3,4,5,6,7,8,9,10,11,12];
$idx = 3;
$k = 4;
circle($arr,$idx,$k);

Running results:

7 11 3 8 1 6 2 10 9 12 5 4

For more information about PHP related content, please check out the topic of this site:PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Summary of usage of php strings》、《Complete collection of PHP array (Array) operation techniques》、《Summary of common traversal algorithms and techniques for PHP"and"Summary of PHP mathematical operation skills》

I hope this article will be helpful to everyone's PHP programming.