Project Euler——Problem 17 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 16
Project Euler——Problem 18

Project Euler——Problem 17

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

原题与答案:

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),累加,源代码如下:

 

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

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter