PHP实现约瑟夫环问题的方法分析

yipeiwu_com7年前PHP代码库

本文实例讲述了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);

运行结果:

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

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

相关文章

php实现中文字符截取防乱码方法汇总

大家在自己的程序中相信都会经常用到截取字符串吧,但是往往遇到截取中文字符串的时候会遇到乱码的问题。很是让人头疼,接下来介绍两种方法防止截取中文字符串的时候出现乱码的问题。 首先第一种,自...

php实现的网络相册图片防盗链完美破解方法

本文实例讲述了php实现的网络相册图片防盗链完美破解方法。分享给大家供大家参考。具体如下: 网络相册图片防盗链破解程序 - PHP版 这个防盗链破解版可以完美破解当下比较流行的: 百度相...

数据库查询记录php 多行多列显示

复制代码 代码如下:<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.or...

递归实现php数组转xml的代码分享

PHP中将数组转为xml的需求是常见的,而且实现方法也有很多种,百度找了一下各种实现方法,但是基本是借组一些组件啥的。我就自己写了一个字符串拼组的方法,支持多维数组。仅供参考,不足之处敬...

PHP备份数据库生成SQL文件并下载的函数代码

复制代码 代码如下: <!?php /****** 备份数据库结构 ******/ /* 函数名称:table2sql() 函数功能:把表的结构转换成为SQL 函数参数:$tabl...