[½»Á÷] Euler Project Q17. Å·À­¹¤³ÌµÚÊ®ÆßÌâ ÒÑÓÐ3È˲ÎÓë

21124
elapsed time=0.000000 seconds.

#include
#include
#include

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();
#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);

static int bufa[]={4,3,3,5,4,4,3,5,5,4,//zero, one, ..., nine,
                  3,6,6,8,8,7,7,9,8,8 };// ten, eleven, ..., nineteen
static int bufc[]={0,0,6,6,5,5,5,7,6,6}; //0, 0, twenty, thirty, ..., ninety

int count(int n){
  if(n<20)return bufa[n];
  if(n<100) {
    if(n%10==0) return bufc[n/10];
    else
      return bufc[n/10]+bufa[n%10];
  }
  if(n<1000) {
    if(n%100==0)
      return bufa[n/100]+7;
    else
      return bufa[n/100]+count(n%100)+10;
  }else if(n==1000) return 11;

  return -1;
}

int euler17(int n){
  int i,sum=0;
  
  for(i=1;i     sum+=count(i);
  
  return sum;
}


int main(void){
  
TIMERSTART;

printf("%d\n",euler17(1000));
  
TIMERSTOP;

  return 0;
}

%% How many letters would be needed to write all the numbers in words from 1 to 1000?
function result = euler17()
tic;
numstr = '';
for i=1:1000
    numstr = [numstr,' ',num2words(i)];
end
numstr = strrep(numstr,' ','');
numstr = strtrim(numstr);
result = length(numstr);
toc;
end

%% write a number in words
% called by euler 17
function result = num2words(num)
key = [1:20,30:10:90];
value = {'one','two','three','four','five','six','seven','eight','nine','ten','eleven','twelve', ...
        'thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen', ...
        'twenty','thirty','forty','fifty','sixty','seventy','eighty','ninety'};
numlist = containers.Map(1,'one'); % must add a value first, then map can hold the right key type
for i=2:length(key)
    numlist(key(i)) = value{i};
end
result = '';
switch length(num2str(num))
    case 4
        if mod(num,1000)==0
            result = [result,numlist(fix(num/1000)),' thousand',num2words(rem(num,1000))];
        else
            result = [result,numlist(fix(num/1000)),' thousand and ',num2words(rem(num,1000))];
        end
    case 3
        if mod(num,100)==0
            result = [result,numlist(fix(num/100)),' hundred',num2words(rem(num,100))];
        else
            result = [result,numlist(fix(num/100)),' hundred and ',num2words(rem(num,100))];
        end
    case 2
        if fix(num/10)==1
            result = [result,numlist(num)];
        else
            result = [result,numlist(fix(num/10)*10),' ',num2words(rem(num,10))];
        end
    case 1
        if num==0
            result = '';
        else
            result = [result,numlist(num)];
        end
    otherwise
        result = '';
end
end

% Elapsed time is 6.267496 seconds.
% ans =
%        21124

#/bin/env python

ones = ["", "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine", "ten",
        "eleven", "twelve", "thirteen", "fourteen",
        "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]

tens = ["", "twenty", "thirty", "forty", "fifty",
        "sixty", "seventy", "eighty", "ninety"]

words = ["", " thousand", " million", " billion"]

def num2words(n):
    "Convert an integer to english words"
    def part(num, s):
        "Convert a part of numbers"
        if num < 20:
            return s + ones[num]

        if num < 100:
            return s + tens[num / 10 - 1] + " " +  ones[num % 10]

        return ones[num / 100] + " hundred " + s + part(num % 100, "")

    # divided into several part
    # each part contain three numbers
    t = 1000
    # results list
    r = []
    i = 0
    while n > 0:
        # add "and" into the word
        if i == 0 and n > 100 and n % 100 != 0:
            r.append(part(n % t, 'and ') + words[i])
        else:
            r.append(part(n % t, "") + words[i])
        n /= t
        i += 1
    r.reverse()
    return r


if __name__ == "__main__":
    s = 0
    for i in range(1, 1001):
        for w in num2words(i):
            s += sum([len(x) for x in w.split()])
    print "total length:", s