有三種飼料，飼料中含有三種營養。給定三種飼料的各成份比，
以及目標成分比，求出三種飼料使用的最小份數，使得合成出的飼料符合目標。
無法合成則輸出"NONE"，可以則輸出 三種飼料的最小份數 及 合成出的目標份數。
解法：
化成數學式可以得到：
(ax1+bx2+cx3) : (ay1+by2+cy3) : (az1+bz2+cz3) = x : y : z
於是可以使用基於分數表示的高斯消去法，求出 a, b, c 的比例，
化為最小整數比後即得答案。
亦可使用克拉瑪公式求方程式的解，
先求出三階行列式之後再求出替換 x, y, z 後的行列式
基本上就是這條式子，同樣可以得到解答。
備註：
此題要小心有 0 的情況！
分數表示寫起來會有點冗長，
不過善用 struct 以及重載運算子應該可以縮減不少程式碼。
---
關於高斯消去法可以參考 DJWS 的文章 高斯消去法
關於克拉瑪公式可以參考這個網站 克拉瑪公式
沒有留言:
張貼留言