php面试题：现有i张十元纸币，k张五元纸币，j张两元纸币，购物后要支付n元(i,j,k,n 为整数)。要求编写一个复杂度为O(1)的函数FindSolution(i,j,k, n),功能是计算出能否用现在手上拥有的纸币是否足够并能刚好拼凑齐n元，而不需要找零。

林明潭
2019-09-05 21:58:06
php
php

今天面试遇，到如下面试题，当时手写代码很不方便，这道题没解清楚，于是回来重新整理下。

php面试题：现有i张十元纸币，k张五元纸币，j张两元纸币，购物后要支付n元(i,j,k,n 为整数)。要求编写一个复杂度为O(1)的函数Changes(i,j,k, n),功能是计算出能否用现在手上拥有的纸币是否足够并能刚好拼凑齐n元，而不需要找零。

1、如果可以，在屏幕输出一个方案并结束: (例子:“需要2张十元纸币，1张五元纸币，张两元纸币，刚好可凑齐27元”)

2、如果不可以，在屏幕输出“不能刚好凑齐 n元”。

//因为时间和手写的关系，只需要求最优解
function FindSolution($n){
	$ten = $five = $two = 0;
	$tmp1 = $n%10;
	if($tmp1 == 0){
		//10的整数倍
		$ten = $n/10;
	}else{
		$ten = ($n - $tmp1)/10;
		//大于10
		if($ten > 0){
			//如果余数小于5，2、4可以被2整除，1、3需要向10借1
			if($tmp1 < 5){
				$tmp2 = $tmp1%2;
				if($tmp2 == 0){
					//余数为2、4
					$five = 0;
					$two = $tmp1/2;
				}else{
					//余数为1、3
					$ten = $ten - 1;//向10借1
					$five = 1;//5块只能为1，1、3加5后肯定能被2整除
					$tmp3 = ($tmp1+5)%2;
					if($tmp3 == 0){
						$two = ($tmp1+5)/2;
					}
				}
			}else{
				//如果余数大于5，5、6、7、8、9
				$tmp2 = $tmp1%5;
				if($tmp2 == 0){
					//余数为5
					$five = $tmp1/5;
				}else{
					//余数为6、7、8、9
					$five = ($tmp1 - $tmp2)/5;
					$tmp3 = $tmp2%2;
					if($tmp3 == 0){
						//余数为7、9
						$two = $tmp2/2;
					}else{
						//余数为6、8
						$five = 0;
						$two = $tmp1/2;
					}
				}
			}
		}else{
			if($tmp1 < 5){
				//余数只有1234，其中1和3不行
				$tmp2 = $tmp1%2;
				if($tmp2 == 0){
					$two =  $tmp1/2;
				}else{
					echo "不能刚好凑齐".$n."元<br>";
				}
			}else{
				//余数为5、6、7、8、9
				$tmp2 = $tmp1%5;
				if($tmp2 == 0){
					//余数为5
					$five = $tmp1/5;
				}else{
					//余数为6、7、8、9
					$five = ($tmp1 - $tmp2)/5;
					$tmp3 = $tmp2%2;
					if($tmp3 == 0){
						//余数为7、9
						$two = $tmp2/2;
					}else{
						//余数为6、8
						$five = 0;
						$two = $tmp1/2;
					}
				}
			}
		}
	}
	echo '需要<span style="color:red;">'.$ten.'</span>张十元纸币，<span style="color:red;">'.$five.'</span>张五元纸币，<span style="color:red;">'.$two.'</span>张两元纸币，刚好可凑齐<span style="color:red;">'.$n.'</span>元<br>';
}

得出1-30的结果如下：测试结果