[Project Euler:018]合計が最大になる経路探索問題。
|
Problem 18 31 May 2002 総当たりではなく、賢く解けよ、と指示あり。
|
ProjectEuler
[ リスト | 詳細 ]
コメント（7）
[Project Euler:017]実行結果
|
問題１７ 数値から文字列を割り当ててその文字列数を加算する、という方法を最初考えたのだけど、 それぞれの数字の出現回数を数え上げた方が簡単だと思い直す。 実行結果 Start time =Tue Feb 24 05:19:39 +0900 2009 ans = 21124 End time =Tue Feb 24 05:19:39 +0900 2009 0.013406 passed. process finished. コード
ThousandWord = "thousand"
FirstDigit = ["one","two","three","four","five","six","seven","eight","nine"]
AndWord = "and"
HandredWord = "hundred"
TyWord = ["ninety","eighty","seventy","sixty","fifty","forty","thirty","twenty"]
TeenWord = ["nineteen","eighteen","seventeen","sixteen","fifteen","fourteen","thirteen","twelve","eleven","ten"]
start_time = Time.now
puts "Start time =#{start_time}"
sum = 0
sum += "one".length+ThousandWord.length
FirstDigit.each{|digit|
sum += (digit.length + HandredWord.length + AndWord.length) * 100
}
sum -= AndWord.length*9
TyWord.each{|ty| sum += ty.length*10*10}
TeenWord.each{|teen| sum += teen.length * 10}
FirstDigit.each{|digit|
sum += digit.length * 10 * (10-1) #teenのときのカウントを削除
}
puts "ans = #{sum}"
end_time = Time.now
puts "End time =#{end_time}"
puts "#{end_time - start_time} passed. process finished."
|
[Project Euler:017]
|
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. もし、１から５までの数字が英単語で書かれていたら、合計で19文字になります。 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. 空白やハイフォンは数えません。例えば、342 (three hundred and forty-two)は、23文字、115 (one hundred and fifteen)は20文字です。andを使う場合はイギリス流に従います。 あー、こういうの、嫌い。
|
[Project Euler:016]2^1000の計算結果の各桁の数値の合計
|
Problem 16 03 May 2002 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 2^1000? Rubyだと、この計算もあっさり計算してくれるので、あとは合計をとるだけか。 2^1000の計算結果 ans = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 コード
start_time = Time.now
puts "Start time =#{start_time}"
temp = 2**1000
sum = 0
while temp != 0
digit = temp % 10
sum += digit
temp /= 10
end
puts "ans = #{sum}"
end_time = Time.now
puts "End time =#{end_time}"
puts "#{end_time - start_time} passed. process finished."
|
[Project Euler:015]20x20グリッドを通る経路の総数
|
問題15 一般式を立てて回答する方法をアドバイスいただいていたが、昨夜既に泥臭く（と言い訳する）解くコードを書いていたので、これで良しとする。ただ、一般式を立てるスキルは絶対に今後必要になるな、と肝に銘じておく。忘れそうだけど。 この問題、ポリアによる組合せ論入門の冒頭の問題だ。 実行結果 （前略） ans = 137846528820 End time =Mon Feb 23 10:25:18 +0900 2009 0.086589 passed. process finished. コード
def routes(n,m)
matrix = []
for i in 0..((m+1)*(n+1)-1)
if i == 0 then
matrix << 0
elsif i % (m+1) == 0 then
matrix << 1
end
matrix << 1 if (i>0 && i<=m)
matrix << matrix[i-1]+matrix[i-(m+1)] if (i%(m+1)!=0 && i>m)
puts "matrix[#{i}]=#{matrix.last}"
end
return matrix[(n+1)*(m+1)-1].to_i
end
start_time = Time.now
puts "Start time =#{start_time}"
row = 20
col = 20
puts "ans = #{routes(row,col)}"
end_time = Time.now
puts "End time =#{end_time}"
puts "#{end_time - start_time} passed. process finished."
|
