用1, 5, 10, 20, 50, 100的纸币各五张,求出纸币组合
今天在网上找工作的时候,遇到一道挺有趣的面试题:
请使用php内置的库以及方法编写一个函数,解决该问题:
现有面额为1,5,10,20,50,100的纸币各五张,对于给定的金额n,求得所有可能的纸币组合,使用$n作为输入参数,输出数组。
正好来了兴趣,所以尝试解了一下,下面将代码贴在下面:
<?php
/**
* Class Permutations
*/
class Permutations
{
const NUM = 5;
private $map = [];
static private $i;
/**
* Permutations constructor.
* @param string $filePath
* @throws Exception
*/
public function __construct(string $filePath = '')
{
if (!empty($filePath))
$this->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);