题目链接:https://projecteuler.net/problem=42
三角形数序列中第 n 项的定义是: tn = ?n(n+1)
26个字母对应其依次出现的顺序,如A:1,B:2
如果一个单词,各个字母对应数字之和在三角形数序列中,则这个单词是三角形单词。
求给的txt文件中有多少个单词
思路:
1.读取txt文件
2.判断是否是三角形单词
3.统计个数
如何判断是三角形单词?
1.求出单词对于的数是多少,这个比较简单
2.判断这个数是否在三角形数序列中
如何判断一个数是在三角形序列中?
1.暴力破解
对1到n的数分别求?n(n+1) 若等于所要判定的数,则是三角形数。
太暴力,时间长,本题让判断的数有2000左右的。
2.巧解
tn = ?n(n+1),我们假设输入的数num是三角形数,则num= ?n(n+1),根据这个我们可以求出n,再判断n对于的真实的三角形数tn是否等于num,等于则是三角形数。
n=1+8tn√?12 OK
或
n=?1+8tn√?12 显然不对,都小于0了
这个也可以,比方法一好多了
3.不直接求n
num= ?n(n+1)
2*num=n*n+n
看到这个式子,突然感觉当n趋向无穷大时候 2*num = n * n
2*num = n * n 是关键
所有 n=sqrt(2*num) 四舍五入
这里的问题要是n是很大的数才满足条件
手工试了下,发现n=1到10都满足。为什么?
我们可以考虑下面两个数的关系,左边的是我们认为的n,右边实际的n,假设小于
2?num???????√ <