WindVoiceの日記： 【続２】笑わない数学者の問題、n=10の途中経過 5
日記 by
WindVoice
昨日の日記で、ボールが10個の場合は計算しないようなことを言いましたが、本日会社を休んだので、少し実行しました。
昨日のスクリプトにリジューム機能をつけて、途中から計算できるようにしています。10個のボールの選び方は、5812通り見つかりますが、2722/5812まで計算が終ったところで、5通りの成功例が見つかっています。
昨日のスクリプトにリジューム機能をつけて、途中から計算できるようにしています。10個のボールの選び方は、5812通り見つかりますが、2722/5812まで計算が終ったところで、5通りの成功例が見つかっています。
(1,5,4,13,3,8,7,12,2,36)
(1,6,9,11,29,4,8,2,3,18)
(1,4,3,10,2,9,14,16,6,26)
(1,4,2,20,8,9,23,10,3,11)
(1,3,9,11,6,8,2,5,28,18)
現状、以上です。残りは週末あたりにでもするでしょう。
ところで、私の興味はすでに答えがあるなしではなくなっており、効率の良いアルゴリズムのほうに向かっています。10個は現在のままで8時間くらいで終わりそうなので頑張れますが、11個になるとお手上げです。おそらく10個の100倍くらいの時間がかかるからです。アルゴリズムを大きく改善できない限り、計算の限界に来てしまいます。そこに、改善のし甲斐があります。
で、AC#1567409さんに頂いたコメントにある方法をアルゴリズム化すべく検討中ですが…… 小さな番号のつながりを並べ替えたりするあたりが、Perlで管理するのはちょっと大変かなと。オブジェクト指向言語のほうが直感的にプログラミングできそうなので、Javaで作り直すかもしれません。や、Perlだってオブジェクト作れるよ！ という人がいるとは思うんですが、なんかめんどくさそうなんですよ。喰わず嫌いですけど。
おひさしぶりですー (スコア:1)
s/(1,5,9,11,29,4,8,2,3,18)/(1,6,9,11,29,4,8,2,3,18)/;
:-)
この問題、5つのバージョンがむかーーしの算数オリンピックに出題されました。僕が小学生の頃ですが。
なつかしいなー、まさかこんなところでであうなんて。
Re:おひさしぶりですー (スコア:2)
もう少し能率のよいアルゴリズム（と、思っているもの）を実装中です！
人生は七転び八起き、一日は早寝早起き
Re:おひさしぶりですー (スコア:1)
なんとなくC++で書いてみました（卑怯
http://srad.jp/~pascal/journal/476473 [srad.jp]
うーなんか行き詰まりました。
Re:おひさしぶりですー (スコア:2)
いまJavaで書いているんですけど、ちゃんと動くにはまだ少し時間がかかります。
早ければ、明日、かも。でもまだパフォーマンスまではわかりません。
人生は七転び八起き、一日は早寝早起き
Re:おひさしぶりですー (スコア:1)
単位は秒ですー。
ちゃんと読んでないんですが、WindVoiceさんのコードとの違いは、
* (n倍速): sort_and_checkの並べ替え部分を高速に書いている
* (5倍速): 先頭部分が[1,2,3]のように絶対に答えにならないような並べ替えはそもそも生成しない
* (2倍速): LogicalにValidなコード変更(含hack)
* (n倍速): PerlじゃなくてC++
ってあたりかなぁと思っています。hackはありますが、「3がないときには1と2が必ず隣」のようなintelligentなことはしていなかったりします。
あとでコード晒しますねー。