トップ «前の日記(2008-06-03) 最新 次の日記(2008-06-05)» 編集

日々の破片

Subscribe with livedoor Reader
著作一覧

2008-06-04

_ 配列を作る

aからbまでを要素に持つ配列の作り方。

(a..b).to_a

(いつも忘れるのでメモ)

_ 再帰ではない方法

TopCoderの最初の練習問題(チュートリアルではなくアリーナのほうのやつ)のアドバンスがどうやってもできずにえらく悩む。

1から与えられた数までの集合(たとえば、与えられた数が4なら、1,2,3,4)から、与えられた桁数を埋める数字を作る(たとえば与えられた数が3なら、123とか431とか)。

この時、作られた数字の並びが、左側に対して等しいか大きくなるような数は何通りできるか? という問題。たとえば、上の集合と桁であれば、123はOK、111もOK。でも、121はNG。

これは再帰を使えばすぐに解ける。といってもすぐにできたわけではないのが悲しいところであるが。

#最後のパラメータはデバッグ用
def count_r(start, range, depth, a)
  if depth == 0
    p a if $DEBUG
    return 1
  end
  r = 0
  start.upto(range) do |is|
    a.push is
    r += count_r(is, range, depth - 1, a)
    a.pop
  end
  r
end
puts "4, 3(r)=" + count_r(1, 4, 3, []).to_s
puts "4, 4(r)=" + count_r(1, 4, 4, []).to_s
puts "4, 5(r)=" + count_r(1, 4, 5, []).to_s
puts "93, 8(r)=" + count_r(1, 93, 8, []).to_s

最初の3つはすぐに求まる。

4, 3(r)=20
4, 4(r)=35
4, 5(r)=56

だが、4つ目(実際の問題のINDIGOのはず)は無限とも思われる時間がかかっても終わらない。もちろんYARVじゃなくてJavaで書いても同じだ。

ということは、もっと賢い(というか、全件を求めているのだから単に力任せで少しも賢くはないから、「もっと」というのは変だな)アルゴリズムがあるはずだ。

が、これがわからない。頭の中には左から右に枝分かれする絵があるのだが、再帰を使ってすべての枝をたどる方法ではなく、それを計算で求める方法がわからない。

で、考えていた。ほぼ1日。正味でも数時間かも。

さっきわかった。1から4の場合であれば

[1, 1, 1, 1]
[4, 3, 2, 1]
[10, 6, 3, 1]
[20, 10, 4, 1]

ということか(数字自体は見えていたのだが、配列に入れることで求め方がわかったということ)。その要素から右端までの要素の総和が次ぎの要素となる。

それにしても、こういうの(あるいはもっと賢い方法)をさっと考えつく人がうじゃうじゃいるわけだから、世の中は広い。

_ >P31 1.9 や JRuby は green thread ではない気がしますね

いや、だから、今の、ステイブルなバージョンについて書くと(言葉は違うが)最初に書いてあるじゃん。あと、JRubyはスコープ外。

まるごと Ruby! Vol.1(るびきち/arton/大場 光一郎/高井 直人/後藤 謙太郎/新井 俊一/瀧内 元気/cuzic/倉貫 義人/大場 寧子/久保 優子/十河 学/舞波)

正誤表とサンプルダウンロード

>特集1 が Java との比較ってのもすごいな

これは同意。正直、JRubyの記事が最初に来て、それに対しての補完(じゃないな。カウンターでもないし、蛇足と言う気はないし)になるのかと思ってた。

>Lisp 涙目

なぜ?

2008年06月03日の日記

_ コンピュータにやらせる

inabaさん(最初、間違えて書いてましたごめんなさい)の指摘に衝撃を受ける。

その通りだ。

やっていることは既に求めた枝の数の足し込みなのだから、キャッシュして利用すれば良い、ということもそうだが、それより僕が思いつかなかったのは、引数の組がそのまま枝の形(葉の数)だという点。これか。

すごく勉強になった。ありがとうございます。

晒してみるものだなぁ。

本日のツッコミ(全5件) [ツッコミを入れる]
_ yadokarielectric (2008-06-04 06:40)

> Lisp 涙目<br>「lambdaをそう説明するか!」ということではないかと

_ arton (2008-06-04 08:36)

難しいですねぇ。高杉晋作の説明するのに木戸孝允を出したら、吉田松陰が涙目という感じ?

_ arton (2008-06-04 11:42)

更新ができないのは何故だ?

_ aki (2008-12-27 16:22)

> [1, 1, 1, 1]<br>> [4, 3, 2, 1]<br>> [10, 6, 3, 1]<br>> [20, 10, 4, 1]<br>これは「パスカルの三角形」と呼ばれるものですね。

_ arton (2008-12-27 20:50)

>これは「パスカルの三角形」と呼ばれるものですね。<br>あ、本当だ。気づきませんでした。ありがとうございます。<br>http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2


2003|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|

ジェズイットを見習え