« 2009年5月 | トップページ | 2009年7月 »

2009年6月

2009年6月27日 (土)

Project Euler - Problem 23

問題はこちらをご覧ください。


今回は計算時間を短くするために、配列を贅沢に使ってみました。

自作の "math_tool.rb" に関してはこちらをご覧ください。

require 'math_tool' MAX = 28123 integer_arr = (0 .. MAX).to_a abu_arr_a = integer_arr.select{|i| i.abundant?} abu_arr_b = Array.new(abu_arr_a) until abu_arr_a.empty? abu_arr_a.size.times do |i| sum = abu_arr_a[i] + abu_arr_b[i] break if sum > MAX integer_arr[sum] = 0 end abu_arr_a.shift end puts integer_arr.inject(:+) # p integer_arr.select{|i| i > 0}

自分の環境では、Ruby 1.9 で約 7 秒で答が出ました。(本当に配列を贅沢に使った甲斐があったのかな?)

Project Euler - Problem 22

問題はこちらをご覧ください。


Ruby 1.9 では、これまでの Ruby 1.8 系と文字列の扱いが変わってしまいました。機能的には進化しているので喜ばしいのですが、まだ慣れていないので、自分の思ったとおりのコードを書くのが大変です。

To_Num = "A".ord - 1 names = open("names.txt"){|f| f.read}.gsub(/"/, '').split(",") names_v = names.sort.map do |str| str.each_byte.inject(0){|sum, ch| sum = sum + ch - To_Num} end sum = 0 names_v.each_with_index{|v, i| sum = sum + v * (i + 1)} puts sum

Project Euler - Problem 20, 21

自作の "math_tool.rb" に関してはこちらをご覧ください。


Problem 20

Ruby の整数には桁数の制限がないので、この問題は非常に楽に解けます。

require 'math_tool' puts 100.factorial.to_a.inject(:+)

Problem 21

"math_tool.rb" に含まれている "Integer#amicable_pair" を使うと、簡単に友愛数を探せます。

require 'math_tool' arr = (2 .. 10000).select{|i| i.amicable_pair} puts arr.inject(:+)

2009年6月26日 (金)

Project Euler - Problem 19

問題はこちらをご覧ください。


この問題を解くために、Ruby の Date クラスを調べたんですけど、Date クラスのメソッドって、よくできてますよね。

# -*- coding: utf-8 -*- require 'date' d1 = Date.new(1901, 1, 1) # 開始日 d2 = Date.new(2000, 12, 31) # 終了日 sum = 0 d1.upto(d2) do |d| sum = sum + 1 if d.day == 1 and d.sunday? end puts sum

Project Euler - Problem 18

問題はこちらをご覧ください。


まず、最初に考えついた方法。

def select(i, j) return 0 unless $arr[i] v1 = select(i + 1, j) v2 = select(i + 1, j + 1) return $arr[i][j] + [v1, v2].max end $arr = Array.new DATA.each_line do |data| $arr.push(data.chomp!.split.map{|st| st.to_i}) end puts select(0, 0)

三角形の上の方から再帰的に最大値を求めています。

再帰的なアプローチは、終了条件と再帰手続きのルールさえ決めてしまえば終わりなので、慣れると結構簡単にできてしまいます。

しかしこの場合は、結局すべての経路を探索することになるし、メソッドを再帰的に呼び出すコストもかかるので、当然非常に遅くなります。

この問題ではまだいいのですが、Problem 67 を同じ方法で試してみたら、とても遅くて話になりませんでした。


ということで、次に考えたのがこちら

def check(arr1, arr2) ans = arr2.map.with_index do |v, i| v + [arr1[i], arr1[i + 1]].max end return ans end arr = Array.new DATA.each_line do |data| arr.push(data.chomp!.split.map{|st| st.to_i}) end arr.reverse! ans = arr.shift arr.each do |a| ans = check(ans, a) end puts ans[0]

三角形の底辺の方から、隣接する数字のうち大きいものを上の段の数字に足していく方法です。

この方法は、上記の再帰的な方法とは逆に、どんどん候補が減っていくので、Problem 67 のようなデータの数が多い問題でも、非常に速く答が出ます。

2009年6月24日 (水)

Project Euler - Problem 15, 16, 17

Problem 15

この問題は、組み合わせの問題ですね。

require 'math_tool' puts 40.combination_size(20)

Problem 16

Ruby の整数は桁数に制限がないので、この問題は普通に計算するだけですね。

require 'math_tool' puts (2 ** 1000).to_a.inject(:+)

Problem 17

数字を英単語にしたときの文字数だけを数え上げるメソッドを作ってもよかったのですが、「それじゃ面白くない」ので 100 以下の数字の英単語を返すメソッドを作ってみました。

class Integer @@w1_9 = {1 => "one", 2 => "two", 3 => "three", 4 => "four", 5 => "five", 6 => "six", 7 => "seven", 8 => "eight", 9 => "nine"} @@w10_19 = {10 => "ten", 11 => "eleven", 12 => "twelve", 13 => "thirteen", 14 => "fourteen", 15 => "fifteen", 16 => "sixteen", 17 => "seventeen", 18 => "eighteen", 19 => "nineteen"} @@w20_90 = {20 => "twenty", 30 => "thirty", 40 => "forty", 50 => "fifty", 60 => "sixty", 70 => "seventy", 80 => "eighty", 90 => "ninety"} def to_words upper, lower = self.divmod(100) case when upper == 10 upper_words = "one thousand" when upper > 0 upper_words = @@w1_9[upper] + " hundred" else upper_words = "" end case when lower == 0 lower_words = "" when lower < 10 lower_words = @@w1_9[lower] when lower < 20 lower_words = @@w10_19[lower] else r = lower.modulo(10) lower_words = @@w20_90[lower - r] lower_words = lower_words + "-" + @@w1_9[r] if r > 0 end if upper_words.empty? or lower_words.empty? then ans = upper_words + lower_words else ans = upper_words + " and " + lower_words end return ans end end ans = 0 1.upto(1000) do |i| ans = ans + i.to_words.delete(" ").delete("-").size end puts ans

2009年6月22日 (月)

Project Euler - Problem 14

問題はこちらをご覧ください。


有名な「Collatz の問題」です。

以前、この「Collatz の問題」を知ったときに、大変興味深かったので、こんなスクリプトを書いて、いろんな数がどうやって 1 に収束していくかを実験したことがありました。

;; Chez Scheme 版 (define collatz (lambda (n) (let loop ((s 1) (i n)) (printf "step ~3d : ~8d~%" s i) (cond ((= i 1) (printf "終了~%")) ((even? i) (loop (+ s 1) (/ i 2))) (else (loop (+ s 1) (+ (* i 3) 1)))))))

今回は生成される数列の長さだけが必要なので、まずこんなスクリプトを書いてみました。

MAX = 100_0000 max = [1, 1] 2.upto(MAX - 1) do |n| v = n c = 1 begin if v.even? then v = v / 2 else v = v * 3 + 1 end c = c + 1 end until v == 1 max = [n, c] if c > max[1] end puts max[0]

このスクリプトは真面目にすべての数を計算するので、非常に遅いです。

Ruby 1.9 で 34 秒ほどかかりました。


ところで、この「Collatz の問題」ではすべての数が 1 に収束すると仮定されています。この仮定が正しいとするならば、すべての数はどこか途中から同じプロセスをたどって 1 に収束していくはずです。

そこで、小さい数の順に生成される数列の長さを記録していき、数列の中に既に記録された数が現れた場合はそれ以上計算しないようにしてみました。

いわゆる Memoize というやつです。『まつもとゆきひろ コードの世界』で「空間で時間を買う」と表現された高速化の一種です。

MAX = 100_0000 collatz = Array.new(MAX, 1) max = [1, 1] 2.upto(MAX - 1) do |n| v = n c = 0 while v >= n if v.even? then v = v / 2 else v = v * 3 + 1 end c = c + 1 end count = c + collatz[v] collatz[n] = count max = [n, count] if count > max[1] end puts max[0]

これだと、Ruby 1.9 で約 2 秒ほどで答が出ました。効果は絶大です。

しかし N88-BASIC の時代からコンピュータに触れている私にとって、「空間で時間を買う」という表現はとても贅沢な響きを持っています。

なんたって、私が初めて買った「PC-8801 MH」のメモリは 128KB でしたからねぇ……。ところが今や、1GB や 2GB は当たり前……。

時代の流れを感じますねぇ……。

2009年6月18日 (木)

Project Euler - Problem 13

問題はこちらをご覧ください。


今回も、データをスクリプトに埋め込むのが面倒だったので、"DATA" を使ってみました。

Ruby のリファレンスマニュアルによれば、"DATA" は

スクリプトの __END__ (スクリプトの終り) 以降をアクセスする File オブジェクト
となっています。

File クラスのスーパークラスである IO クラスに "Enumerable" が組み込まれているので、"DATA" でも "inject" がそのまま使えるようです。

a = DATA.inject(0){|sum, str| sum + str.to_i} puts(a.to_s[0, 10]) __END__ 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 53282654108756828443191190634694037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 34829543829199918180278916522431027392251122869539 40957953066405232632538044100059654939159879593635 29746152185502371307642255121183693803580388584903 41698116222072977186158236678424689157993532961922 62467957194401269043877107275048102390895523597457 23189706772547915061505504953922979530901129967519 86188088225875314529584099251203829009407770775672 11306739708304724483816533873502340845647058077308 82959174767140363198008187129011875491310547126581 97623331044818386269515456334926366572897563400500 42846280183517070527831839425882145521227251250327 55121603546981200581762165212827652751691296897789 32238195734329339946437501907836945765883352399886 75506164965184775180738168837861091527357929701337 62177842752192623401942399639168044983993173312731 32924185707147349566916674687634660915035914677504 99518671430235219628894890102423325116913619626622 73267460800591547471830798392868535206946944540724 76841822524674417161514036427982273348055556214818 97142617910342598647204516893989422179826088076852 87783646182799346313767754307809363333018982642090 10848802521674670883215120185883543223812876952786 71329612474782464538636993009049310363619763878039 62184073572399794223406235393808339651327408011116 66627891981488087797941876876144230030984490851411 60661826293682836764744779239180335110989069790714 85786944089552990653640447425576083659976645795096 66024396409905389607120198219976047599490197230297 64913982680032973156037120041377903785566085089252 16730939319872750275468906903707539413042652315011 94809377245048795150954100921645863754710598436791 78639167021187492431995700641917969777599028300699 15368713711936614952811305876380278410754449733078 40789923115535562561142322423255033685442488917353 44889911501440648020369068063960672322193204149535 41503128880339536053299340368006977710650566631954 81234880673210146739058568557934581403627822703280 82616570773948327592232845941706525094512325230608 22918802058777319719839450180888072429661980811197 77158542502016545090413245809786882778948721859617 72107838435069186155435662884062257473692284509516 20849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690

2009年6月17日 (水)

Project Euler - Problem 12

問題はこちらをご覧ください。


ここにも書いてあるように、素因数分解の結果がわかれば、約数の個数が出せます。

例えば、素因数分解の結果が [[2, 2], [3, 1]] だった場合、

[[2, 2], [3, 1]].inject(1){|pr, n| pr * (n[1] + 1)}

とすることで個数が出ます。


ということで、何のひねりもなく素直にコーディングすると次のようになりました。

"math_tool.rb" に関してはここを見てください。

require 'math_tool' tri = 0 1.upto(1.0/0) do |i| tri = tri + i # 三角数を加算で表現。 if tri.factorize.inject(1){|pr, n| pr * (n[1] + 1)} > 500 then puts(tri) break end end

私のパソコン上で Ruby 1.9 を使って実行すると、約 1.6 秒で答が出ます。


ところで、この問題にはもっと高速に答えを出す方法があります。

ヒントは……

  • 三角数の一般式は T(n) = n * (n + 1) / 2
    • 当然、T(n+1) = (n + 1) * (n + 2) / 2
  • n と n + 1 は「互いに素」になる。
    • n が偶数の場合、n / 2 と n + 1 は「互いに素」になる。
    • n が奇数の場合、n と (n + 1) / 2 は「互いに素」になる。
  • 整数 a と整数 b が「互いに素」となる場合、(a の約数の数) * (b の約数の数) = (a * b) の約数の数

これらの考えを基にコーディングした結果、約 0.3 秒で答が出ました。


このアルゴリズムは、他のブログに付いていたコメントがヒントになって生まれました。

自分だけでこんなアルゴリズムを考えつけるくらいの数学的知識が欲しいなぁ……。

2009年6月16日 (火)

Project Euler - Problem 11

問題はこちらをご覧ください。


今回は、データを二次元配列に入れてただ計算しただけです。

コードもやたら長くて、同じような部分がたくさんあるので、自分としては不満があるのですが、今のところいいアイデアもないので……。

def check1(x, y) return 0 if x < 3 or y > 16 product = 1 4.times{|i| product = product * $arr[x - i][y + i]} return product end def check2(x, y) return 0 if y > 16 product = 1 4.times{|i| product = product * $arr[x][y + i]} return product end def check3(x, y) return 0 if x > 16 or y > 16 product = 1 4.times{|i| product = product * $arr[x + i][y + i]} return product end def check4(x, y) return 0 if x > 16 product = 1 4.times{|i| product = product * $arr[x + i][y]} return product end $arr = Array.new DATA.each_line do |data| $arr.push(data.chomp!.split.map{|st| st.to_i}) end v_max = 0 20.times do |x| 20.times do |y| v_max = [check1(x, y), check2(x, y), check3(x, y), check4(x, y), v_max].max end end puts(v_max) __END__ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

2009年6月15日 (月)

Project Euler - Problem 10

問題はこちらをご覧ください。


この問題は、いかにして「200万以下の素数」を求めるかがポイントになります。

Ruby であれば、"prime.rb" を読み込んだ上で Prime.each(200_0000) ... とすることで簡単に求めることができます。

require 'prime' puts(Prime.each(200_0000).inject(:+))

Ruby 1.9 なら、約 4 秒で答が出ます。


ただ、「n 以下の素数を求める」といった限定的な条件なら、ここにも書きましたが自作の "math_tool.rb" に含まれている "prime_list" メソッドの方が高速です。

require 'math_tool' puts(prime_list(200_0000).reduce(:+))

こちらの場合、Ruby 1.9 なら約 1.5 秒くらいで答が出ます。


「楽しく、楽にプログラミングをする」というコンセプトの Ruby では、わざわざ新たにメソッドを作らずに添付ライブラリを使用するのが本来のやり方なのでしょう。

でも、この "prime_list" メソッドは、Chez Scheme で Project Euler を解いているときに必要に迫られて作った手続きを Ruby に移植したもので、それなりに思い入れがあるんです。

しかも、Project Euler のようにたくさんの計算をする必要がある場合、より速い方を使いたくなるのはしょうがないですよね。(たぶん、誰もかばってくれないだろうから、自己弁護……)

2009年6月14日 (日)

いまさら "FizzBuzz"

なんでいまさら「FizzBuzz」問題かというと、こんな記事を見つけたんですよ。

この記事の中の「剰余なしで……」というのが面白そうだったから……。

かなり古いエントリーなんだけど、探してみたら同じような話題が結構あったみたい(既に過去形……)。

一般的にはここの一番上の例のように剰余を使いますよね。このパターンは私もかなり前に自分でやってみました(ただしその時は Scheme でしたが……)。

それじゃあ、今度は剰余を使うなと……。


いろいろ考えた結果、Ruby 限定かも知れませんが面白いのができたので、ブログに載せてみようかと思ったわけです。

しかも、「剰余を使わない」どころか、コード上は算術計算を一切していません(そのぶん、裏では Ruby がしっかり計算をしてくれていますが……)。

ということで、今回考えたコードはこれです。

nums = (0 .. 100).to_a a = [[3, "Fizz"], [5, "Buzz"], [15, "FizzBuzz"]] a.each{|arr| 0.step(100, arr[0]){|i| nums[i] = arr[1]}} puts nums.drop(1)

これって、私の好きな配列の内容を上書きしていくパターンです。

どうも、Scheme でコードを書いているうちに、何でもかんでも配列やハッシュに貯め込んで、後から加工する癖がついちゃったみたいです。

Project Euler - Problem 9

問題はこちらをご覧ください。


"math_tool.rb" の一部として既にこのブログにも投稿していますが、「ピタゴラスの三つ組」を求める "pythagorean_triples" というメソッドを作りました。

def pythagorean_triples(n) return [] if n.odd? ans = Array.new 1.upto(n / 3) do |a| q, r = (n * n).divmod(2 * n - 2 * a) if r.zero? then b = n - q break if a > b ans.push([a, b, n - a - b]) end end return ans end

このメソッドは次のような考察を基に a, b を求めています。

a + b + c = n であれば、c = n - (a + b)
これを a² + b² = c² に代入すると……
b = (2 * a * n - n²) / (2 * a - 2 * n) = n - n² / (2 * n - 2 * a)

ということで、b が整数になるような a を探していくことで「ピタゴラスの三つ組」を求めています。


require 'math_tool' a, b, c = pythagorean_triples(1000)[0] puts(a * b * c)

Project Euler - Problem 8

問題はこちらをご覧ください。


問題を解く方法自体はそんなに難しそうではありませんが、1000 桁の数字をどうやってスクリプトに埋め込むか悩みました。

すべての数字を一行につなげて、num = 7316... と直接埋め込む方法も考えてみましたが、一行が 1000 文字を越えるのはちょっと……。

そこで、今回は "DATA" を使った処理をしてみました。

"DATA" を使うと読み込んだデータは文字列として処理されるので、それをさらに加工していきました。

また、数字を 5 つずつ処理するために "Enumerable#each_cons" を使ってみました。

require 'math_tool' nums = DATA.inject([]){|arr, str| arr + str.chomp!.to_i.to_a} max = 0 nums.each_cons(5) do |arr| v = arr.inject(:*) max = v if v > max end puts(max) __END__ 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

また、"math_tool.rb" を少しだけイジりました。Integer#prime?Integer#factorize の内容を見直して若干のスピードアップを図っています。

2009年6月11日 (木)

Project Euler - Problem 7

問題はこちらをご覧ください。


この問題は素数を数えていくだけですが、次のようにひとつひとつ素数判定をしていくと結構時間がかかります。(Ruby 1.9 で実行して 1 秒くらいです)

require 'math_tool'   i = 2 p = 3 # 3 は素数の 2 番目   while (i < 10001) do p = p + 2 # p : 奇数だけを調べていく。 i = i + 1 if p.prime? end   print("#{p}\n")

さりとて、上限が分からないので、自作の prime_list も使えないし……。


こういう時には、添付ライブラリの "prime.rb" に含まれる Prime class を使うと、速くてすっきりとした code がかけます。

require 'prime' puts(Prime.take(10001).last)

この code を Ruby 1.9 で実行すると約 0.2 秒で答が出ます。


この問題を解くためにいろいろ調べていて、初めて Enumerable#take と言うメソッドを知りました。いろいろと便利なメソッドが増えていくんですね。うれしい限りです。


"math_tool.rb" を最新版に更新しました。メソッドの改良、追加などを行っています。興味がある方はご覧ください。

Project Euler - Problem 6

問題はこちらをご覧ください。


この問題は単純に計算するだけです。何の工夫もしていません。

a = (1 .. 100).inject(:+) ** 2 b = (1 .. 100).inject(0){|sum, n| sum = sum + n ** 2} puts(a - b)

2009年6月 3日 (水)

Project Euler - Problem 5

問題はこちらをご覧ください。


要するに「1 〜 20 のすべての最小公倍数」を求める問題ですよね。

ここにも書きましたが、2 数の最大公約数が分かれば最小公倍数も分かるので、「ユークリッドの互除法」を使った最大公約数を求めるメソッドを自作できればこの問題は解けます。

でも、Ruby には最大公約数を求める Integer#gcd や、最小公倍数を求める Integer#lcm が既にあるので、今回はこれを使っていきます。

a = 1 (2 .. 20).each{|i| a = a.lcm(i)} puts(a)

inject を使うこともできます。

puts((1 .. 20).inject{|n, i| n = n.lcm(i)})

あまりにも簡単に答えが出てしまうので、面白くない?

じゃあ、自分でメソッドを作ってみましょうか。

class Integer # # == 最大公約数を求める # # * ユークリッドの互除法を使用。 # def my_gcd(num) m = [self, num].max n = [self, num].min r = m.modulo(n) until r.zero? m, n = n, r r = m.modulo(n) end return n end # # == 最小公倍数を求める # def my_lcm(num) return self * num / self.my_gcd(num) end end puts((1 .. 20).inject{|n, i| n = n.my_lcm(i)})

こんな感じでどうでしょう?

Project Euler - Problem 4

問題はこちらをご覧ください。


ここにも書きましたが、二重ループを使って 3 桁の整数 × 3 桁の整数をすべて求めて、その中から最大の回文数を探すのは計算量が多くなるので大変だと思っていました。

そこで、大きい順に 6 桁または 5 桁の回文数をつくって、それが 3 桁の整数 × 3 桁の整数で表せるかをどうかを調べる方法を考えました。

require 'math_tool' # 3 桁の約数の組を探す。 def find_div(n) mid = sqrt(n).to_i mid.step(100, -1) do |i| if n.modulo(i).zero? and (n / i) < 1000 then return true end end return false end # 大きい順に回文数を作り、3 桁の約数の組を持って入れば、 # 答として表示する。 def check [true, false].each do |flag| 997.step(100, -1) do |n| p_num = n.make_palindromic(flag) return p_num if find_div(p_num) end end end puts(check)

このコードでも、Ruby 1.9 なら 0.08 秒ほどで答が出るのですが、他のブログを見て回ったところ、二重ループを使う方法でも、 break をうまく使うと、計算量を減らせることがわかりました。

require 'math_tool' v_max = 0 999.downto(100) do |i| i.downto(100) do |j| a = i * j break if a <= v_max v_max = a if a > v_max and a.palindromic? end end puts(v_max)

こちらのほうは、Ruby 1.9 で 0.05 秒ほどで答が出ます。私が最初に考えたコードよりシンプルでかつ速いですね。

2009年6月 2日 (火)

Project Euler - Problem 3

問題はこちらをご覧ください。


要するに「素因数分解」の問題ですね。

まずは、添付ライブラリを使用するもの……

require 'prime' factor = 600851475143.prime_division puts(factor.last[0])

次は自作の "math_tool.rb" を使用するもの……

require 'math_tool' factor = 600851475143.factorize puts(factor.last[0])

ちなみに、自作の "Integer#factorize" が添付ライブラリの "Integer#prime_division" より若干遅いのが判明して、くやしかったので、 またちょっと改良を加えました。

Project Euler - Problem 2

問題はこちらをご覧ください。


ここにも書きましたが、反復的に求めていきます。

まずは、単純に足していくもの……

MAX = 400_0000 sum = 0 a, b = 1, 1 while a < MAX sum = sum + a if a.even? a, b = a + b, a end puts(sum)

次は、フィボナッチ数列を一旦配列に収めてから加工していくもの……

MAX = 400_0000 def fib_list(limit) f = Array.new a, b = 1, 1 while a < limit f.push(a) a, b = a + b, a end return f end sum = fib_list(MAX).select{|x| x.even?}.inject(:+) puts(sum)

どちらも Ruby 1.9 なら 0.02 〜 0.05 秒くらいで結果が出ます。

« 2009年5月 | トップページ | 2009年7月 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ