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

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

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的结果如下: 测试结果

如果还要加上输入的纸币数量判断,更复杂点,后期补上。

林明潭blog
请先登录后发表评论
  • latest comments
  • 总共0条评论