今天看啥
    热点:

      天发国际娱乐官网:同时官方宣布,讴歌TLX将会在2017年国产亮相。

      逆FizzBuzz问题求最短序列,fizzbuzz最短序列


      问题描述

      FizzBuzz问题:一个大于0的自然数能整除3,将输出“Fizz”;能整除5,将输出“Buzz”;能整除3和5,将输出“FizzBuzz”;否则输出自己。

      逆FizzBuzz问题最短序列:已知一个FizzBuzz问题的非数字输出序列,求能获得该序列的最短连续数字序列。如“Fizz”的最短序列是“3”,“Fizz Buzz”的最短序列是“9 10”,而不是“3 4 5”。

       

      编程实现

        1 <?php
        2 
        3 /**
        4  * @author cenze
        5  *
        6  * 反FizzBuzz问题求最短序列
        7  * 
        8  * $inverseFizzBuzz = new InverseFizzBuzz([
        9  *   'fizz',
       10  *   'fizz',
       11  *   'buzz',
       12  * ]);
       13  * $inverseFizzBuzz->sequence():
       14  * Array ( [0] => 6 [1] => 7 [2] => 8 [3] => 9 [4] => 10 )
       15  */
       16 class InverseFizzBuzz
       17 {
       18     // FizzBuzz问题赋值
       19     const FizzBuzz = [
       20         'fizz' => 3,
       21         'buzz' => 5,
       22         'fizzbuzz' => 15
       23     ];
       24     
       25     // 预定义问题区间
       26     private $range = [
       27         1,
       28         100
       29     ];
       30     
       31     // 待求序列
       32     private $list = [];
       33     
       34     // 待求序列包含项数统计
       35     private $listItemsCount = 0;
       36 
       37     public function __construct($list = [], $range = [])
       38     {
       39         $this->init($list, $range);
       40     }
       41 
       42     /**
       43      * 待求序列、区间初始化
       44      *
       45      * @param array $list
       46      *            待求序列
       47      * @param array $range
       48      *            问题区间
       49      * @param bool $check
       50      *            是否检查属性已完成初始化
       51      *            
       52      * @return void
       53      */
       54     private function init($list = [], $range = [], $check = false)
       55     {
       56         if ($list) {
       57             $this->list = $this->inverseList($list);
       58             $this->listItemsCount = count($this->list);
       59             if (! $this->listItemsCount) {
       60                 exit('Invalid list.');
       61             }
       62         }
       63         
       64         if ($range) {
       65             $this->range = $range;
       66         }
       67         
       68         if ($check) {
       69             if (! $this->list) {
       70                 exit('Property list uninitialized.');
       71             }
       72         }
       73     }
       74 
       75     /**
       76      * 将待求解序列反转
       77      *
       78      * @param array $list
       79      *            待求解序列
       80      *            
       81      * @return mixed
       82      */
       83     private function inverseList($list)
       84     {
       85         $inverseList = [];
       86         foreach ($list as $item) {
       87             if (! array_key_exists($item, self::FizzBuzz)) {
       88                 return null;
       89             }
       90             $inverseList[] = self::FizzBuzz[
       91                 $item
       92             ];
       93         }
       94         
       95         return $inverseList;
       96     }
       97 
       98     /**
       99      * 搜索最短序列是否存在
      100      *
      101      * @param array $list
      102      *            待求序列
      103      * @param array $range
      104      *            问题区间
      105      *            
      106      *            
      107      * @return mixed
      108      */
      109     public function sequence($list = [], $range = [])
      110     {
      111         $this->init($list, $range, true);
      112         
      113         $sequences = $this->findSequences();
      114         if (! $sequences) {
      115             return 'Found no sequences.';
      116         }
      117         
      118         $sequence = $this->shortestSequence($sequences);
      119         // 将最短序列序列化后返回
      120         return range($sequence[0], $sequence[$this->listItemsCount - 1]);
      121     }
      122 
      123     /**
      124      * 搜索最短序列(未序列化)
      125      *
      126      * @param array $sequences
      127      *            序列集合,包含最短序列
      128      *            
      129      * @return array
      130      */
      131     private function shortestSequence($sequences)
      132     {
      133         // 默认第一条为最短
      134         $shortestSequence = $sequences[0];
      135         // 把每一个序列看做一条路径,都有对应的长度。记录最短的序列长度
      136         $shortestSequenceLength = $sequences[0][$this->listItemsCount - 1] - $sequences[0][0];
      137         // 为array_reduce()定义一个callback,用来搜索最短序列
      138         $findShortestSequence = function ($shortestSequence, $currentSequence) use(&$shortestSequenceLength) {
      139             $currentSequenceLength = $currentSequence[$this->listItemsCount - 1] - $currentSequence[0];
      140             if ($currentSequenceLength < $shortestSequenceLength) {
      141                 $shortestSequenceLength = $currentSequenceLength;
      142                 return $currentSequence;
      143             } else {
      144                 return $shortestSequence;
      145             }
      146         };
      147         
      148         return array_reduce($sequences, $findShortestSequence, $shortestSequence);
      149     }
      150 
      151     /**
      152      * 从指定位置开始搜索指定项目的序列
      153      *
      154      * @param int $item
      155      *            指定项目
      156      * @param int $start
      157      *            起始搜索位置
      158      *            
      159      * @return int
      160      */
      161     private function findItemSequenceFromPosition($item, $start)
      162     {
      163         if ($start % $item == 0) {
      164             return $start;
      165         }
      166         
      167         return $start + ($item - $start % $item);
      168     }
      169 
      170     /**
      171      * 从指定位置开始搜索首个序列
      172      *
      173      * @param int $start
      174      *            起始搜索位置
      175      *            
      176      * @return mixed
      177      */
      178     private function findSequenceFromPosition($start)
      179     {
      180         $listSequence = [];
      181         for ($i = 0; $i < $this->listItemsCount; $i ++) {
      182             $itemSequence = $this->findItemSequenceFromPosition($this->list[$i], $start);
      183             if ($itemSequence > $this->range[1]) {
      184                 return null;
      185             } else {
      186                 $listSequence[] = $itemSequence;
      187                 $start = $itemSequence + 1;
      188             }
      189         }
      190         
      191         return $listSequence;
      192     }
      193 
      194     /**
      195      * 找到多个序列,其中包括最短序列
      196      *
      197      * @return void
      198      */
      199     private function findSequences()
      200     {
      201         $sequences = [];
      202         // 以第一个项为初始搜索位置在预定区间中搜索,且以第一个项为递增步长向后逐步搜索
      203         for ($start = $this->list[0]; $start <= $this->range[1]; $start += $this->list[0]) {
      204             // 只需找到指定位置开始的第一个序列即可
      205             if ($sequence = $this->findSequenceFromPosition($start)) {
      206                 $sequences[] = $sequence;
      207             }
      208         }
      209         
      210         return $sequences;
      211     }
      212 }

       

      www.1click-soft.comtruehttp://www.1click-soft.com/PHPjc/1311229.htmlTechArticle逆FizzBuzz问题求最短序列,fizzbuzz最短序列 问题描述 FizzBuzz问题 :一个大于0的自然数能整除3,将输出“Fizz”;能整除5,将输出“Buzz”;...

      相关文章

        暂无相关文章
      相关搜索:

      帮客评论

      视觉看点
      百度 360 搜狗