トップ «前の日記(2006-07-10) 最新 次の日記(2006-07-12)» 月表示 編集

日々の流転


2006-07-11 [長年日記]

λ. 非外延的集合論

<URL:http://d.hatena.ne.jp/ytb/20060702/p1>

ビックリさせてしまって済みません。非外延的集合論は存在自体は知っていましたが、こんなところに役に立つのか、というのが新鮮でした。

λ. キミならどう書く 2.0 - ROUND 2 -

与えられた範囲の中でCollatz予想の収束までのステップ数が最大となる値を求める問題。とりあえず、Haskellで超素朴なコードで試してみたら「h 1000000」に40秒くらいかかった。

import List

g 1 = 1
g n = 1 + g (if even n then n `div` 2 else 3*n + 1)

h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
    where c (_,x) (_,y) = x `compare` y 

実行結果。

Main> h 100
97
Main> h 1000000
837799

以下のようにして100000までの値をテーブル化すると7秒まで縮んだ。 更に効率化するにはどうすれば良いだろう?

import List
import Array

tableMax = 100000  
table = array (1, tableMax) [(k, g' k) | k <- [1..tableMax]]

g n = if n <= tableMax then table ! n else g' n

g' 1 = 1
g' n = 1 + g (if even n then n `div` 2 else 3*n + 1)

h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
    where c (_,x) (_,y) = x `compare` y
Tags: haskell

λ. めがまり (4)

めがまりをクリアした。

ボスラッシュに苦戦するうちにボスの弱点がわかってきたので、ボスラッシュは弱点の技で適当に倒す。が、妖夢とレミリアが依然として苦手。生身のパチュリーはサウザンドナイブズで華麗にスルー。パチュリーマシンはフォースクライシスと紅色マジックでたこ殴り。クリアはできたけど、もうE缶残ってないよ。

もう余力が無かったので、最終ステージではあっさりゲームオーバーに。コンティニュー。小悪魔はパターンが簡単なので慣れれば楽勝。パチュリーカプセルはどの攻撃を撃ってくるのかが判別できずにダメージを受けてしまうのが嫌。パチュリーカプセルがかなり上の位置に現れた場合にはホーミングアミュレットで攻撃し、 自機のすぐ上に現れたときにはゴーストカッターでザクザク斬る。ラストのメカパチュリーは例によってフォースクライシスと紅色マジックで攻撃。攻撃はそれなりに激しいが、ある程度ダメージを与えたあとは、エネルギーを溜めての体当たり(?)が多くなり、これは魔法の箒を使えば比較的簡単にかわせるので結構楽。最終ステージはE缶まったく無しでクリア。

クリア後、攻略サイトを眺めていて、M缶やS缶の存在、それから四季映姫ステージのショートカットとかを知って、結構ショック。次の目標はノーコンティニュークリア?

Tags: 東方
本日のツッコミ(全2件) [ツッコミを入れる]
ψ 向井 (2006-07-12 11:11)

実行しながらメモ化する方式を下記に書いてます。<br>http://haskell.g.hatena.ne.jp/jmk/20060711/1152631202<br>やってみたら、デカい値では Int だと g の引数が負値に突入してしまい h 1000000 はスタックオーバフローになってしまいましたが……。

ψ さかい (2006-07-13 14:42)

なんか副作用を使うのは負けのような気がした(^^; のでやらなかったのですが、実行しながらメモ化するのは「予め指定した範囲外もメモ化可能」という利点からでしょうか。<br>それと、更に大きな n について h n を求める場合には、テーブルが大きくなり過ぎないように古い値をテーブルから除く必要がありそうですが、そういうことも出来そうですね。