Problem 42 Coded triangle numbers

Problem

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); 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 19 + 11 + 25 = 55 = t10. 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?

分析

判断一个单词是不是三角单词,即该单词的所有字母对应的数字(A->1 B->2…)之和(成为单词的value)是不是一个三角数。三角数即n(n+1)/2 的数。

方法: 使用一个set集合将所有可能的三角数保存起来。所谓可能,就是小于words.txt中最长的单词的长度len和27的积。然后从words.txt中分割出每一个单词,统计它的value是不是在set中,在则表示是三角单词,计数+1.

C\C++

方法1 [思路同分析] 使用vector和set存储,使用getline()分隔单词

read_data()函数读取words.txt中所有单词到vector容器words中,并且记录最长的单词的长度max_len。其中getline(fin,word,’,’) 从fin文件流中读取一行,以逗号, 为分割。

value(string word) 函数得到单词word的所有字母之和。

process() 函数统计三角单词数。首先,构造所有可能的三角数的集合triangle_numbers,上界是max_len * 27 ;然后遍历words,判断每一个单词是否在triangle_numbers中,在则cnt+1.

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>

using namespace std;

int max_len = 0;        //最长单词的长度
vector<string> words;   //保存所有单词

/************************************************************************
 * 从文件中读取所有的单词到words容器中,并得到最长单词的长度max_len
 ************************************************************************/
bool read_words()
{
	ifstream fin("words.txt");
	string word;
	while(getline(fin,word,',')) //,号分隔
	{
		//去除单词两边的引号,"HELLO" -> HELLO
		word = word.substr(1,word.length()-2);

		//记录最长的单词的长度
		if(word.length() > max_len) max_len = word.length();

		//保存到容器
		words.push_back(word);
	}
	return true;
}

/************************************************************************
 * 返回单词的值
 ************************************************************************/
int value(string word)
{
	int sum = 0;
	for (int i=0;i<word.length();i++)
	{
		sum += word[i]-'A' + 1;
	}
	return sum;
}

/************************************************************************
 * 统计三角单词的数目
 ************************************************************************/
int process()
{
	//构造所有可能的三角数的集合
	int upper_limit = max_len * 27;
	set<int> triangle_numbers;
	for (int n=1;;n++)
	{
		int num = n*(n+1)/2;
		triangle_numbers.insert(num);
		if (num >= upper_limit) break;
	}

	//统计三角单词的个数
	int cnt = 0;
	for (int i=0;i<words.size();i++)
	{
		int v = value(words[i]);                          //得到单词的value
		set<int>::iterator it = triangle_numbers.find(v); //查找集合
		if (it != triangle_numbers.end())    //找到
		{
			cnt ++;
		}
	}

	return cnt;

}
int main()
{
	read_words();
	cout<<process()<<endl;
	return 0;
}

Python

方法1  [思路同分析] 使用列表和set集合

download() 函数 从网上将words.txt文件下载到本地。process() 函数统计三角单词的数目,它首先从words.txt中读取所有的单词,然后去掉双引号”,然后根据,号分割出每个单词保存到words列表中,接着,构造了一个包含了所有可能三角数的set集合triangle_words,继而,判断每个words元素的值是不是在triangle_words中,在则cnt+1。最后输出cnt。ord()函数返回字母对应的ASCII码。

import os, urllib2

def download():
    '''download the file words.txt'''
    if os.path.isfile('words.txt'):
        print 'File already Existed'
    else:
        #download
        print 'Start Downloading...'
        url = 'http://projecteuler.net/project/words.txt'
        request = urllib2.Request(url)
        response = urllib2.urlopen(request)
        f = open('words.txt', 'w')
        f.write(response.read())
        f.close()
        print 'Downloading OK'

def process():
    '''do the process ,return the count of triangle words'''
    #read from the file
    f = open('words.txt', 'r')
    content = f.read()
    f.close()

    #split out each word
    words = content.replace(r'"','').split(',')  # remove "" and then split by ,

    #construct the set contains all the triangle number
    max_len = max([len(i) for i in words])        #max length of all words
    upper_limit = max_len * 27

    n = 1
    triangle_words = set()
    while True:
        num = n * (n + 1) / 2
        triangle_words.add(num)
        if num > upper_limit:
            break
        n += 1
    print triangle_words

    #count
    cnt = 0
    for w in words:
        # ord('A') = 65 --> 1 = 65 - 64
        value = sum([ord(i) - 64 for i in w])
        if value in triangle_words:
            cnt += 1
    print 'count=',cnt

if __name__ == "__main__":
    download() #download words.txt
    process()  #get the answer

答案

162

知识点

作者:JarvisChu
原文链接:Problem 42 Coded triangle numbers
版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0

发表评论