Litfal的S/L中心

之所以會寫這篇，是因為逛黑暗執行緒時，看到了無尾差分贓法崩壞記。
想到我之前做的一些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;
    }
}