Coding4Fun-K Sum問題求解

2014-09-21 11:40 PM

小學一年級生數學題目一枚：

請從 1 - 10 取出 4 個數字，4 個數字不可重複，總和必須為 15。例如：1, 2, 3, 9。

答案紙有七組空格，嘗試排列組合卻只能找到六組，小朋友心靈受挫，也成了大人間的討論話題。大家紛紛手算，「只有六組解」幾乎已成共識。但，程式魔人壓根沒算，而始默默在心中草擬演算法，決心要搞支程式暴力破解兼練功。

在FB專頁貼了題目，看到上官神人留言才知這問題在電腦科學領域很有名，是複雜度理論（Complexity Theory）與密碼學（Cyptography）裡重要的數學問題－ Subset Sum Problem。維基百科裡還提到 Q(i,s) := Q(i − 1,s) or (x_i == s) or Q(i − 1,s − x_i) for A ≤ s ≤ B 之類的數學公式，害我有點昏眩。我對數學理論全無興趣，純粹喜歡想方法用程式解決問題。（當年若真唸了資工、資科，會不會被離散數學、資料結構的一堆公式擊倒，頓失寫程式的熱情呢？）

不懂理論無妨，這問題難不倒有經驗的老鳥，就算不花太多腦筋，用「愚公移山」都可搞定。跑幾個迴圈湊數字，為避免數字順序換調的組合重複出現，限定後方數字一定要比前方大。而第四位不需要跑迴圈，直接用總和15反推即可。簡單幾行，程式完成！

using System;

using System.Linq;

using System.Collections.Generic;

using System.Diagnostics;

public class Program

    class AnswerFinder

        public List<string> Answers = new List<string>();

        public void Explore()

            for (int i = 1; i <= 9; i++)

                //限定後一位數字要比前一位大

                for (int j = i + 1; j <= 9; j++)

                    for (int k = j + 1; k <= 9; k++)

                        if (k == j || k == i) continue;

                        int l = 15 - k - j - i; //計算湊成15所需的第四位數字

                        if (l <= k) continue; //第4位數字不得小於前一位

                        if (l < 1) break; //前三位數字已過大，中斷k迴圈

                        if (l == k || l == j || l == i) continue; //與前面數字重複

                        Answers.Add(string.Format("{0}{1}{2}{3}", i, j, k, l));

    public static void Main(string[] args)

        AnswerFinder t = new AnswerFinder();

        Stopwatch sw = new Stopwatch();

        sw.Start();

        t.Explore();

        sw.Stop();

        Console.WriteLine("Done! {0} answers found in {1:n0}ms.",

                          t.Answers.Count, sw.ElapsedMilliseconds);

        Console.WriteLine(string.Join("\n", t.Answers.ToArray()));

        Console.Read();

執行結果瞬間噴出：

Done! 6 answers found in 0ms.
1239
1248
1257
1347
1356
2346

問題已輕鬆解決，但對程式魔人尚未達止癢效果。前述做法寫死數字位數（4）、數字範圍（1-9），只有總和可調。如果題目改成 8 位數字，數字範圍 1-32，總和 128，得 i, j, k, l, m, n, o 一路寫到到 p，搞出七層巢狀迴圈，而且位數長度一改程式就得重寫…

俗話說：「迴圈只應凡間有，魔人該當用遞迴」

遞迴上場的時間到了！

我想了一個以 Stack 為核心的演算法，將數字長度、範圍、總和都改為可調參數，每 Push 進一個數字，就重算下一個可 Push 數字的範圍（不得小於前一位數字，不得大於數字範圍上限並考慮總和不可破表），依依序 Push 範圍內的可用數字，再重算下一位的數字範圍，依序 Push…，直到只剩一位數字要填時，再以總和反推求解。當下一位已無數字可用，則 Pop 退回上一位繼續嘗試，有點類似探索迷宮路徑的概念。

程式範例如下：

using System;

using System.Linq;

using System.Collections.Generic;

using System.Diagnostics;

public class Program

    class AnswerFinder

        public static int MaxLength = 4;

        public static int Sum = 15;

        public static int MinNumber = 1;

        public static int MaxNumber = 9;

        public static void Set(int maxLen, int sum, int min, int max)

            MaxLength = maxLen;

            Sum = sum;

            MinNumber = min;

            MaxNumber = max;

        public Stack<int> Digits = new Stack<int>();

        bool lastDigFixed = false;

        int delta = Sum;

        public int Min = MinNumber, Max = MaxNumber;

        public bool Perfect = false;

        private void updateStats()

            int currLen = Digits.Count; //目前數字長度

            lastDigFixed = MaxLength - currLen == 1; //最後一位數確定

            delta = Sum - Digits.Sum(); //目前總和與目標總和的差額

            Perfect = MaxLength == currLen && delta == 0; //是否符合要求

            //下個可用數字為為已使用數字之最大者＋1

            var nextNum = Digits.Max() + 1;

            //若只剩一位且差額在可用數字範圍，以差額為Min；否則取下一可用數字

            Min = lastDigFixed && delta >= nextNum ? delta : nextNum;

            //若只剩一位且差額在可用數字範圍內，以差額為Max；否則取數字上限及差額較小者

            Max = lastDigFixed && delta <= MaxNumber ?

                       delta : Math.Min(MaxNumber, delta);

        public void Push(int num)

            Digits.Push(num); //將數字放進組合

            updateStats();

        public void Pop()

            Digits.Pop(); //將數字從組合換下來

            if (Digits.Count > 0) //長度為0表處理完畢，不需更新統計

                updateStats();

        public List<string> Answers = new List<string>();

        public void Explore()

            //下一位數字可用範圍為Min to Max

            int min = Min, max = Max;

            for (var n = min; n <= max; n++)

                Push(n);

                if (Perfect)

                    Answers.Add(string.Join(", ", Digits.Reverse().ToArray()));

                else

                    Explore();

                Pop();

            return;

    public static void Main(string[] args)

        AnswerFinder.Set(4, 15, 1, 9);

        AnswerFinder t = new AnswerFinder();

        Stopwatch sw = new Stopwatch();

        sw.Start();

        t.Explore();

        sw.Stop();

        Console.WriteLine("Done! {0} answers found in {1:n0}ms.",

                                       t.Answers.Count, sw.ElapsedMilliseconds);

        Console.WriteLine(string.Join("\n", t.Answers.ToArray()));

        Console.Read();

遞迴版本邏輯比較複雜，跑起來比迴圈版慢，4 位數總和 15 需要 5ms 才能算出答案。

Done! 6 answers found in 5ms.
1, 2, 3, 9
1, 2, 4, 8
1, 2, 5, 7
1, 3, 4, 7
1, 3, 5, 6
2, 3, 4, 6

但它的優勢在於參數可調，我們來試試更複雜的題目，例如：1-32，8 位數，總和 224，耗時 3.3 秒得解。

Done! 5 answers found in 3,285ms.
21, 26, 27, 28, 29, 30, 31, 32
22, 25, 27, 28, 29, 30, 31, 32
23, 24, 27, 28, 29, 30, 31, 32
23, 25, 26, 28, 29, 30, 31, 32
24, 25, 26, 27, 29, 30, 31, 32

我對執行效能不滿意，祭出新武器Visual Studio Performance Analyzer，找出效能瓶頸落在 Stack.Max() 及 Stack.Sum() 兩個彙總方法上：

小幅改寫，改用 Stack.Peek() 取最大值（循序 Push，最後一位數字永遠最大）會比 .Max() 有效率；另外，每次 Push 及 Pop 時改為自行重算數字總和，預期也會比 .Sum() 快：

        int currSum = 0;

        private void updateStats(int sumChange)

            currSum = currSum + sumChange;

            int currLen = Digits.Count; //目前組合的數字長度

            if (currLen == 0) return; //組合已無數字不需重算

            lastDigFixed = MaxLength - currLen == 1; //最後一位數確定

            delta = Sum - currSum; //目前總和與目標總和的差額

            Perfect = MaxLength == currLen && delta == 0; //是否符合要求

            //下個可用數字為為已使用數字之最大者＋1

            var nextNum = Digits.Peek() + 1;

            //若只剩一位且差額在可用數字範圍，以差額為Min；否則取下一可用數字

            Min = lastDigFixed && delta >= nextNum ? delta : nextNum;

            //若只剩一位且差額在可用數字範圍內，以差額為Max；否則取數字上限及差額較小者

            Max = lastDigFixed && delta <= MaxNumber ?

                  delta : Math.Min(MaxNumber, delta);

        public void Push(int num)

            Digits.Push(num); //將數字放進組合

            updateStats(num);

        public void Pop()

            int num = Digits.Pop(); //將數字從組合換下來

            updateStats(-num);

改寫後，耗時縮短到 0.8 秒，加快四倍，效果不錯。

Done! 5 answers found in 807ms.
21, 26, 27, 28, 29, 30, 31, 32
22, 25, 27, 28, 29, 30, 31, 32
23, 24, 27, 28, 29, 30, 31, 32
23, 25, 26, 28, 29, 30, 31, 32
24, 25, 26, 27, 29, 30, 31, 32

針對位數、範圍較大的題目，我猜演算法還可以再優化，但再鑽下去已感覺枯躁，失去 Coding4Fun 初衷，就此打住囉～

Live Demo

【後記】回到 4 位1-9 總和 15 的小學數學題，經人腦與電腦驗證，答案確實只有六組，答案紙有七格是怎麼一回事？原來老師的用意是若答案只有六格，小朋友在找出六組答案後就會停止，減少反覆嘗試練習加法的次數，也失去思索「是否答案就只有六組」的機會。嗯，很有教育意涵。

Comments

# 2014-09-21 08:22 PM by 阿多

雖然老師設了七格答案空格立意良好，但造成小朋友心靈受挫似乎也不太好？

# 2014-09-22 02:55 AM by 胡忠晞

用遞迴還要寫這麼長不太優喔! 我也用 JS 小試一下! var values = [0,0,0,0]; function findAns(num, p, remain) { if(remain < 0){ return; } if(p == 0){ if(remain == 0){ console.log('ans: '+values.join()); } return; } /* 利用梯形公式計算最低數值 (lowest + (lowest - p + 1)) * p / 2 = remain */ var lowest = Math.max(1, Math.floor(remain/p + (p-1)/2)); if(num < lowest){ return; } values[p-1] = num; findAns(num-1, p-1, remain - num); findAns(num-1, p, remain); } findAns(10, values.length, 15);

# 2014-09-22 04:10 AM by Jeffrey

to 胡忠晞, 請受小弟一拜！orz

Comments

# 2014-09-21 08:22 PM by 阿多

# 2014-09-22 02:55 AM by 胡忠晞

# 2014-09-22 04:10 AM by Jeffrey

Post a comment