约瑟夫环--下篇

December 22 , 2015

@(算法)[数据结构, 基本算法, 排序问题]

       上面一篇说到了约瑟夫环问题的来源和基本的逻辑处理,本篇就说说怎么在代码中实现这个功能。

       最终结果访问:http://activity.500efuma.com/

约瑟夫环实现(PHP)

       这里我直接在博客框架中另起一个新的模块进行编写,所以会用到ThinkPHP的有关函数。

  • 定义一个新的控制器,并且设置一些初始化的数据

<?php
namespace Activity\Controller;
use Think\Controller;

class IndexController extends Controller {

    private $user_arr;
    private $K;
    private $M;
    private $N;

    //数据初始化
    public function _initialize(){
        $this->user_arr = array('小百合','小龙华','小六花','小假肢','小CC','小小野','小魔王','小透华');
        $this->N = count($this->user_arr);
        $this->K = rand(1, $this->N);
        $this->M = rand(1, $this->N);
    }
}

  • 根据随机的K,M将初始数据进行新的排列

这里使用php的array_splice函数能够很方便的将数组的前后进行替换或者删除 注意array_splice的返回是提出的数据,不拿返回直接拿参数结果,则是运行后的返回值。 至于参数的传递运算这里需要用到一些很简单的数学算法。 方法my_sort这里使用的递归算法。

public function christmas(){
    $temp = array_splice($this->user_arr, $this->K-1,$this->N-($this->K-1));
    array_splice($this->user_arr, 0, 0, $temp);
    $start = $this->user_arr;
    $result = $this->my_sort($this->user_arr);
}

  • 递归算法的实现

$i = $this->M % count($a);这个算法很关键,要注意的是出现余数为0的情况就不需要进行重新的排序了,因为本来被踢出去的人就在最后一个。

private function my_sort($a,$new = array()){
    if (count($a) > 1){
        $i = $this->M % count($a);//余数即踢出的第i个
        $out = array_splice($a, $i-1 ,1);
        array_push($new, $out[0]);
        //重组下
        if ($i != 0){
            $last = array_splice($a, $i-1 ,count($a)-($i-1));
            array_splice($a, 0 ,0 ,$last);
        }
        return $this->my_sort($a, $new);
    }else {
        array_push($new, $a[0]);
        return $new;
    }
}

  • 最后再把生成的数据处理下保存到数据库中就OK了

christmas方法中添加ThinkPHP的模型处理方法,最后的代码为:

public function christmas(){
    $temp = array_splice($this->user_arr, $this->K-1,$this->N-($this->K-1));
    array_splice($this->user_arr, 0, 0, $temp);
    $start = $this->user_arr;
    $result = $this->my_sort($this->user_arr);
    //data数据生成
    $data['k'] = $this->K;
    $data['m'] = $this->M;
    $data['start'] = $start;
    $data['result'] = $result;
    //DB操作记录数据
    $christmas_model = M('activity_christmas');
    $save['data'] = json_encode($data);
    $save['ctm'] = date('Y-m-d H:i:s',time());
    $christmas_model->add($save);
}

定时任务

       要求上说道要定时执行,我这里的实现方式为最常用的linux crontab任务。关于crontab不知道的同学可以自行百度下,这里就不讲解了,直接上代码。

//记住为管理员root运行
crontab -e

然后输入需要定时运行的php文件 这里的php使用cli模式进行运行 这里的格式:php的路径 项目入口文件路径 模块/控制器/Action

/usr/local/php/bin/php /home/www/500efuma/cron.php Activity/Index/christmas

Alt text

需要注意的是如果是用的是ThinkPHP框架,这里需要重新写一个入口文件,即我这里的cron.php。需要修改APP_PATHThinkPHP.php的访问路径,不然的话php会报错无法找到文件。

<?php
/**
 * 此文件为crontab定时运行的入口文件
 */
// 检测PHP环境
if(version_compare(PHP_VERSION,'5.3.0','<'))  die('require PHP > 5.3.0 !');

define('APP_DEBUG',True);
// 本地测试配置
define('APP_PATH','/home/saki/Work/PHP/500efuma/Application/');
require '/home/saki/Work/PHP/500efuma/ThinkPHP/ThinkPHP.php';

设置完crontab之后将服务重启下就ok了

service cron restart

所有代码

<?php
namespace Activity\Controller;
use Think\Controller;

class IndexController extends Controller {

    private $user_arr;
    private $K;
    private $M;
    private $N;

    //数据初始化
    public function _initialize(){
        $this->user_arr = array('小百合','小龙华','小六花','小假肢','小CC','小小野','小魔王','小透华');
        $this->N = count($this->user_arr);
        $this->K = rand(1, $this->N);
        $this->M = rand(1, $this->N);
    }

    public function index(){
        $christmas_model = M('activity_christmas');
        $list = $christmas_model->order('ctm desc')->select();
        foreach ($list as $k=>$temp) {
            $temp['data'] = (array)json_decode($temp['data']);
            $list[$k] = $temp;
        }
        $this->assign('list',$list);
        $this->assign('user_arr',$this->user_arr);
        $this->display();
    }

    public function christmas(){
        $temp = array_splice($this->user_arr, $this->K-1,$this->N-($this->K-1));
        array_splice($this->user_arr, 0, 0, $temp);
        $start = $this->user_arr;
        $result = $this->my_sort($this->user_arr);
        //data数据生成
        $data['k'] = $this->K;
        $data['m'] = $this->M;
        $data['start'] = $start;
        $data['result'] = $result;
        //DB操作记录数据
        $christmas_model = M('activity_christmas');
        $save['data'] = json_encode($data);
        $save['ctm'] = date('Y-m-d H:i:s',time());
        $christmas_model->add($save);
    }

    private function my_sort($a,$new = array()){
        if (count($a) > 1){
            $i = $this->M % count($a);//余数即踢出的第i个
            $out = array_splice($a, $i-1 ,1);
            array_push($new, $out[0]);
            //重组下
            if ($i != 0){
                $last = array_splice($a, $i-1 ,count($a)-($i-1));
                array_splice($a, 0 ,0 ,$last);
            }
            return $this->my_sort($a, $new);
        }else {
            array_push($new, $a[0]);
            return $new;
        }
    }

}

游客评论区

#1 大魔王 2016-03-08 16:58:39 / 回复

跟换到linode服务器,测试下


发表评论

(请不要填写空的评论)
提交评论 使用QQ登录