Project Euler第八題
又係編程解題,先看題目:
題目出自Project Euler第八題,要求找出以上1000位數字之中,任何連續13個數字的乘積的最大值。
這條題目早於2017年就已經解答過並提交了正確的答案。當時的APL程式:
毋庸置疑是一場災難,非常驚嘆自己可以寫出這樣笨的程式,也許出於當時對陣列編程的陌生吧。加上劣拙的英語註解,整片程式與一塊廢鐵無異。當時的思路大致如下:
- 將1000位數字以字串C儲存
- 字串C轉化位1000個元素的陣列D,D的每個元素相當於數字的每個位數
- 將陣列D轉化為12個76行 x 13列的二維陣列(因為1000可以被13整除76次)
- 再將二維陣列的每一行中的13個位數相乘
- 最大的乘積即為答案
時值2020年,再看到同一條題目,我想到的答案卻是:
程式碼可以大量簡化是因為當中使用了"/"運算子。在雙價 (dyadic) 使用下,"/"運算子將左面的函數安插在右面陣列的元素之中,即係函式語言中的還原 (reduction):
以上的表達式,執行起來就好似以下的一樣:
由此可見使用"/"運算子可以大幅簡化程式碼之餘,卻不會犧牲可讀性。更強大的功能係,在函數左方加入數字引數,可以達致區間還原 (partitioned reduction) 如下:
第一個表達式之中,函數 + 並沒有用作還原整條陣列,而是對每三個順序元素還原一次,區間大小由左引數3決定,亦是題解 ⌈/13×/⍎¨C 中 13 的意義。最後用 ⌈ (max) 選出最大的乘積同樣仰賴"/"運算子,將答案之中的程序式 (procedural) 成分完全移除。
留言
張貼留言