美文网首页PHP经验分享
PHP算法之过河问题

PHP算法之过河问题

作者: 小牛_6666 | 来源:发表于2019-05-17 00:33 被阅读51次

    方法一:动态规划

    <?php
    echo "过桥问题--动态规划\n";
    fwrite(STDOUT,'请输入每个过桥人(人数>=2)的时间,用空格隔开:');
    $a=fgets(STDIN);
    $speed=array_map(function ($v){ return intval($v);}, array_filter(explode(' ',$a)));
    $status=['left'=>array_keys($speed),'right'=>[],'candle'=>'left','sumTime'=>0,'path'=>'0','comment'=>'开始'];
    $end=[];
    $i=0;
    $result=[];
    gep_bridge($status);
    $path=explode(',',$end['path']);
    foreach ($path as $v){
        echo "{$result[$v]['comment']}\n";
    }
    
    function gep_bridge($status){
        global $i;
        global $result;
        global $speed;
        if(!judge($status)){#判断是否已全部过河
            return;
        }
        $result[$i]=$status;
        if($status['candle']=='left'){//灯在左边
            $c=C($status['left']);//列出左边所有的两人组合
            foreach ($c as $v){
                $time=max($speed[$v[0]],$speed[$v[1]]);//本次过河需要的时间
                $newStatus['left']=array_diff($status['left'],$v);//左边剩余的人
                $newStatus['right']=array_merge($status['right'],$v);//右边已过河的人
                $newStatus['sumTime']=$status['sumTime']+$time;//当前策略用时
                $newStatus['candle']='right';//灯在河右边
                $i++;
                $newStatus['path']=$status['path'].','.$i;//记录策略
                $newStatus['comment']="第".($v[0]+1)."个人和第".($v[1]+1)."个人过河,用时{$time},总用时{$newStatus['sumTime']}";//这里只是为了结果更直白
                gep_bridge($newStatus);//把这个策略节点当做新的节点,递归处理
            }
        }else{//灯在右边,这里还可以优化,在当前问题中,每次返回送灯的人肯定是速度最快的人,没必要列举所有情况。
            foreach ($status['right'] as $v){
                $time=$speed[$v];
                $newStatus['left']=array_merge($status['left'],[$v]);
                $newStatus['right']=array_diff($status['right'],[$v]);
                $newStatus['sumTime']=$status['sumTime']+$time;
                $newStatus['candle']='left';
                $i++;
                $newStatus['path']=$status['path'].','.$i;
                $newStatus['comment']="第".($v+1)."个人返回,用时{$time},总用时{$newStatus['sumTime']}";
                gep_bridge($newStatus);
            }
        }
    }
    
    //排列组合,返回所有两人组合
    function C($arr){
        $count=count($arr);
        $result=[];
        for ($i=0;$i<$count-1;$i++){
            for ($j=$i+1;$j<$count;$j++){
                $result[]=[$arr[$i],$arr[$j]];
            }
        }
        return $result;
    }
    
    //判断是否结束
    function judge($status){
        global $result;
        global $end;
        global $i;
        if(count($status['left'])==0){//如果左边没有人了,表示已经全部过河
            if(!$end || $status['sumTime']<$end['sumTime']){
                //如果还没有策略成功或者策略过河的时间比当前策略时间长,则保留当前策略为最优策略
                $end['sumTime']=$status['sumTime'];
                $end['path']=$status['path'];
            }
            $result[$i]=$status;
            return false;
        }
        foreach ($result as $v){
            if($v['left']==$status['left'] && $v['right']==$status['right'] && $v['candle']==$status['candle'] && $status['sumTime']>=$v['sumTime']){
                //判断当前状况有没有出现过,在本例中不会出现
                return false;
            }
        }
        return true;
    
    }
    

    运行结果

    过桥问题--动态规划
    请输入每个过桥人(人数>=2)的时间,用空格隔开:1 8 9 10
    开始
    第1个人和第2个人过河,用时8,总用时8
    第1个人返回,用时1,总用时9
    第3个人和第1个人过河,用时9,总用时18
    第1个人返回,用时1,总用时19
    第4个人和第1个人过河,用时10,总用时29
    

    方法二:数学归纳

    <?php
    echo "过桥问题--归纳为数学问题,要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥\n";
    fwrite(STDOUT, '请输入每个过桥人(人数>=2)的时间,用空格隔开:');
    $a = fgets(STDIN);
    $speed = array_map(function ($v) {
        return intval($v);
    }, array_filter(explode(' ', $a)));
    $result = [];
    
    $sumTime = 0;
    $num = count($speed);//未过桥人数
    asort($speed);//对时间进行排序
    $keys = array_keys($speed);
    echo "开始\n";
    while ($num > 0) {
        if ($num == 1) {//一个人
            $sumTime += $speed[$keys[0]];
            $result[] = "第".($keys[0]+1)."个人过河,用时{$speed[$keys[0]]},总用时{$sumTime}";
        } elseif ($num == 2) {//两个人
            $sumTime += $speed[$keys[1]];
            $result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河,用时{$speed[$keys[1]]},总用时{$sumTime}";
        } elseif ($num == 3) {//三个人
            $sumTime += $speed[$keys[1]];
            $result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河,用时{$speed[$keys[0]]},总用时{$sumTime}";
            $sumTime += $speed[$keys[0]];
            $result[] = "第".($keys[0]+1)."个人返回,用时{$speed[$keys[0]]},总用时{$sumTime}";
            $sumTime += $speed[$keys[2]];
            $result[] = "第".($keys[0]+1)."个人和第".($keys[0]+2)."个人过河,用时{$speed[$keys[0]]},总用时{$sumTime}";
        } else {//四个人 分两种情况
            //1最快的将最慢两人送过河
            $time1 = $speed[$keys[$num - 1]] + $speed[$keys[0]] * 2 + $speed[$keys[$num - 2]];
            //2最快的两人将最慢两人送过河
            $time2 = $speed[$keys[1]] * 2 + $speed[$keys[0]] + $speed[$keys[$num - 1]];
            if ($time1 < $time2) {
                $sumTime += $speed[$keys[$num - 1]];
                $result[] = "第".($keys[0]+1)."个人和第".($keys[$num-1]+1)."个人过河,用时{$speed[$keys[$num-1]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[0]];
                $result[] = "第".($keys[0]+1)."个人返回,用时{$speed[$keys[0]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[$num - 2]];
                $result[] = "第".($keys[0]+1)."个人和第".($keys[$num-2]+1)."个人过河,用时{$speed[$keys[$num-2]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[0]];
                $result[] = "第".($keys[0]+1)."个人返回,用时{$speed[$keys[0]]},总用时{$sumTime}";
            } else {
                $sumTime += $speed[$keys[1]];
                $result[] = "第".($keys[0]+1)."个人和第".($keys[1]+1)."个人过河,用时{$speed[$keys[1]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[0]];
                $result[] = "第".($keys[0]+1)."个人返回,用时{$speed[$keys[0]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[$num - 1]];
                $result[] = "第{$keys[$num-1]}个人和第".($keys[$num-2]+1)."个人过河,用时{$speed[$keys[$num-1]]},总用时{$sumTime}";
                $sumTime += $speed[$keys[1]];
                $result[] = "第".($keys[1]+1)."个人返回,用时{$speed[$keys[1]]},总用时{$sumTime}";
            }
        }
        $num = ($num >= 3 ? $num - 2 : 0);
    }
    foreach ($result as $v){
        echo $v."\n";
    }
    

    运行结果

    过桥问题--归纳为数学问题,要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥
    请输入每个过桥人(人数>=2)的时间,用空格隔开:1 8 9 10
    开始
    第1个人和第4个人过河,用时10,总用时10
    第1个人返回,用时1,总用时11
    第1个人和第3个人过河,用时9,总用时20
    第1个人返回,用时1,总用时21
    第1个人和第2个人过河,用时8,总用时29
    

    相关文章

      网友评论

        本文标题:PHP算法之过河问题

        本文链接:https://www.haomeiwen.com/subject/eaegaqtx.html