当前位置: 代码迷 >> 综合 >> 欧拉工程第42题:Coded triangle numbers
  详细解决方案

欧拉工程第42题:Coded triangle numbers

热度:35   发布时间:2023-12-13 07:14:06.0

题目链接: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??????? <