稍微說點錢的事吧 - 分錢的方法 (1)

  • 2281
  • 0
  • C#
  • 2012-09-06

摘要:分錢的方法 (1)

之所以會寫這篇,是因為逛黑暗執行緒時,看到了無尾差分贓法崩壞記
想到我之前做的一些UI,也有這種分贓的行為,不過用的算法不一樣。

喔,對了。先提醒一下,若你真的要嚴格的分錢,請不要用這篇的做法,也不要用黑暗執行緒目前的做法,是有缺陷存在的。

大家不知道有沒有這種經驗:做一個UI,想把它的內容項目均分、或依比例顯示在某個可變區域裡。類似表格的感覺。
但對於整數的寬或高,總是無法真正均分,這時剩下的部分要怎麼分配呢?

回到算錢,說到錢大家比較有興趣!

有個公司賺錢了,要依照資本比例(股份)將賺的錢分給投資者。
但可能會有除不盡的狀況,也沒辦法開個一堆小數點的支票,這時該怎麼分呢?
此時會定義一個最小分配單位,可能是一元、一毛、一分等任何數字。台幣來說應該會用一元。

到此會有幾個關鍵資料:

1. 最小分配單位 = p
2. 總盈餘(要被分的錢) = Vs
3. 每個投資者的股份 = Fi
4. 總股份 = Sum(Fi) = Fs
5. 投資者理論分到的盈餘 = Vi = Fi * (Vs / Fs)
6. 投資者因最小分配單位,實際分到的盈餘 = Mi

前五點是已知的,最後一條是我們想算出的部分。

另外,這幾個參數會有一些限制關係:

1. 每個人實際拿到與理論值的差,不應該大於一個最小單位。 Di = | Mi - Vi | < p,
2. 總共分下去的錢,不能超過總盈餘,且剩下的部分不能超過最小分配單位,有多就要分掉。Ms = Sum(Mi) ; Ms <= Vs  && Vs - Ms < p
3. 實際上,總共分下去的錢會等於整數份的最小單位。 Ms = Truncate(Vs / p) * p,Truncate函數為取整數部分、小數部分完全捨棄。這點可以完全涵蓋2.的限制。

當然,我們是來寫程式的,對於分錢這種事,寫個單元測試是應該的。限制關係部分等等可以用來建立單元測試。

以我最近的習慣,我會先用最簡單的方式,建立演算的抽象類別,也就是實踐Strategy Pattern。好吧!打了那麼多字終於要有程式碼了。


public abstract class BaseDivider
{
    /// <summary>依照輸入的比例、總值、與最小單位,傳回分配的結果。</summary>
    /// <param name="totalValue">被分配的總值。</param>
    /// <param name="factors">各單位的權重。</param>
    /// <param name="digits">傳回值中的小數位數。</param>
    /// <returns>依照權重分配總值的結果。</returns>
    public decimal[] Divide(decimal[] factors, decimal totalValue, int digits)
    {
        return divide(factors, totalValue, digits);
    }

    abstract protected decimal[] divide(decimal[] factors, decimal totalValue, int digits);
}

前置作業那麼多,終於要提到我的分法了。不知道有沒有名稱,姑且叫做累進分配法。
原理是依序計算每筆比例,記錄累計理論應分配總金額,也記錄每筆捨入後的已分配總金額。下一筆作累計後捨入,再減掉以分配的部分,就是該筆所能得的金額了!
寫成偽數學式: Mi = ROUND( SUM(V1~Vi) - SUM(M1~M(i-1))  )
看不懂也沒關係,因為我也是隨興寫的。看看以下程式碼比較清楚:
 


public class MyDivider1 : BaseDivider
{
    sealed protected override decimal[] divide(decimal[] factors, decimal totalValue, int digits)
    {
        // 邊界檢查
        if (factors == null)
            throw new NullReferenceException();
        if (factors.Length == 0)
            return new decimal[0];

        decimal[] values = new decimal[factors.Length];
        decimal fSum = factors.Sum();
        if (fSum == 0)
            throw new Exception("factors sum = 0");
        // 每單位能分配到的量
        decimal valueUnit = totalValue / fSum;
        // 紀錄累進量
        var sumValue = 0M;
        // 紀錄已分配的量, 為Round後真正發出的量
        var sharedValue = 0M;
        int i = 0;
        foreach (var _f in factors)
        {
            // 將目前權重的量累計
            sumValue += valueUnit * _f;
            // Round後才是真正可發的部分
            var new_sharedValue = Math.Round(sumValue, digits, MidpointRounding.AwayFromZero);
            // 新的可發部分 - 上次發掉的部分 = 當前筆能分配到的
            values[i++] = new_sharedValue - sharedValue;
            sharedValue = new_sharedValue;
        }
        return values;
    }
}

已通過單元測試,測試程式碼在這邊

既然單元測試(裡面包括一些簡單的大量測試)通過了,表示符合了限制條件的正確性,那為什麼不能使用呢?
因為有些合理性上的問題。
你讓三個持有20%股份和一個持有40%股份的人,去分1元的獲利,最小單位為1元。印出結果,就會知道為什麼了。
這個問題留待下次再討論。

雖有缺陷,但這個算法在一般的分配狀況下,既快又有效。
另一個重點是,可以輕鬆轉成符合IEnumerable的形式;利用yield return,不需要另外的decimal陣列來存放結果,如下:


public IEnumerable<decimal> Divide(IEnumerable<decimal> factors, decimal totalValue, int digits)
{
    // 邊界檢查
    if (factors == null)
        throw new NullReferenceException();

    decimal fSum = factors.Sum();
    if (fSum == 0)
        throw new Exception("factors sum = 0");
    // 每單位能分配到的量
    decimal valueUnit = totalValue / fSum;
    // 紀錄累進量
    var sumValue = 0M;
    // 紀錄已分配的量, 為Round後真正發出的量
    var sharedValue = 0M;
    foreach (var _f in factors)
    {
        // 將目前權重的量累計
        sumValue += valueUnit * _f;
        // Round後才是真正可發的部分
        var new_sharedValue = Math.Round(sumValue, digits, MidpointRounding.AwayFromZero);
        // 新的可發部分 - 上次發掉的部分 = 當前筆能分配到的
        var _v = new_sharedValue - sharedValue;
        sharedValue = new_sharedValue;
        yield return _v;
    }
}