分類: 程式

#152 Writing 1/2 as a sum of inverse squares (難度 65%)

這題躺在我的未解題裡躺很久了：有一陣子我在嘗試從頭開始答題，寫一寫就撞上這題這個軟牆，所以就開始往後亂跳題目 XD 也就是說，除了在約三四百題那附近時有比較集中在一出題就去解之外，其他的解題進度都是這樣散散的，看到有點難的題目就給它拼命跳，所以這題才留著這麼久。

題目很簡單：就如同標題說的，把 1/2 寫成不同整數平方的倒數和。題目敘述給了一個範例：

$$\begin{align}\dfrac{1}{2} &= \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dfrac{1}{4^2} + \dfrac{1}{5^2} +\\
&\quad \dfrac{1}{7^2} + \dfrac{1}{12^2} + \dfrac{1}{15^2} + \dfrac{1}{20^2} +\\
&\quad \dfrac{1}{28^2} + \dfrac{1}{35^2}\end{align}$$

並且給出如果只考慮 2 到 45 的平方倒數的話，連同這個範例一共只有三組解。題目要問的是：如果放大範圍到 2 到 80 的話有幾組解？

之所以是軟牆是因為，2 到 80 這個範圍很微妙的稍微大了一點；這個題目本質上是一個子集和問題，要我們在給定的 79 個元素中選出數個來加到目標 1/2；由於子集和問題是著名的 NP-Complete 問題，所需要的工作量不會比把 79 個數個別選不選所得到的 \(2^{79}\) 種選項逐一嘗試來得好多少。

Continue reading “Project Euler 解題筆記 (2)”

既然要來記解題筆記就來順便記一下時不時會做的 Project Euler 好了。這裡的文章應該會一起排進慣例的週三更新當中，所以看到一篇筆記出來並不代表我剛解完這一題，而可能是好幾天前的事了 XD

我做 Project Euler 主要的工具是 Mathematica，因為很多數學相關的東西可以不用我自己寫；只有在一些資料結構用 MMA 不好寫或很需要效率的時候才會轉用 C++ 來寫的。我的 PE 帳號裡登記的使用語言也是 Mathematica。

另外，為了在全文章模式也作點簡單的防雷，每篇在討論的題目我會放在繼續閱讀之上，然後在前面寫一點這題可以公開的東西，例如簡評或我流翻譯等；在繼續閱讀的前一段我會放上我的 Project Euler 簽名圖，那之下就會來開始放雷了。

#168 – Number Rotations (難度 65%)

簡述這題是這樣的：
142857 這個數字，將其個位數放到最前面 (稱為其右旋轉) 得到 714285，而我們發現 714285 是 142857 的 5 倍整。試問，所有具有此種性質－－一數為其右旋轉的因數－－並且在 10 到 10¹⁰⁰ 之間的數的總和，其末五位是多少？

這題其實很久以前解過，但因為少考慮了一個東西所以 WA 了不少次，就被我放著了。最近回來重新思考才發現我少考慮的東西是什麼－－而說來有趣，題目用 142857 舉例正是讓我掉進這個陷阱的元兇 XD

Continue reading “Project Euler 解題筆記 (1)”