用1, 5, 10, 20, 50, 100的纸币各五张,求出纸币组合
今天在网上找工作的时候,遇到一道挺有趣的面试题:
请使用php内置的库以及方法编写一个函数,解决该问题:
现有面额为1,5,10,20,50,100的纸币各五张,对于给定的金额n,求得所有可能的纸币组合,使用$n作为输入参数,输出数组。
正好来了兴趣,所以尝试解了一下,下面将代码贴在下面:
loadFile($filePath); else $this->generateMap(); } /** * @param string $filePath * @throws Exception */ private function loadFile(string $filePath): void { if (!file_exists($filePath)) throw new Exception("文件 $filePath 不存在!"); $strBuffer = file_get_contents($filePath); $this->map = @json_decode($strBuffer, true); if (!$this->map) throw new Exception("文件读取错误!"); } private function generateMap(): void { for ($i100=0; $i100<=self::NUM; $i100++) { for ($i50=0; $i50<=self::NUM; $i50++) { for ($i20=0; $i20<=self::NUM; $i20++) { for ($i10 = 0; $i10<=self::NUM; $i10++) { for ($i5 = 0; $i5<=self::NUM; $i5++) { for ($i1 = 0; $i1<=self::NUM; $i1++) { $sum = $i1*1 + $i5*5 + $i10*10 + $i20*20 + $i50*50 + $i100*100; $this->addItem($sum, [$i1, $i5, $i10, $i20, $i50, $i100]); } // end for $i1 } // end for $i5 } // end for $i10 } // end for $i20 } // end for $i50 } // end for $i100 } /** * @param string $key * @param array $item * @return array */ private function addItem(string $key, array $item): array { if (!isset($this->map[$key])) $this->map[$key] = []; return $this->map[$key][] = $item; } /** * @param string $key * @throws Exception */ public function print(string $key = ''): void { if (!empty($key)) { if (!isset($this->map[$key])) throw new Exception("键值不存在!"); $this->echoItem($key, $this->map[$key]); } else { foreach ($this->map as $k => $v) $this->echoItem($k, $v); } } /** * @param string $key * @param array $value */ private function echoItem(string $key, array $value): void { $sum = $key; foreach ($value as $k=>$v) { list($i1, $i5, $i10, $i20, $i50, $i100) = $v; echo "i1=$i1, i5=$i5, i10=$i10, i20=$i20, i50=$i50, i100=$i100, sum=$sum\n"; } echo "\n"; } /** * @param string $key * @return array * @throws Exception */ public function getValue(string $key = ''): array { if (!empty($key)) { if (!isset($this->map[$key])) throw new Exception("键值不存在!"); return $this->map[$key]; } return $this->map; } /** * @param $filePath */ public function saveFile($filePath) { @file_put_contents($filePath, @json_encode($this->map)); } /** * 单例 * @param string $filePath * @throws Exception * @return \Permutations */ static public function i(string $filePath = ''): \Permutations { if (!static::$i) static::$i = new static($filePath); return static::$i; } } $test = Permutations::i(); //$test->saveFile("test.txt"); //print_r($test->getValue(70)); $test->print(90);