PHP實現約瑟夫環問題的方法分析

2024-05-05 00:01:21

字體：大中小

來源：轉載

供稿：網友

本文實例講述了PHP實現約瑟夫環問題的方法。分享給大家供大家參考，具體如下：

一、概述

先來看看網上比較常見的約瑟夫環問題描述：約瑟夫環（約瑟夫問題）是一個數學的應用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重復下去，直到圓桌周圍的人全部出列。通常解決這類問題時我們把編號從0~n-1，最后結果+1即為原問題的解。

二、實現代碼

1. 循環

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);

運行結果：

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

2. 遞歸

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);

運行結果：