Project Euler——Problem 17

daybreakcx posted @ 2009年7月19日 17:47 in Prject Euler , 1207 阅读

原题与答案：

Problem 17

17 May 2002

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Answer:21124

分析与解答：

这个题目是到现在为止最为恶心的题目，是求1到1000所构成的英文单词除掉空格的总长度。当然是可以笔算的，但是最麻烦的是去数单词的长度（我不喜欢英语）。笔算的过程很多种，我介绍一下我自己的吧，首先是1到9的总长度=3+3+5+4+4+3+5+5+4=36，然后是10到19总长度=3+6+6+8+8+7+7+9+8+8=70，接着从20到99都有规律可循了，20到90所有10倍数的单词总长度=6+6+5+5+5+7+6+6=46，而个位都是1到9，于是1到99的总长度=36×9+70+46×10=854。伴随1到999，1到99总是一轮轮出现的，总次数是10次，因此十位和各位总长度=854×10=8540。接下来就是百位了，百位有点麻烦，虽然是1到9数字每个各出现了100次，但是还有单词"hundred"，此外还有"and"，但是不影响计算，百位总长度=36×100+7×900+3×9×99=12573。于是就得到了1到999的总长度=8540+12573=21113。最后加上单词"onethousand"，那么我们得到的答案=21113+11=21114。我的程序稍微偷懒了一下，用了枚举各个位的情况（等于枚举了1到999），累加，源代码如下：

#include<stdio.h>
#include<string.h>
int ans=0,ones[10]={0,3,3,5,4,4,3,5,5,4},tens[10]={0,0,6,6,5,5,5,7,6,6},ten[10]={3,6,6,8,8,7,7,9,8,8},i,j,k;
int main()
{
for (i=0;i<10;i++)
for (j=0;j<10;j++)
for (k=0;k<10;k++)
{
if (j!=1) ans+=ones[i]+tens[j]+ones[k];
else ans+=ones[i]+ten[k];
if (i) ans+=10;
if (i&&j+k==0) ans-=3;
}
printf("%d\n",ans+strlen("onethousand"));
return 0;
}