问题描述

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

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

 

编程实现

1 
     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 $list102      *            待求序列103      * @param array $range104      *            问题区间105      *            106      *            107      * @return mixed108      */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->findShortestSequence($sequences);119         // 将最短序列序列化后返回120         return range($sequence[0], $sequence[$this->listItemsCount - 1]);121     }122 123     /**124      * 搜索最短序列(未序列化)125      *126      * @param array $sequences127      *            序列集合，包含最短序列128      *            129      * @return array130      */131     private function findShortestSequence($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 $item155      *            指定项目156      * @param int $start157      *            起始搜索位置158      *            159      * @return int160      */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 $start174      *            起始搜索位置175      *            176      * @return mixed177      */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 void198      */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 }