论坛 › 欧拉计划（Project Euler） › 题目42：这个英语词列表里共有多少个三角形词？

欧拉计划 发表于 2015-5-2 12:11:29

题目42：这个英语词列表里共有多少个三角形词？

本帖最后由 欧拉计划 于 2015-5-2 12:20 编辑

Coded triangle numbers

Theterm of the sequence of triangle numbers is given by, ; so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is   If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
题目：

三角形数序列中第 n 项的定义是：；此前十个三角形数是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

通过将一个单词中每个字母在字母表中的位置值加起来：我们可以将一个单词转换为一个数。例如，单词 SKY 的值为如果单词的值是一个三角形数，我们称这个单词为三角形单词。

（右键另存为）是一个 16K 的文本文件，包含将近两千个常用英语单词。在这个文件中，一共有多少个三角形词？

迷雾少年 发表于 2016-8-30 13:58:52

不是很懂题目意思。。

愤怒的大头菇 发表于 2016-9-7 12:49:38

dic = {
      'A':1,
      'B':2,
      'C':3,
      'D':4,
      'E':5,
      'F':6,
      'G':7,
      'H':8,
      'I':9,
      'J':10,
      'K':11,
      'L':12,
      'M':13,
      'N':14,
      'O':15,
      'P':16,
      'Q':17,
      'R':18,
      'S':19,
      'T':20,
      'U':21,
      'V':22,
      'W':23,
      'X':24,
      'Y':25,
      'Z':26}

def San():
      list1 = []
      for i in range(10000):
            list1.append(i*(i+1)/2)
      return list1
list1 = []
f = open('word.txt')
for word in f:
      str_1 = ''
      for each in word:
            if each != '"':
                  str_1 += each
      list1.append(str_1)
count = 0
list2 = []
for each in list1:
      for i in each:
            if i == ',':
                  list2.append(count)
                  count = 0
            else:
                  count += dic
list2.append(count)

list3 = San()
total = 0
for each in list2:
      if each in list3:
            total += 1
print(total)

答案：162

飘飞的白杨 发表于 2016-10-8 11:31:40

count = 0 #用于记数
num = lambda s: sum(int(ord(i))-64 for i in s) #计算每个单词的值
list0 = #生成一个三角数的list
with open("p042_words.txt","r") as f:
    text = f.read()
for x in text.replace("\"","").split(","): #对文本处理，生成单词列表
    if num(x) in list0:
      count += 1
print(count)

芒果加黄桃 发表于 2017-1-15 11:43:16

# encoding:utf-8
# 查找三角形单词个数
from time import time
def euler042():
    l_trinum =
    d_abc = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
    count = 0
    with open('p042_words.txt') as f:
      l_text = f.read().replace('\"', '').split(',')
    for each in l_text:
      w_n = 0
      for t in :
            w_n += d_abc.get(t)
      if w_n in l_trinum:
            count += 1
    print(count)   
if __name__ == '__main__':
    start = time()
    euler042()
    print('cost %.6f sec' % (time() - start))

162
cost 0.007988 sec

渡风 发表于 2017-6-12 22:44:37

%% Problem42.m
%最后编辑时间：2017-06-12 22:10 版本1.0
%找出转换值为三角形数值得单词数
% Problem42所用时间为0.17588秒
% Problem42的答案为162
%% Problem42.m
%最后编辑时间：2017-06-12 22:10 版本1.0
%找出转换值为三角形数值得单词数
% Problem42所用时间为0.17588秒
% Problem42的答案为162
function Output = Problem42()
tic
Output = 0;
Data = importdata('p042_words.txt');
Data = cell2mat(Data);

Qua = 0;             %引号个数
QuaLoca = [];      %引号位置
for ii = 1:length(Data)
    if strcmp(Data(ii),'"') == 1
      Qua = Qua + 1;
      QuaLoca = ;
    end
end

Words = cell(1, Qua /2);
for jj = 1:length(Words)
    Words{jj} = Data(QuaLoca(jj*2-1)+1 : QuaLoca(jj*2)-1); %提取两个引号之间的字母
    ifIsTriNum(Words{jj}) == 1;
      Output = Output + 1;
    end
end

toc

disp('此代码使用matlab编程')
disp(['Problem42所用时间为',num2str(toc),'秒'])
disp(['Problem42的答案为',num2str(Output)])
end
%% 输入一个字母判定其是否为判定它是否为三角形数
function Output = IsTriNum(Input)
if nargin == 0
Input = 'JK';
end
Letter = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];


InputScore = 0;
for ii = 1:length(Input)
    for jj = 1:26
      if strcmp(Input(ii),Letter(jj))
            InputScore = InputScore + jj;
            break
      end
    end
end

n = floor(sqrt(InputScore * 2));

if InputScore * 2 == n*(n+1)
    Output = 1;
else
    Output = 0;
end
end

najin 发表于 2017-9-30 10:54:03

用的matlab
结果是：
>> Untitled

count =

   162

时间已过 0.007360 秒。
>>

k往事如烟k 发表于 2019-3-29 14:55:29

def t(n):
    return n*(n+1)//2

path = r"E:\Python EX\Euler Project\p042_words.txt"
with open(path, "r") as f:
    words = f.read()
wordsList = words.strip('"').split('","')

wordsValueList = []
for each in wordsList:
    sum = 0
    for i in range(len(each)):
      sum += (ord(each)-ord("A")+1)
    wordsValueList.append(sum)

triNumList = []
for i in range(1, 100):
    if t(i) <= max(wordsValueList):
      triNumList.append(t(i))
    else:
      break

finalWordsList = []
for each in wordsList:
    sum = 0
    for i in range(len(each)):
      sum += (ord(each)-ord("A")+1)
    if sum in triNumList:
      finalWordsList.append(each)

print(len(finalWordsList))
162.....写的感觉有点重复~~~太丑了

王小召 发表于 2019-6-14 15:06:52

本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:39 编辑

共有：162 个
用时：0.1404009 秒

import math
import functools
import time


def trangle_num(num):
    if int(math.sqrt(8*num + 1)) == math.sqrt(8*num + 1):
      return True


def cal_result():
    count = 0
    with open(r"C:\Users\wangyongzhao\Desktop\p042_words.txt") as f:
      for each_word in for each in f.read().split(",")]:
            if trangle_num(functools.reduce(lambda x, y: x + y, )):
                count += 1
    return count

print("共有：{} 个\n用时：{} 秒".format(cal_result(), time.process_time()))

debuggerzh 发表于 2020-8-11 17:29:32

162

Process returned 0 (0x0)   execution time : 0.054 s
Press any key to continue.
又可以利用Excel VBA处理源文件使之易于输入
Public Sub PE42()
    Open "C:\Users\zcfcf\Desktop\words.txt" For Input As #1
    Dim s As String
    Dim cnt As Integer
    cnt = 1
    Do Until EOF(1)
      Input #1, s
      Range("a" & CStr(cnt)).Value = s
      cnt = cnt + 1
    Loop
    Close #1
End Sub

接着利用ASCII码天然的编码特性计算单词的值，并加以统计
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;

const int a[] = {1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136,
                153, 171, 190, 210, 231, 253, 276, 300, 325, 351};

int calc(const string & s){
int res = 0;

for (int i = 0;i < s.length();i++)
    res += s - 'A' + 1;

return res;
}

int main(){
freopen("i.in","r",stdin);
string s;
int cnt = 0;

while(cin >> s){
    int t = calc(s);
    for (int i = 0;a <= 351;i++)
      if (t == a){ cnt++;    break; }
}

cout << cnt << endl;
return 0;
}

永恒的蓝色梦想 发表于 2021-1-11 15:54:56

本帖最后由 永恒的蓝色梦想 于 2021-3-6 10:40 编辑

#include<iostream>
#include<fstream>
#include<cmath>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    ifstream file("p042_words.txt");
    unsigned int val, count = 0;
    char ch;


    while (file) {
      if (file.get() == '"') {
            if (file) {
                for (val = 0; (ch = file.get()) != '"'; val += ch - 'A' + 1);
                count += !fmod(sqrt((val << 3) | 1), 1.0);
            }
            else {
                break;
            }
      }
    }


    file.close();
    cout << count << endl;
    return 0;
}

a1351468657 发表于 2021-3-20 12:17:55

#include <stdio.h>
#include <math.h>

int check_trinum(int);
int check_trinum(int num)//判断是否为三角形数
{
        int i, j, k;
        j = sqrt(2 * num);
        for (i = j; i >= 1; i--)
        {
                k = i * (i + 1) / 2;
                if (k == num)
                {
                        return 1;
                }
        }
        return 0;
       
}
main()
{
        FILE *fp;
        int i = 0, j, k, n, count = 0;
        char ch, word;
        fp = fopen("words.txt", "r");
        while (!feof(fp))//将文件中名字写入字符串数组word中
        {
                ch = fgetc(fp);

                if (ch == '"')
                {
                        j = 0;
                        continue;
                }
                else if (ch == '\n')
                {
                        continue;
                }
                else
                {
                        if (ch == ',')
                        {
                                i++;
                        }
                        else if (ch >= 'A' && ch <= 'Z')
                        {
                                word = ch;
                                word = '\0';
                                j++;
                        }
                }       
        }
        fclose(fp);
        k = i;
        for (i = 0; i <= k; i++)
        {
                n = 0;
                for (j = 0; word != '\0'; j++)
                {
                        n += (word - 64);//因为'A'的acsii码为65，所以减去64就是字母在字母表的位置
                }
                if (check_trinum(n))
                {
                        count++;//记录三角形词的个数
                }
        }
        printf("%d", count);
}

162

ft215378 发表于 2021-10-21 19:25:26

#共有多少个三角形词
'''
角形数序列中第 n 项的定义是：Tn = 1/2n(n+1)；此前十个三角形数是：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
'''
from time import *
#生成n项三角形数序列
def creat_triangle_numlist(n):
    triangle_numlist = []
    for i in range(1, n+1):
      triangle_numlist.append((i * (i+1)) // 2)
    return triangle_numlist

def get_letter_value(letter):
    letter_dic = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9\
                  , 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, \
                  'Q':17 , 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, \
                  'X':24, 'Y':25, 'Z':26}
    return letter_dic

#处理文件获得文本
with open("c:\\Users\\Administrator\\Desktop\\word.txt") as f:
    word_str = f.read()

start = time()
#处理字符串
word_list = word_str.split(',')

#计算多少三角形词
count = 0
each_sum = 0
word_value = []
for each in word_list:
    each = each.replace('"', '')
    for i in each:
      each_sum += get_letter_value(i)
    word_value.append(each_sum)
    each_sum = 0
#print(max(word_value)) 129160
#'''

triangle = creat_triangle_numlist(1000)
result = []
for each in word_value:
    if each in triangle:
      result.append(each)
      count += 1
    else:
      continue
end = time()
print(count)
print("用时%4f秒" % (end-start))

B1tetheDust 发表于 2022-10-24 19:55:56

import time as t
import numpy as np

start = t.perf_counter()


def is_triangle_number(tn):
    n = int(np.sqrt(2 * tn))
    if 2 * tn == n * (n + 1):
      return True
    else:
      return False


names = np.loadtxt("C:/Users/wuhw/Desktop/p042_words.txt", dtype=str, delimiter=',')
name_list = []
count_nums = 0
for name in names:
    name_list.append(name.strip('"'))
for each in name_list:
    name_value = sum()
    if is_triangle_number(name_value):
      count_nums += 1

print(count_nums)
print("It costs %f s" % (t.perf_counter() - start))



162
It costs 0.009455 s

查看完整版本: 题目42：这个英语词列表里共有多少个三角形词？