Project Euler——Problem 22

daybreakcx posted @ 2009年7月22日 05:50 in Prject Euler , 1030 阅读

原题与答案：

Problem 22

19 July 2002

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Answer:871198282

分析与解答：

这个问题的题意是给定了一个大概64K的文本name.txt（这个文本的链接给出了，这里就不贴了，太废页面空间了），然后里面是一大堆人的名字，然后我们要做的操作是按照字典序排列后然后对每个名字单词求他的分数，分数的计算是每个字母在大写字母表中的排位的和，然后乘以他的序号，求这些分数的和。本身题目的描述把计算过程都给出了，估计这个题目也没有人会笔算吧（那就是神人了），我们就利用程序直接计算，这里只要注意读入的方式，然后排序计算就可以了，程序员源代码如下：

#include<stdio.h>
#include<algorithm>
struct node
{
char str[15];
};
node name[6000];
int i,j,t,ans;
bool cmp(node s,node t)
{
return strcmp(s.str,t.str)<0;
}
int main()
{
freopen("names.txt","r",stdin);
for (i=0;getchar()=='"';i++)
{
for (j=0;(name[i].str[j]=getchar())!='"';j++);
getchar();
name[i].str[j]=0;
}
std::sort(name,name+i,cmp);
ans=0;
for (i=0;name[i].str[0];i++)
{
t=0;
for (j=0;name[i].str[j];j++)
t+=name[i].str[j]-'A'+1;
ans+=t*(i+1);
}
printf("%d\n",ans);
return 0;
}