過去ログ

まるケン

#24876
あ、私のもtimeでの計測結果です。
rubyの起動時間等は、、、ま、誤差と言うことで。

ちなみに、#24874に晒したプログラムは、リアルタイムで挑戦したときのものでして、プログラムとしては直感的に考えられて、短く書けるっていうメリットの反面、決して効率のよいものではありませんでした。
（#24837や#24854をrubyで書き直したら、0.5秒とかで結果が出ました）

ということで、本日は会社にて「各種算術計算のアルゴリズムの調査および検証」というテーマで、もっと一般的な数字(ｍとｎを与える)順列のプログラムなどをしてみました。そしたら、プログラムは長くなっちゃったけど、実行時間は0.85秒まで短縮できました。

例によって、全角スペース使ってます。

# pPc
# Permutation

def perm(a, c)
　　if(c == 0) then
　　　　return []
　　end

　　if(c == 1) then
　　　　return a.map do |s| [s] ; end
　　end

　　r = Array.new
　　a.size.times do
　　　　j = a.shift
　　　　r += perm(a, c-1).map do |s| s.insert(0, j); end
　　　　a.push j
　　end
　　return r
end

if(ARGV.size < 2) then
　　p = 9
　　c = 5
else
　　p = ARGV[0].to_i
　　c = ARGV[1].to_i
end

a = (1..p).to_a
j = k = 0
perm(a, c).each do |s|
　　j += 1
　　k += 1 if (s.join('').to_i % 3 == 0)
end
p j, k

perm関数は、引数ａに要素を羅列した配列、ｃにその中から選ぶ数を与えると、要素数ｃの配列の配列を返すってなことになってます。
与えられた配列の先頭の要素をshiftで取り除き、再帰呼び出しでさらに計算させ、使った要素はpushで最後尾に連結するってのがミソです。でも、そのせいで結果は辞書的順番ではなくなっちゃってますが、、、

% ruby perm.rb
とかすれば、今回の問題の答えが出るし、
% ruby perm.rb 9 3
なんてすれば、全体の1/3にならないケースの検証もできます。

　　 4月12日（火） 17:23:02　　 MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋　　24878

過去問題一覧へ戻る