CODE-分贓程式的寫法

把一筆錢依特定的比例分給幾個人是我工作上常要處理的需求。由於金額必須四捨五入到元或分,因此常需面對除不盡的錢要設法攤掉的問題。例如100元平分給三個人,每人33元後,最後的1元要發給三人之一的幸運兒,變成一人34, 兩人33的分配結果。

以前年紀小不懂事,很直覺的想法是先用100*1/3四捨五入得到33把錢分一分,之後再跑一個迴圈(沒辦法,總不能打電話請這三個人過來猜拳吧?)把分剩的錢(總金額大、人數多時餘下數十上百元也是有可能滴)每次一元地發下去,直到發光為止。

說實在說,當初並不覺得這個寫法有什麼不對,直到有前輩指點了另一種更精巧的演算法,一口氣就能把錢攤到一毛不剩,省去分完一輪後處理餘數的麻煩。相形之下,原本的寫法挺笨拙的...

using System;
using System.IO;
using System.Threading;
 
public class CSharpLab
{
    public static void Test()
    {
        //100萬元要依比例分給3個人(四拾五入計算到元)
        int totalAmt = 1000000;
        int[] amt = new int[3];
        //三個人勢均力敵,100萬除以3會有餘1元的問題
        //且看以下的邏輯演法如何避免事後分攤的困擾
        decimal[] fact = new decimal[] { 1.2M, 1.2M, 1.2M };
        //先加總分配權重
        decimal factSum = 0;
        for (int i = 0; i < fact.Length; i++)
            factSum += fact[i];
        //使用以下邏輯分配, 會自然吸收掉四捨五入差額
        for (int i = 0; i < fact.Length; i++)
        {
            amt[i] = Convert.ToInt32(
                    Math.Round(totalAmt * fact[i] / factSum, MidpointRounding.AwayFromZero)
                );
            Console.WriteLine("{0} * {1} / {2} = {3}", totalAmt, fact[i], factSum, amt[i]);
            totalAmt -= amt[i];
            factSum -= fact[i];
        }
    }
}

執行結果是: (以上程式可以用Mini C# Lab直接測試)

1000000 * 1.2 / 3.6 = 333333
666667 * 1.2 / 2.4 = 333334
333333 * 1.2 / 1.2 = 333333

很棒吧! 它可以很自然順暢地在分攤過程中吸收掉四捨五入可能產生的差額,一步到位!

最近手上的案子在寫AJAX網頁,開始把這樣的概念搬到Javascript上實作。(以下程式可以使用Mini jQuery Lab測試)

var factor = [ 1.2, 1.2, 1.2 ], factorSum = 0;
var totalAmount = 1000000, amount = [];
for (var i = 0; i < factor.length; i++) factorSum += factor[i];
var r = "";
for (var i = 0; i < factor.length; i++)
{
    amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum))
    r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";
    totalAmount -= amount[i];
    factorSum -= factor[i];
}
alert(r);

執行結果是

1000000 * 1.2 / 3.5999999999999996 = 333333
666667 * 1.2 / 2.3999999999999994 = 333334
333333 * 1.2 / 1.1999999999999995 = 333333

數字是對的,但明眼人已可看到其中暗藏殺機... 3.5999999999999996? 明明應該是3.6,因為Javascript裡只有浮點數,沒有像.NET decimal一樣分亳不差的精準數字型別,所以數字都是用逼近的。

俗話說得好: "算錢用浮點,遲早被人扁"! 雖然浮點運算的微小誤差多半要遇到天文數字計算或複雜的累乘累除時才會爆炸,但實事求事總是比較好,跟錢有關的東西,一丁點不對都會吵翻天。"插擠摳"(差一元)是每一個帳務會計程式開發人員的惡夢,為了避免未來某一天為了找一塊錢找到吐血,這裡還是花點心思防範未然。

var factor = [1.2, 1.2, 1.2], factorSum = 0;
var totalAmount = 1000000, amount = [];
function r2(n) { return parseFloat(n.toFixed(2)); }
for (var i = 0; i < factor.length; i++) 
    factorSum = r2(factorSum + factor[i]);
var r = "";
for (var i = 0; i < factor.length; i++)
{
    amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum))
    r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";
    totalAmount -= amount[i];
    factorSum = r2(factorSum - factor[i]);
}
alert(r);

我假設factor的精準度到兩位,利用to.Fixed(2)的方法四捨五入加總及刪減過的結果。經過這番修正,結果好看多了!

1000000 * 1.2 / 3.6 = 333333
666667 * 1.2 / 2.4 = 333334
333333 * 1.2 / 1.2 = 333333

【心得】Javascript在數字處理上挺弱的,沒有decimal,型別不嚴謹,計算速度無法跟.NET等編譯式語言匹敵,連四捨五入到小數第幾位都得繞一圈。不過看在它可以輕易跨平台跨瀏覽器的分上,只好摸摸鼻子認了。Silverlight 3.0正式版快要誕生了,過陣子再來Survey它與AJAX網頁應用上的互補性。

[2012-02-23更新]本演算法在極端例子下會崩壞,修正方法請參見補充文章

歡迎推文分享:
Published 11 June 2009 05:53 AM 由 Jeffrey
Filed under: , ,
Views: 21,917



意見

# steve said on 10 June, 2009 06:23 PM

請問權重為何是1.2?

看起來應該是每個權重都相等就好了

1.2/3.6 跟 1/3不是一樣嗎?

# bugryder said on 10 June, 2009 07:08 PM

實用的KB~之前都沒注意(跟您以前一樣)

# 我是路過的~~ said on 10 June, 2009 07:19 PM

100元3個人分,會不會每次都是相同的人多拿一元 XD

# Maxi said on 10 June, 2009 08:07 PM

等你的silverlight分析

# tomexou said on 10 June, 2009 09:45 PM

SL3 Final 聽說應該是在7/10出來。之前也有謠傳6/10,但它已過了,而況最重要的特色RIA Data Service還沒順利整合進去,比較可能是7/10。

Win7好像在10月發表,VS2010在12月,以上都是猜測而己。

# 山姆大叔 said on 11 June, 2009 03:16 AM

受教了~ 滿有趣的...

# 山姆大叔 said on 11 June, 2009 03:17 AM

受教了~ 滿有趣的方法 (抄筆記)

# 路過的貓 said on 11 June, 2009 03:30 AM

之前在寫算錢的程式時遇到四捨五入的問題

這是那時寫的筆記(有些資料是查別人BLOG來的)

請黑暗大看看是不是真的是這樣子@@

Rounding 有分兩種,Arithmetic Rounding 跟 Banker's Rounding

Arithmetic Rounding 就是我們平常所說的四捨五入

Banker's Rounding 他是奇入偶不入,所以只有當遇到奇數位的時候會四捨五入 (所以 1.115 會進位成 1.12)

否則就是四捨六入 (所以 1.125 是捨去變成 1.12,如果是 1.126 則變成 1.13)

除了 Round() 這個函數外 CByte()、CInt()、CLng()、CCur() 也都是使用 Banker's Rounding。

# 剛好經過 said on 11 June, 2009 03:57 AM

如果每次都是相同的人多拿一塊錢,那不公平阿

我覺得這次多拿一元的人,他的權重應該要降低,

這樣下次就不會又是他多拿一元了。

# Jeffrey said on 11 June, 2009 09:49 AM

@路過的貓,斯斯有兩種,四捨五入也是,正如你所說。我也有另一篇文章談過: blog.darkthread.net/.../kb-net-math-quiz.aspx

@我是路過的/剛好經過,就會計師的角度,制訂嚴謹的規則比公平性更重要。我本來還異想天開想用用亂數來分配餘額以求公平,結果被長官當頭棒喝: 如果會計師請你證明這個金額是怎麼算出來的,你每次跑程式出來的結果都不同,就該準備一下履歷表了。

# 路過的貓 said on 14 June, 2009 07:19 PM

咦,對耶

之前搜尋技術資料時很多都會GOOGLE到這裡

但這篇四捨五入為啥不是XD

失禮了@@a

遇到要分錢的問題(有ABC三人的話)

我是A先算好並四捨五入

B算好並四捨五入

C=Total-A-B

這樣子來做的

# 必要的 said on 23 June, 2009 04:14 PM

滿有趣的

但是以下是不是比較實用些?

int count = amt.Length;

int average = totalAmount / count;

for (var i = 0; i < totalAmount%count; i++)

{

   amount[i] = average + 1;

}

for (var i = totalAmount%count; i < count; i++)

{

   amount[i] = average;

}

# Jeffrey said on 23 June, 2009 05:01 PM

to 必要的,您提供的演算法應用於整數等比例平分時很合適,但實務上常需要依不同人不同權重比例做分配,有時也會到小數兩位(例如: 美金),演算法多半會再複雜些。

# bestlong said on 22 March, 2010 02:54 AM

很好玩的處理技巧

但是想請教當面臨不同的狀況下要怎麼處理呢?

例如:

10 元分給 7 人會有三個人拿 2 元

100 元分給 7 人會有兩個人拿 15 元

怎麼做出共用的演算法?

# Jeffrey said on 22 March, 2010 04:14 AM

to bestlong, 沒看懂,文中的演算法理論應可滿足你說的需求(10元分7人有3人拿2元,100元分7人有2人拿15元),或者指的是還有其他考量?

# bestlong said on 22 March, 2010 06:43 PM

是我偷懶了,沒有自己改程式碼跑過。目前研究結果如下,已在 Mini jQuery Lab 跑過

十元分七人:

var factor = [ 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2 ], factorSum = 0;

var totalAmount = 10, amount = [];

for (var i = 0; i < factor.length; i++) factorSum += factor[i];

var r = "";

for (var i = 0; i < factor.length; i++){

   amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum));

   r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";

   totalAmount -= amount[i];

   factorSum -= factor[i];

}

alert(r);

百元分七人:

var factor = [ 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2 ], factorSum = 0;

var totalAmount = 100, amount = [];

for (var i = 0; i < factor.length; i++) factorSum += factor[i];

var r = "";

for (var i = 0; i < factor.length; i++){

   amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum));

   r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";

   totalAmount -= amount[i];

   factorSum -= factor[i];

}

alert(r);

所以權重分配是由 factor 陣列來決定的是吧,唯一的限制就是 factor 陣列必須至少有一個非零值,不知道我有沒有理解錯誤。不過這個演算碼有名字嗎?

# bestlong said on 22 March, 2010 06:43 PM

是我偷懶了,沒有自己改程式碼跑過。目前研究結果如下,已在 Mini jQuery Lab 跑過

十元分七人:

var factor = [ 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2 ], factorSum = 0;

var totalAmount = 10, amount = [];

for (var i = 0; i < factor.length; i++) factorSum += factor[i];

var r = "";

for (var i = 0; i < factor.length; i++){

   amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum));

   r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";

   totalAmount -= amount[i];

   factorSum -= factor[i];

}

alert(r);

百元分七人:

var factor = [ 1.2, 1.2, 1.2, 1.2, 1.2, 1.2, 1.2 ], factorSum = 0;

var totalAmount = 100, amount = [];

for (var i = 0; i < factor.length; i++) factorSum += factor[i];

var r = "";

for (var i = 0; i < factor.length; i++){

   amount[i] = parseInt(Math.round(totalAmount * factor[i] / factorSum));

   r += totalAmount + " * " + factor[i] + " / " + factorSum + " = " + amount[i] + "\n";

   totalAmount -= amount[i];

   factorSum -= factor[i];

}

alert(r);

所以權重分配是由 factor 陣列來決定的是吧,唯一的限制就是 factor 陣列必須至少有一個非零值,不知道我有沒有理解錯誤。不過這個演算碼有名字嗎?

# Clement said on 31 October, 2010 09:48 PM

太晚看到這篇了(該死的採購),Jeffrey 您真的是明燈阿,順便好奇一下,有沒有SP版本的(貌似年假大了越懶得動腦><")

你的看法呢?

(必要的) 
(必要的) 
(選擇性的)
(必要的) 
(提醒: 因快取機制,您的留言幾分鐘後才會顯示在網站,請耐心稍候)

5 + 3 =

搜尋

Go

<June 2009>
SunMonTueWedThuFriSat
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011
 
RSS
創用 CC 授權條款
【廣告】
twMVC
最新回應

Tags 分類檢視
關於作者

一個醉心技術又酷愛分享的Coding魔人,十年的IT職場生涯,寫過系統、管過專案, 也帶過團隊,最後還是無怨無悔地選擇了技術鑽研這條路,近年來則以做一個"有為的中年人"自許。

文章典藏
其他功能

這個部落格


Syndication