假設我有一塊 8027 平方米的地塊（一塊土地），我有多個所有者，但他們擁有的土地數量不同。
業主 A 有：1003.5 平方米 業主 B 有：1003.5 平方米 業主 C 有 1337 平方米 業主 D 有 1338 平方米 業主 E 有 1338 平方米 業主 F 有 2007 平方米
作為輸出，我想獲得具有最低可能公分母的整數分數等
1/8 1/8 .. .. ..
我知道它不太可能會這么小......
但是當您劃分分數時，每個所有者的差異不應超過 /- 1m2
意思是如果所有者 A 一開始有 1003.5 平方米，我得到 1/8 8027/8=1003.35 沒關系，但是，不幸的是，大但是！最后所有所有者的總和必須保持不變:(
現在，我能夠單獨為所有者獲得最低公分母，我什至不確定獲得想要的結果的下一步是什么......
任何幫助深表感謝！
gcd = function (a, b) {
if (b < 0.0000001)
return a; // Since there is a limited precision we need to limit the value.
return gcd(b, Math.floor(a % b)); // Discard any fractions due to limitations in precision.
};
var total_area = 8027;
var area_parts = [1003.5, 1003.5, 1337, 1338, 1338, 2007];
ResaultArr = Array();
for (let i = 0; i < area_parts.length; i ) {
var decimal_fraction = area_parts[i] / total_area;
var denominator = Math.pow(10, 4);
var numerator = decimal_fraction * denominator;
var divisor = gcd(numerator, denominator);
numerator /= divisor;
denominator /= divisor;
var fraction = Math.floor(numerator) '/' Math.floor(denominator);
var decimal_fraction_after = Math.floor(numerator) / Math.floor(denominator);
var area_difference = area_parts[i] - (total_area * decimal_fraction_after);
var area_part_after = total_area * decimal_fraction_after;
ResaultArr[i] = {
area_difference: area_difference,
fraction: fraction,
decimal_fraction: decimal_fraction,
decimal_fraction_after: decimal_fraction_after,
area_part: area_parts[i],
area_part_after: area_part_after,
total_area: total_area
};
}
console.log(ResaultArr);
uj5u.com熱心網友回復：
蠻力方法只是嘗試連續的分母，直到找到一個有效的分母：
const makeFractions = (xs, tolerance = 1, n = xs .length) => {
const total = xs .reduce ((a, b) => a b, 0)
const numerators = xs .map (x => Math .round (x * n / total))
const denom = numerators .reduce ((a, b) => a b, 0)
const candidates = numerators .map (y => y * total / denom)
return candidates .some ((y, i) => Math .abs (y - xs [i]) > tolerance)
? makeFractions (xs, tolerance, n 1)
: numerators .map (y => `${y}/${denom}`)
}
const parts = [1003.5, 1003.5, 1337, 1338, 1338, 2007], total = 8027
const results = makeFractions (parts)
console .log ('parts: ', parts)
console .log ('fractions:', results)
console .log ('exact values: ', results .map (
s => s .split('/').map (Number)) .map (([n, d]) => n * total / d
)).as-console-wrapper {max-height: 100% !important; top: 0}在這里，我們從陣列的長度 of 開始n，6然后將這些值按6它們近似的總數的 th 數四舍五入，得到 的潛在分子[1, 1, 1, 1, 1, 2]，這些分子的總和為我們提供了 的分母7和 的候選分解[1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 2293.4285714285716]。其中至少有一個距離我們的目標數字太遠了——事實上，在這種情況下，它們都離我們的目標數字太遠了——所以我們用7for再試一次n。我們得到相同的細分，并且再次獲得相同的細分8。當我們擊中時9，我們得到 的分母9和候選者[891.8888888888889, 891.8888888888889, 891.8888888888889, 1783.7777777777778, 1783.7777777777778, 1783.7777777777778]}。這些還太遠了，我們一直在努力。最終，我們遇到n了22，這給了我們 的潛在分子[3, 3, 4, 4, 4, 6]]，因此得到了 的分母24候選值為[1003.375, 1003.375, 1337.8333333333333, 1337.8333333333333, 1337.8333333333333, 2006.75]. 這些中的每一個都在我們1對目標數字的容忍范圍內，我們在這里停下來，回傳分數[3/24, 3/24, 4/24, 4/24, 4/24, 6/24]。
提取一個函式并存盤計算的總數可能是有意義的，sum每次遞回呼叫都不會改變，所以這可能更清晰：
const sum = (ns) => ns .reduce ((a, b) => a b, 0)
const makeFractions = (xs, tolerance = 1, total = sum (xs), n = xs .length) => {
const numerators = xs .map (x => Math .round (x * n / total))
const denom = sum (numerators)
const candidates = numerators .map (y => y * total / denom)
return candidates .some ((y, i) => Math .abs (y - xs [i]) > tolerance)
? makeFractions (xs, tolerance, total, n 1)
: numerators .map (y => `${y}/${denom}`)
}
uj5u.com熱心網友回復：
在您的示例中，比例大約為 1/8,1/8,1/6,1/6,1/6 和 1/4，我們可以給這些公分母 24，因此分數變為 3/24, 3 /24, 4/24, 4/24 和 6/24 給出的區域 1003.375, 1003.375,1337.833333,1337.833333,1337.833333, 2006.75 總和為 8027。
這讓我們知道如何更好地定義問題。找到分數 a/n、b/n、c/n、d/n、e/n、f/n 的集合，使得它們的總和為 1，并且乘積 8027 * a/n 在您想要的誤差范圍內。例如| 8027*a/n - 1003.5 | <bound 等。找到滿足此屬性的最小 n。
一種簡單的方法是在 n 上迭代地作業。
for(n=1;n<limit; n) {
a = round(n * 1003.5 / 8027);
b = round(n * 1003.5 / 8027);
c = round(n * 1337 / 8027);
d = round(n * 1338 / 8027);
e = round(n * 1338 / 8027);
f = round(n * 2007 / 8027);
errA = abs(8027*a/n - 1003.5);
....
if(a b c d e f==n && errA < bound && ... ) break;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488647.html
標籤：javascript 算法 数学
上一篇：為什么我的代碼超出了時間限制，而幾乎相同的代碼在LeetCode中作業得很好？
下一篇：無法在陣列之間分配專案