« 2009年4月 | トップページ | 2009年6月 »

2009年5月

2009年5月29日 (金)

またまた、 Problem 1

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


なぜ、今更「Problem 1」なのかというと…… Ruby でやるならいろいろなやり方ができるはずなので、「このくらい簡単な問題ならバリエーションを考える余裕があるかな?」と思ったわけです。

# Integer#times sum = 0 1000.times {|x| sum = sum + x if x % 3 == 0 or x % 5 == 0} puts(sum) # Integer.upto sum = 0 1.upto(999) {|x| sum = sum + x if x % 3 == 0 or x % 5 == 0} puts(sum) # Range#each sum = 0 (1...1000).each {|x| sum = sum + x if x % 3 == 0 or x % 5 == 0} puts(sum) # while sum = 0 x = 1 while x < 1000 sum = sum + x if x % 3 == 0 or x % 5 == 0 x = x + 1 end puts(sum) # Array#select lst = (1...1000).select{|x| x % 3 == 0 or x % 5 == 0} puts(lst.inject(:+)) # Array#delete_if lst = (1...1000).reject{|x| x % 3 > 0 and x % 5 > 0} puts(lst.inject(:+)) # さらに…… sum = (1...1000).inject(0) do |v, x| if x % 3 == 0 or x % 5 == 0 v = v + x else v end end puts(sum) # Integer#step No.1 sum = 0 [3, 5].each do |i| 0.step(999, i) {|x| sum = sum + x} end 0.step(999, 15) {|x| sum = sum - x} puts(sum) # Integer#step No.2 lst = Array.new(1000, 0) [3, 5].each do |i| 0.step(999, i) {|x| lst[x] = x} end puts(lst.inject(:+))

一応、このくらいは考えてみたのですが、もっと他にもあるんだろうなぁ…… 。

おもしろいコードを考えついた方は、是非お知らせください。

素因数分解

あるブログで「素因数分解の速度」を競っているような話題が出ていました。

二人が仲がよくてただじゃれあっているのか、真剣に競い合っているのかは、私の知るところではないのですが、「素因数分解の速度」については思うところがあるので、私も記事を書いてみようかな……。

もし、二人が「素数列をつくる速度」を競っていて、その延長線上で「因数分解の速度」の話になったのなら的外れになるかもしれませんが……。


「素因数分解」の速度を上げようと思ったら、素数を探して割っていくより、対象の数を 2 で割り続けて奇数にした後に、単純に小さい順に奇数で割っていくほうが速いと思います。

なにせ、素数を求めること自体にけっこう時間がかかるのですから。

(さらに、5 以上の素数 p は必ず p = 6 * n - 1 または p = 6 * n + 1 と表せる事を利用するとさらに割る数が少なくなります)


と、いうことで奇数で割り続ける「素因数分解」の Ruby 版です。

# = factorize.rb class Integer def factorize return [] if self < 2 ans = Array.new n = self [2, 3].each do |i| c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 end i = 5 add = 2 while true c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 i = i + add break if n < i * i add = 6 - add end ans.push([n, 1]) if n > 1 return ans end end n = ARGV[0].to_i print "#{n.factorize}\n"
$ ruby -v ruby 1.9.1p129 (2009-05-12 revision 23412) [i686-linux] $ time ruby factorize.rb 111111111 [[3, 2], [37, 1], [333667, 1]] real 0m0.078s user 0m0.020s sys 0m0.012s

Scheme 版はこちら。(普段は "Chez Scheme" を使っているのですが、同じ条件で比較するために "Gauche" で動くようにしてみました)

(define factorize (lambda (n) (define result '()) (define factor-count (lambda (n i) (let loop ([n n] [c 0]) (cond ([zero? (remainder n i)] (loop (/ n i) (+ c 1))) (else (if [> c 0] (set! result (cons (cons i c) result))) n))))) (set! n (factor-count n 2)) (set! n (factor-count n 3)) (let loop ([n n] [i 5] [add 2]) (cond ([= n 1] (reverse result)) ([> (* i i) n] (reverse (cons (cons n 1) result))) (else (loop (factor-count n i) (+ i add) (- 6 add))))))) (define (main args) (print (factorize (string->number (cadr args)))))
$ gosh -V Gauche scheme interpreter, version 0.8.13 [utf-8,pthreads] $ time gosh factorize.scm 111111111 ((3 . 2) (37 . 1) (333667 . 1)) real 0m0.060s user 0m0.012s sys 0m0.016s

では、Gemma さんのコードを見てみましょう。

(ちなみにここに書いてあるコードは終了判定に問題があったようで、こちらに改訂版が書いてあります。以下の記事では改訂版をもとに話をします)

$ gosh -V Gauche scheme interpreter, version 0.8.13 [utf-8,pthreads] $ time gosh factStrm.scm 111111111 ((3 . 2) (37 . 1) (333667 . 1)) real 0m0.174s user 0m0.092s sys 0m0.008s

このコードのスピードは Ruby 版よりは遅いですが、まだまだ実用の範囲にあると思います。


ところで、こちらのコードはというと……

まず "primes.py" というファイルが無いとエラーが出ます。しかも "primes.py" には 997 までしか素数が書き込まれないので、理論的には 994009 以上の数は素因数分解できません。

実際に実効してみると…… 7884 以上では "RuntimeError: maximum recursion depth exceeded in cmp" が出てまともな答えが出ません。

そこでこのコードが使える範囲で速度を見てみると……

$ python -V Python 2.6.2 $ time python fact.py 7882 [2, 7, 563] real 0m0.383s user 0m0.332s sys 0m0.004s $ time python fact.py 7882 [2, 7, 563] real 0m0.326s user 0m0.252s sys 0m0.012s

"primes.py" が空の一回目も "primes.py" が書き込まれた後の二回目もあまりスピードが変わりません。

同じ数字を私の Ruby 版で試してみると……

$ time ruby factorize.rb 7882 [[2, 1], [7, 1], [563, 1]] real 0m0.062s user 0m0.024s sys 0m0.004s

Python 2.6 と Ruby 1.9 では処理系自体のスピードにも差があるのかもしれませんが、Python 版は Ruby 版の約 6 倍時間がかかっています。

使用できる範囲も狭いし、速度も遅い……少なくとも Project Euler クラスの問題を解くにはとても使えません。


※ Gemma さんやみずぴーさんのところのトラックバックをたどって来られる方がいらっしゃるようなので、新しく分かった事実などを元に、以前書いた記事を書き直しました。(2009/09/02)

※ 記事を書き直した際に、Scheme 版を書き忘れていたようなので、改めて最新版を載せました。(2009/10/19)

2009年5月25日 (月)

「1以上100未満の『2個の素数の積』である整数を列挙しなさい」

先日、あるブログで「1以上100未満の『2個の素数の積』である整数を列挙しなさい」という問題を Python で解いているのをみました。

ちょっと簡単な "Project Euler" みたいな感じなので、私も Ruby で解いてみようと思ったわけです。


一番簡単なのは、100 未満の素数を順に掛け合わせていって、100 未満の数だけ集める方法ですが、これだと計算に多くの無駄があったり、答に重複が出るので、もう少し考える必要があります。


まず重複をなくすために、二つの素数を a, b としたときに必ず a ≦ b になるように決めます。

次に、a と b の範囲を考えます。

a ≦ b かつ a × b < 100 ですから、a は 10 未満になることが分かります。

また、b は a ≦ b < 100 / a の範囲になります。ただ、毎回 b の範囲を計算し直すのも時間の無駄のような気がしたので、これに関してはちょっと方法を変えてみました。


Ruby で素数を扱う場合、一番手っ取り早いのは 1.9 についてくる "mathn" "prime.rb" に含まれる Prime クラスを使うことだと思います。

require 'prime' include Math Limit = 100 ans = Array.new a = Prime.instance b = Prime.instance a.each(sqrt(Limit).to_i) do |i| b.each do |j| next if j < i c = i * j if c < Limit then ans.push(c) else break end end end p ans.sort
=> [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] real 0m0.086s user 0m0.044s sys 0m0.008s

この方法でも結構速いのですが、今回のように使う素数列の上限が決まっている場合、前回紹介した "prime_list" メソッドの方が若干速かったりします。


この "prime_list" は、Ruby のサンプルに含まれている "sieve.rb" を独自に改良したものです。

"sieve.rb" はいわゆる「エラトステネスの篩」なのですが、一般的なものが割り算の余りを評価して合成数を除外していくのに対して、"sieve.rb" は足し算を使うことによって合成数を除外していきます。

アセンブラを知っている方はご存知と思いますが、コンピュータは足し算や引き算は得意ですが、掛け算や割り算はあまり得意ではありません。

したがって割り算を多用するコードより足し算を多用するコードのほうが速く処理できます。

私が "sieve.rb" を改良してつくった "prime_list" は最初から偶数を除外しておくなどの工夫を加えてあります。

Ruby 1.9 なら百万以下の素数列を 0.5 秒ほどでつくってしまいます。

include Math def prime_list(n) return [] if n <= 1 size = n / 2 - 1 max = sqrt(n).to_i a = Array.new(size){|i| 2 * i + 3} a.unshift(nil) max.times do |i| j = a[i] next unless j (2 * i * (i + 1)).step(size, j) do |k| a[k] = nil end end return a.unshift(2).compact end Limit = 100 p_lst1 = prime_list(sqrt(Limit).to_i) p_lst2 = prime_list(Limit / 2) ans = Array.new p_lst1.each do |a| p_lst2.each do |b| next if a > b c = a * b if c < Limit then ans.push(c) else break end end end p ans.sort
=> [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] real 0m0.084s user 0m0.024s sys 0m0.020s

2009年5月24日 (日)

"math_tool.rb" by Ruby 1.9.1

しばらく、Scheme ばかり使ってきた反動か、最近は Ruby でコードを書きたい衝動にかられています。

私が使用している Ubuntu のパッケージで管理されているのは Ruby 1.8.7 と Ruby 1.9.0 なのですが、「やっぱりこれからは 1.9.1 でしょ」ということで、自前で Ruby 1.9.1 をインストールしてみました。

いや〜、1.9.1 は速くなりましたねぇ……。同じスクリプトを走らせても、普通に 2 〜 3 倍は速くなっている感じです。Shell からスクリプトとして実行した Chez Scheme のコードに引けを取らない速さにビックリです。

これからしばらくは、今まで Scheme で解いてきた Project Euler の問題を改めて Ruby で解いていきたいと思います。


そこで、今後使っていくことになるであろう自作のメソッドなどを、まとめて紹介しておきます。

私は、これらのメソッドを "math_tool.rb" という名前で保存して使っています。

# -*- coding: utf-8 -*- # # = math_tool.rb -- Methods for "Project Euler" # # Author:: ツムジ # class Integer # call-seq: # n.prime? -> bool # # * n が素数ならば true を返す。 ( 試し割法 ) # * 添付ライブラリの prime.rb を参考に改良。 # # === Example # 3.prime? # => true # def prime? return true if self == 2 or self == 3 return false if self.even? or self % 3 == 0 or self <= 1 limit = (self ** 0.5).to_i i = 5 add = 2 while limit >= i return false if self % i == 0 i = i + add add = 6 - add end return true end # call-seq: # n.fast_prime? -> bool # # * n が素数ならば true を返す。( Miller-Rabin test ) # * Wikipedia から引用 ( 一部改変 ) # # === Example # 3.fast_prime? #=> true # def fast_prime? n = self.abs() return true if n == 2 return false if n == 1 || n & 1 == 0 d = n-1 d >>= 1 while d & 1 == 0 10.times do a = rand(n-2) + 1 t = d y = pow(a,t,n) while t != n-1 && y != 1 && y != n-1 y = (y * y) % n t <<= 1 end return false if y != n-1 && t & 1 == 0 end return true end def pow(base, power, mod) result = 1 while power > 0 result = (result * base) % mod if power & 1 == 1 base = (base * base) % mod power >>= 1; end result end # call-seq: # n.to_a -> array # n.to_a(radix) -> array # # * n の各桁を要素とする配列を返す。 # * 基数を radix として指定できる。 # # === Example # 123.to_a => [1, 2, 3] # 123.to_a(2) => [1, 1, 1, 1, 0, 1, 1] # def to_a(radix = 10) n = self a = Array.new while (n >= radix) do n, r = n.divmod(radix) a.unshift(r) end return a.unshift(n) end # call-seq: # n.factorize -> array # # * n を素因数分解した結果を配列にして返す。 # # === Example # 120.factorize #=> [[2, 3], [3, 1], [5, 1]] # def factorize return [] if self < 2 ans = Array.new n = self [2, 3].each do |i| c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 end i = 5 add = 2 while true c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 i = i + add break if n < i * i add = 6 - add end ans.push([n, 1]) if n > 1 return ans end # call-seq: # n.divisor -> array # # * n の約数を配列にして返す。 # # === Example # 12.divisor #=> [1, 2, 3, 4, 6, 12] # def divisor sq = self ** 0.5 sqi = sq.to_i d1 = (1 .. sqi).select{|i| self % i == 0} d2 = d1.map{|i| self / i} d1.pop if sq == sqi return d1.concat(d2.reverse) end # call-seq: # n.divisor2 -> array # # * n の約数を配列にして返す。 # * 素因数分解の結果を元に計算している。 # * n > 5000 で Integer#divisor より速度的に優位になる? # # === Example # 12.divisor2 #=> [1, 2, 3, 4, 6, 12] # def divisor2 f_arr = self.factorize.map{|f, i| (0 .. i).map{|j| f ** j}} f_arr = f_arr.inject([1]) do |pro, arr| pro = pro.map{|i| arr.map{|j| j * i}}.flatten end return f_arr.sort end # call-seq: # n.sum_of_divisors -> integer # # * n の「真の約数の和」を返す。 # * 詳しくは『数学ガール』を参照のこと。 # * self < 2 の場合は、本来 error にすべきだが 0 を返すように # してある。 # # === Example # 28.sum_of_divisors #=> 28 # def sum_of_divisors return 0 if self < 2 arr = self.factorize.map do |f, i| (f ** (i + 1) - 1) / (f - 1) end return arr.inject(:*) - self end # call-seq: # n.amicable_pair -> integer or nil # # * n と友愛数の組みになる整数を返す。 # # === Example # 220.amicable_pair #=> 284 # 221.amicable_pair #=> nil # def amicable_pair a = self.sum_of_divisors return false if a == self if self == a.sum_of_divisors return a else return nil end end # call-seq: # n.perfect? -> bool # # * n が完全数ならば true を返す。 # # === Example # 28.perfect? #=> true # def perfect? return false if self < 2 return self == self.sum_of_divisors end # call-seq: # n.abundant? -> bool # # * n が過剰数ならば true を返す。 # # === Example # 12.abundant? #=> true # def abundant? return false if self < 2 return self < self.sum_of_divisors end # call-seq: # n.deficient? -> bool # # n が不足数ならば true を返す。 # # === Example # 9.deficient? #=> true # def deficient? return false if self < 2 return self > self.sum_of_divisors end # call-seq: # n.factorial -> integer # n.factorial(m) -> integer # # * n の階乗または下降階乗冪を返す。 # * n.factorial == n! # * n.factorial(m) == n * (n - 1) * ... * (n - m + 1) # * n < m の場合、n.factorial(m) == 0 # # === Example # 5.factorial #=> 120 # 5.factorial(3) #=> 60 # def factorial(m = self) fact = (self - m + 1 .. self).inject(:*) return (fact or 1) end # call-seq: # n.permutation_size(r) -> integer # # * 順列 nPr の数を返す。 # # === Example # 5.permutation_size(3) #=> 60 # def permutation_size(r = self) return self.factorial(r) end # call-seq: # n.combination_size(r) -> integer # # * 組み合わせ nCr の数を返す。 # # === Example # 5.combination_size(3) #=> 10 # def combination_size(r) return self.permutation_size(r) / r.factorial end # call-seq: # n.pandigital? -> bool # # * n が Pandigital な整数ならば true を返す。 # # === Example # 35412.pandigital? #=> true # def pandigital? self.to_a.pandigital? end # call-seq: # n.palindromic? -> bool # # * n が回文数ならば true を返す。 # # === Example # 12321.palindromic? => true # def palindromic? str = self.to_s return str == str.reverse end # call-seq: # n.make_palindromic -> integer # n.make_palindromic(:odd) -> integer # n.make_palindromic(:even) -> integer # # * n を上位の桁とする回文数をつくる。 # * 引数が省略された場合、奇数桁の回文数をつくる。 # * 引数が :odd の場合、奇数桁の回文数をつくる。 # * 引数が :even の場合、偶数桁の回文数をつくる。 # # === Example # 123.make_palindromic #=> 12321 # 123.make_palindromic(:odd) #=> 12321 # 123.make_palindromic(:evne) #=> 123321 # def make_palindromic(flag = :odd) str1 = self.to_s str2 = str1.reverse str1.chop! if flag == :odd return (str1 << str2).to_i end # call-seq: # n.sum_of_digits -> integer # # * 各桁の和を返す。 # # === Example # 123.sum_of_digits #=> 6 # def sum_of_digits arr = self.to_s.split('') return arr.inject(0){|sum, st| sum + st.to_i} end end class Array # call-seq: # arr.to_i -> integer # arr.to_i(radix) -> integer # # * 配列の要素を各桁とする整数を返す。 # * 基数を radix として指定できる。 # # === Example # [1, 2, 3].to_i #=> 123 # [1, 1, 1, 1, 0, 1, 1].to_i(2) #=> 123 # def to_i(radix = 10) return self.inject(0){|sum, i| sum * radix + i.to_i} end # call-seq: # arr.pandigital? -> bool # # * arr が Pandigital な配列ならば true を返す。 # # === Example # [1, 2, 4, 3].pandigital? #=> true # def pandigital? self.sort.each_with_index do |a, i| return false unless a == i + 1 end return true end # call-seq: # arr.palindromic? -> bool # # * arr が回文配列ならば true を返す。 # # === Example # [1, 2, 3, 2, 1].palindromic? #=> true # def palindromic? return self == self.reverse end end # call-seq: # prime_list(n) -> array # # * n 以下の素数を配列にして返す。 # * エラトステネスの篩 : 加算版 # # === Example # prime_list(20) => [2, 3, 5, 7, 11, 13, 17, 19] # def prime_list(n) return [] if n < 2 return [2] if n == 2 limit = (n ** 0.5).to_i arr = (1 .. n).step(2).to_a arr[0] = 2 len = arr.size i = 0 while true i = i + 1 j = arr[i] next unless j break if j > limit k = 2 * i * (i + 1) while k < len arr[k] = nil k = k + j end end arr.compact! return arr end # call-seq: # pythagorean_triples(n) -> array # # * a < b < c, a + b + c = n, a² + b² = c² の条件を満たす # [a, b, c] を配列にして返す。 # # === Example # pythagorean_triples(90) #=> [[9, 40, 41], [15, 36, 39]] # pythagorean_triples(90).select do |a, b, c| # a.gcd(b).gcd(c) == 1 # 既約でないものを除く # end #=> [[9, 40, 41]] # 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 == 0 b = n - q break if a > b ans.push([a, b, n - a - b]) end end return ans end # call-seq: # amicable_numbers(min, max) -> array # # * min 〜 max の範囲に存在する友愛数の組を配列にして返す。 # # === Example # amicable_numbers(1, 2000) #=> [[220, 284], [1184, 1210]] # def amicable_numbers(min, max) min = 2 if min < 2 ans = Array.new (min .. max).each do |a| b = a.amicable_pair if b and a < b ans.push([a, b]) end end return ans end # call-seq: # phi(n) -> integer # # * オイラーのφ関数 # * 正の整数 n に対して、1 から n までの自然数のうち n と互いに # 素なものの個数(1 と n は互いに素と考える) # # === Example # phi(6) = 2 (1, 5 のみなので) # def phi(n) arr = (1 ... n).to_a.select{|i| i.gcd(n) == 1} return arr.size end

追記 < 2009/09/08/ > : prime_list にバグを見つけたので、修正しました。

2009年5月22日 (金)

Project Euler - Problem 35

* 今回の内容は、以前投稿した内容を一部修正して、Ruby のコードを加えたものです。


Problem 35 は次のような問題でした。

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および 97 である. 100万未満の巡回素数は何個か?

100 万未満の素数の全てで巡回素数かどうかを調べると、

(length (prime-list 1000000)) ; => 78498

78498 個もの素数を調べる必要があります。


そこで、もう少し考えてみましょう。

2 桁以上の素数で、偶数または 5 を含むものは、巡回しているうちに偶数または 5 が一の位になった時点で、素数でなくなります。ならば偶数や 5 を含む素数は最初から除外しておけば、調べる数が減るはずです。

ということで、私は以下のようなコードを書いてみました。いかがでしょうか?

(define problem-035 (lambda (n-max) ;; 偶数または 5 を含んでいるか? (define include_even_or_5? (lambda (lst) (if [null? (cdr lst)] #f (exists (lambda (x) (memv x lst)) '(0 2 4 5 6 8))))) ;; 循環素数となるリストか? (define circular? (lambda (lst) (let* ([len (length lst)] [lst-a (append lst lst)]) (let loop ([lst-a (cdr lst-a)]) (cond ([= (length lst-a) len] #t) ([prime? (list->integer (list-head lst-a len))] (loop (cdr lst-a))) (else #f)))))) (let* ([lst-a (map integer->list (prime-list n-max))] [lst-b (remp include_even_or_5? lst-a)] [lst-c (filter circular? lst-b)]) (printf "~d~%~a~%" (length lst-c) (map list->integer lst-c))))) (problem-035 1000000)


ちなみに、Ruby だとこんなかんじでしょうか?

# -*- coding: utf-8 -*- include Math class Integer # # 素数の判定 # def prime? return false if (self <= 1) return true if (self == 2) return false if (self.even?) 3.step(sqrt(self).to_i, 2) do |i| return false if (self.modulo(i) == 0) end return true end # # 整数を配列に変換する。 # ex : 123.to_a => [1, 2, 3] # ex : 123.to_a(2) => [1, 1, 1, 1, 0, 1, 1] # def to_a(radix = 10) n = self a = Array.new while (n >= radix) do a.unshift(n.modulo(radix)) n = n / radix end a.unshift(n) end end # # n 以下の素数を要素とする配列を返す。 # ex : prime_list(20) => [2, 3, 5, 7, 11, 13, 17, 19] # def prime_list(n) return([]) if (n <= 1) size = n / 2 - 1 max = sqrt(n).to_i a = Array.new(size) size.times do |i| a[i] = 2 * i + 3 end a.unshift(nil) max.times do |i| j = a[i] next unless j (2 * i * (i + 1)).step(size, j) do |k| a[k] = nil end end return a.unshift(2).compact end class Array # # 配列を整数に変換する。 # ex : [1, 2, 3].to_i => 123 # ex : [1, 1, 1, 1, 0, 1, 1].to_i(2) => 123 # def to_i(radix = 10) sum = 0 self.each do |i| sum = sum * radix + i if (i < radix) end return sum end # # 偶数または 5 を含むか? # def check_even_and_5 return false if self.length == 1 if [0, 2, 4, 5, 6, 8].any? {|x| self.include?(x)} then return true else return false end end # # 循環素数になるリストか? # def circular? a_size = self.size a = self * 2 a_size.times do |i| next if i.zero? return false if not a[i, a_size].to_i.prime? end return true end end p_list = prime_list(100_0000).map {|x| x.to_a} p_list = p_list.delete_if {|x| x.check_even_and_5} p_list = p_list.select {|x| x.circular?} print("#{p_list.size}\n") p p_list.map {|x| x.to_i}

2009年5月 6日 (水)

Project Euler - Problem 45

Problem 45 です。

この問題は、ちょっといやらしいです。

n = 2 * m - 1 の時、Tn = Hm になるので、六角数は完全に三角数に含まれてしまいます。つまり、六角数であれば、必ず三角数になるのです。

ということで、この問題を解くのに三角数の判定は必要ありません。


実際のコードは 144 番目以降の六角数を探していって、五角数かどうかを判定しています。

(define pentagon-number? (lambda (n) (let* ([a (sqrt (+ 1 (* 24 n)))] [b (/ (+ 1 a) 6)]) (if [positive-integer? b] b #f)))) (define hexagon-number (lambda (n) (- (* 2 n n) n))) (define problem-045 (lambda (n) (do ([i n (+ i 1)]) ([pentagon-number? (hexagon-number i)] (printf "~d~%" (hexagon-number i)))))) (problem-045 144)

ruby で書くとこんな感じでしょうか?

class Integer # = 五角数であれば、何番目かを返す。 def pentagon? x = (1 + Math.sqrt(1 + 24 * self)) / 6 if (x == x.to_i) then return x.to_i else return false end end # = 六角数を求める。 def hexagon return (2 * self * self - self) end end 144.upto(1.0/0.0) do |i| h = i.hexagon if (h.pentagon?) then puts h break end end

2009年5月 5日 (火)

Scheme でクイックソート

あるブログに、「schemeでクイックソート」という記事を見かけました。

コードを書いた後に

ふと思い立って書いたけどやっぱschemeめんどくさいな。
schemeというかlisp特有の括弧が面倒なんだけど。

と、書いてあります。


括弧に関しては、慣れるまではたしかにめんどうかも……。でも、ちゃんとしたエディタを使えば、困ることはほとんどないはず。

問題は、コードのほう。確かに面倒なことをしています。

では、実際のコードをご覧ください。

(define (partition proc input-list) (define left '()) (define right '()) (define (fork elt) (if (proc elt) (set! left (cons elt left)) (set! right (cons elt right)))) (for-each fork input-list) (cons left right)) (define (qsort input-list compare) (define result #f) (if (null? input-list) '() (begin (set! result (partition (lambda (elt) (compare elt (car input-list))) (cdr input-list))) (append (qsort (car result) compare) (list (car input-list)) (qsort (cdr result) compare))))) (define (compare a b) (> a b)) (display (qsort '(3 4 0 1 2 4 0 1 -1) compare))

この記事からは実際に使っている Scheme の処理系までは分かりませんでしたが、もし "filter" が使えるなら、もっとすっきり書けます。

(define q-sort (lambda (pred? lst) (if (or (null? lst) (null? (cdr lst))) lst (let* ((a (car lst)) (befor (filter (lambda (x) (pred? x a)) (cdr lst))) (after (filter (lambda (x) (not (pred? x a))) (cdr lst)))) (append (q-sort pred? befor) (list a) (q-sort pred? after)))))) (display (qsort > '(3 4 0 1 2 4 0 1 -1)))

まあ、1 つのリストを条件に沿って 2 つに分けるために "filter" を 2 回使うのが非効率的だと考えるなら、新しく関数を作る手もありますが……。

Scheme は、ちゃんと勉強するとすごく使いやすい言語だと思っています。考えたことが比較的ストレートにコードに書けるので……。

ただ、手続き型言語に慣れ親しんだ人にとって、それまでの常識が通用しないところも多々あるので、慣れるまでは大変かもしれませんね。


追記:コメントもトラックバックも不可のブログはどうかと思うぞ!

« 2009年4月 | トップページ | 2009年6月 »

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            
フォト

最近のトラックバック

無料ブログはココログ