问题
第n个三角数由公式\(t_n = \frac{1}{2} n(n+1)\)定义;所以前十个三角数如下:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
将一个英语单词的每个字母的字母顺序当作数值,然后将它们相加,得到的值我们称它为单词的值。例如,SKY的值就是\(19+11+25 = 55 = t_{10}\)。如果一个单词的值刚刚好就是一个三角数,那么我们称它为三角词。
在这个words.txt(右键保存链接/目标为…)16K文本文件中包含大约2000个英语单词,它们当中有多少个三角词?
* 传送门
分析
简单直接的问题。判断是否三角数,将三角数的生成公式改为一元二次方程\(n^2 + n – 2t = 0\),即判断n是否有正整数解。n的通解为\(n = \frac{-1 ± \sqrt{1+8t}}{2}\)。只考虑正整数解,所以只考虑\(n = \frac{-1 + \sqrt{1+8t}}{2}\)的情况。
答案
// answer: using formula
const $ = jQuery
const char_base = 'A'.charCodeAt(0) - 1
function alphabetical_value(word) {
let result = 0
for (let i = 0; i < word.length; ++i)
result += word.charCodeAt(i) - char_base
return result
}
function is_triangle_word(word) {
const word_value = alphabetical_value(word)
return is_triangle_number(word_value)
}
function is_triangle_number(t) {
const n = (Math.sqrt(1+8*t)-1)/2
return Math.floor(n) == n
}
$.get('/_x_.php?' + $('#p042_words').attr('href'), function(txt) {
const start = Date.now()
const words = JSON.parse('[' + txt + ']')
let result = 0
for (const word of words)
if (is_triangle_word(word))
result++
alert(result + ', ' + (Date.now() - start) + 'ms')
})
打赏作者