--- id: 5900f37a1000cf542c50fe8d title: '問題 14:最長考拉茲序列' challengeType: 5 forumTopicId: 301768 dashedName: problem-14-longest-collatz-sequence --- # --description-- 對正整數集定義如下迭代序列:
nn / 2(n 爲偶數)
n → 3n + 1(n 爲奇數)
從 13 開始使用上述規則,我們可以得到如下序列:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
可以看出,該序列(從 13 開始到 1 結束)共包含 10 項。 雖然考拉茲猜想尚未得到證明,但是該猜想認爲以任意數字開始,序列均到 1 結束。 求出在小於 `limit` 的數中,哪個可以產生最長的考拉茲序列? **注意:** 序列中數字的個數允許超過一百萬。 # --hints-- `longestCollatzSequence(14)` 應該返回一個數字。 ```js assert(typeof longestCollatzSequence(14) === 'number'); ``` `longestCollatzSequence(14)` 應該返回 9。 ```js assert.strictEqual(longestCollatzSequence(14), 9); ``` `longestCollatzSequence(5847)` 應該返回 3711。 ```js assert.strictEqual(longestCollatzSequence(5847), 3711); ``` `longestCollatzSequence(46500)` 應該返回 35655。 ```js assert.strictEqual(longestCollatzSequence(46500), 35655); ``` `longestCollatzSequence(54512)` 應該返回 52527。 ```js assert.strictEqual(longestCollatzSequence(54512), 52527); ``` `longestCollatzSequence(100000)` 應該返回 77031。 ```js assert.strictEqual(longestCollatzSequence(100000), 77031); ``` `longestCollatzSequence(1000000)` 應該返回 837799。 ```js assert.strictEqual(longestCollatzSequence(1000000), 837799); ``` # --seed-- ## --seed-contents-- ```js function longestCollatzSequence(limit) { return true; } longestCollatzSequence(14); ``` # --solutions-- ```js function longestCollatzSequence(limit) { let longest = 1; let maxLength = 1; for (let i = Math.floor(limit / 2); i < limit; i++) { let len = colLen(i); if (len > maxLength) { longest = i; maxLength = len; } } return longest; } const knownSequence = { '1': 1 }; function colLen(n) { if (knownSequence[n]) { return knownSequence[n]; } else { const len = n % 2 === 0 ? colLen(n / 2) + 1 : colLen((3 * n + 1) / 2) + 2; knownSequence[n] = len; return len; } } ```