有趣的小算法（PHP版）

发表于 | 更新于 | 分类于

本文主要记录一些在工作、生活中遇到的有趣的算法，旨在用简单的代码给出过程和答案（基于目前编程水平的理解），不定期更新。

打印函数封装

为打印数据方便，简单自定义一个打印函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * format and output array,string, supporting objects
 *
 * @param   mixed   $print
 * @param   string  $show
 * @param   bool    $need
 */
function pp($print,$show = 'pp',$need = false){

    echo '<div style="border: 1px solid bisque;border-bottom-color:red;border-right-color:red;color:green;background-color: bisque;"><pre>';
    if($need && is_object($print)){
        $print = json_decode($print);
    }
    if($show === 'pp'){
        print_r($print);
    }
    if($show === 'var'){
        var_dump($print);
    }
    echo '</pre></div>';
    
}

“约瑟夫手环”

故事背景

一群人排成一圈，按1,2,…,30依次编号。然后从第1个开始数，数到第7个把他踢出圈，从他后面再开始数，再数到第7个，在把他踢出去，如此不停的进行下去，直到最后个剩下一个人为止，求出最后剩下的那个人是谁。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
$arr = range(1,30);
$num = 0;
while(count($arr) !== 1){
    foreach($arr as $k => $v){
        $num++;
        if($num % 7 === 0){
            unset($arr[$k]);
            $num = 0;
        }
    }
}

pp($arr);

思路说明

  1. 解题关键点是不能被编号为1到30的人所迷惑，最直接的办法就是如上：设置一个变量，让他从零自增，自增到7再重新赋值为0，每次这个变量的值为7的时候，便把数组中循环了7次时对应的键删掉，核心逻辑就这么多；
  2. unset($arr[$k]);不能替换成unset($v)，unset($v)这只是把$v这个数字删除掉，但并没有把数组中这个值对应的键删掉。

封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function theLastOne($peopleCount,$remove){
    $arr = range(1,$peopleCount);
    $num = 0;
    while(count($arr) !== 1){
        foreach($arr as $k => $v){
            $num++;
            if($num % $remove === 0){
                unset($arr[$k]);
                $num = 0;
            }
        }
    }
    return $arr;
}

pp(theLastOne(30,7));

关于分钱的问题

问题描述

将10000块钱分成5份，且每一份之间的相差的值$d不一样，并且相差$d得大于100。

代码及调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 判断数组内是否有差值相等
function check_diff($arr){
    if(empty($arr)){
        return false;
    }
    
    $arr = array_map('intval',$arr);
    sort($arr);
    
    $count    = count($arr);
    $diff_arr = array();
    for($i = $count - 1;$i >= 0;$i--){
        for($j = 0;$j < $count;$j++){
            if($arr[$i] <= $arr[$j]){
                continue 2;
            }
            $diff_arr[] = $arr[$i] - $arr[$j];
        }
    }
    
    return count($diff_arr) === count(array_unique($diff_arr));
}

// 主要处理逻辑
function process($sum = 10000,$diff = 100,$count = 5){
    
    $return = array();
    $i      = 1;
    while($i < $count){
        // 随机数不符合要求时的结果初始化
        if(isset($return[$i]) || isset($return[$i + 1])){
            unset($return[$i],$return[$i + 1]);
        }
        $remain_sum   = $sum - array_sum($return);      // 剩余数
        $remain_count = ($count - count($return));     // 剩余需要随机的个数
        $min_diff     = $remain_count * ($remain_count - 1) * (2 * ($remain_count - 1) + 4) / 12 + ($remain_count * ($remain_count - 1) / 2) * $diff;// 高斯求最小差值和，分两部分：S = n(n+1)(2n+4)/12 + $diff * ((n-1)(n-2)/2)
        $min          = $i === 1 ? 1 : $return[$i - 1] + $diff + 1; // 随机范围的最小值
        mt_srand((double)microtime() * 1000000);// 在范围内获取随机数
        $rand_max   = (int)(($remain_sum - $min_diff) / $remain_count); // 随机范围的最大值
        $min        = random_int($min,$rand_max);   // 产生随机数
        $return[$i] = $min;     // 放入返回的数组
        if($i === $count - 1){
            $return[$i + 1] = $remain_sum - $min;   // 最后一个随机数直接取总数减去前面的随机数
        }
        if(check_diff($return) === false){
            $i--;
            continue;
        }
        $i++;
    }
    
    return $return;
}

pp(process());

思路说明

问题链接

更新时间：2018-05-31 15:30