2011-06-01から1ヶ月間の記事一覧

ScalaでProject Euler(32)

Problem 17この問題はoneがいくつ、twoがいくつと数えたほうが速いです。ただコーディングがひたすらめんどくさいです。

秀丸でCOMを操作する

いつの間にか秀丸のマクロでCOMを操作することができるようになっていたようです。これでなんでもできるようになりますね! それは極端としてもいろいろできるようになります。例えばUNIXのduコマンドと同じようにフォルダのサイズを再帰的に表示しましょう…

n次方程式の判別式の項数

京大、16次方程式の判別式計算に成功 | エンタープライズ | マイコミジャーナル たぶんここに書いた話と同じです。n次方程式の判別式の具体的表示(1) - 桃の天然水 n次方程式の判別式の具体的表示(2) - 桃の天然水判別式は、根の差積を自乗したものなの…

ScalaでProject Euler(31)

Problem 17 Map Mapをまとめて作るには、キーと値のタプルのリストを使います。 val words = List((1, "one"), (2, "two"), ...) val maplen = words.map(x => (x._1, x._2.size)).toMap 上は、数 → 文字数というマップを作っています。 あとは1〜1000の文字…

Project Euler 344

http://projecteuler.net/index.php?section=problems&id=344出題されて4時間以上経ってから問題見たが、まだ誰も解けていなかった。 まだ1行もコード書いていないが、c = 1のときだけは解けた。

サイコロの目が6つとも出るまでにかかる回数の確率分布

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2011/02/26メディア: 単行本購入: 19人 クリック: 779回この商品を含むブログ (103件) を見る買って通勤時に4日で読んだけど、とにかく重い。持ち…

ScalaでProject Euler(30)

Problem 15多倍長整数を使えば簡単です。 def sum_digits(n :BigInt) :Int = if(n == 0) 0 else (n % 10).toInt + sum_digits(n / 10) val N = 1000 val n = (1 to N).foldLeft(BigInt(1))((x, y) => x * 2) println (sum_digits(n)) しかし、使わなくても簡…

ScalaでProject Euler(29)

Problem 15組み合わせの計算をLongの範囲に収まるように工夫する、くらいでしょうか。実質1行です。 def C(n :Int, m :Int) = (1 to m).foldLeft(1L)((x, y) => x * (n - y + 1) / y) val N = 40 val M = 20 println (C(N, M))

ScalaでProject Euler(28)

Problem 14 メモ化 配列を用意して一度計算したらそこに記憶していくとよいです。非常に速くなります。 配列を用意するので範囲が大きくなればその分大きなメモリが必要になりますが、そのときはメモ化の範囲を狭くするんでしょうね。 Benchmark Benchmarkは…

ScalaでProject Euler(27)

Problem 14 Rangeオブジェクトの罠 RangeオブジェクトはPythonのxrangeに似ています。すなわち、等差数列の最初と最後(と公差)だけ持ちます。 val N = 1e8.toInt println ((1 to N).reduceLeft(-_ + _)) しかし、一度なにか操作するとVectorオブジェクトに…

Project Euler 343

http://projecteuler.net/index.php?section=problems&id=343343なだけに立方数に関する問題、というのはProblem 341と同じで表面的なものかと最初は思っていた。だが、よく考えると違っていた。Problem 341はそうみせかけるための前振りだったのだ。立方数…

ScalaでProject Euler(26)

Problem 13 BigInt 今回は最初なので多倍長整数を使います。 多倍長整数のリテラルはこんな感じです。 BigInt("4637693767749000971") あとはIntなどと同じように扱えます。

ScalaでProject Euler(25)

Problem 12 option#map next_combination(Some(e2 :: tail)) match { case Some(b) => Some(e2 :: b) case None => None } は、 next_combination(Some(e2 :: tail)).map(e2 :: _) と書けるんですねえ。いや、書けなきゃおかしいと思ってましたが。 option#f…

Project Euler 341

http://projecteuler.net/index.php?section=problems&id=341ややこしそうだったからずっと放置していたが、組んでみたら簡単だった。 Gを素直に計算するとき、リストか何かが必要かと思ったが、こう書くとその必要はない。 from itertools import * def G()…

Project Euler 342

メインマシンがいかれてテンション下がり中。1週間くらいはこんな感じかな。http://projecteuler.net/index.php?section=problems&id=342難しそうだけど、ちょっと考えると枝刈りできて意外と簡単に求められる。と思ったら、数時間かかりそう。 枝刈りをちゃ…

ScalaでProject Euler(24)

Problem 12引き続き約数の個数がある数より大きい自然数を昇順に列挙する(1)でPythonで書いたコードをScalaにします。 Set Setはこんな感じに使います。 import scala.collection.mutable.Set val s = Set[Int]() s += 3 s += 1 s += 4 println (s) printl…

ScalaでProject Euler(23)

Problem 12引き続き約数の個数がある数より大きい自然数を昇順に列挙する(1)でPythonで書いたコードをScalaにします。 Option 指数の組合せに1加えて次の指数の組合せするPythonのコードは次のようでした。 for k in xrange(1, len(es0)): if es0[k-1] == …

ScalaでProject Euler(22)

Problem 12Pythonで書いたコードをScalaにします。 Ordering val pq = new PriorityQueue[(Int,List[Int])] とすると怒られます。List[Int]が比較できないからのようです。このようなときは自前の比較のためのオブジェクトを与えます。 import scala.collect…

約数の個数がある数より大きい自然数を昇順に列挙する(2)

前回の方法は、約数が小さいほうから順に指数の組合せを生成していきましたが、約数の個数が5万を超えるものを生成するのに2個から始めるというのはかなりムダがあるような気がしますね。実際のところ、ギリギリ5万個を超える指数の組合せ(一つでも指数が減…

約数の個数がある数より大きい自然数を昇順に列挙する(1)

Project EulerのProblem 12は三角数を昇順に列挙してその約数の個数が500より大きい最初の数を得ていましたが、Eulerianならきっと約数の個数が500より大きい自然数を昇順に列挙して最初に三角数になる数を見つけようとするでしょう。しかし、これが難しくて…

Project Euler 341

http://projecteuler.net/index.php?section=problems&id=341出遅れた。86は出たんだけど、それ以降はどうするんだろう。やや体調悪いし明日以降考えよう。

ScalaでProject Euler(21)

Problem 12500くらいなら前回の方法でも十分ですが、さらに大きくなると素数を求めるのにエラトステネスのふるいを使いたくなります。無限の素数列を作りたいので、例えば0〜99999までのエラトステネスのふるいをまず行って、そこまでの素数が尽きたら100000…

ScalaでProject Euler(20)

Problem 121から順に素因数分解していきます。偶数なら2で割って、一つずらして掛け算すれば三角数の素因数分解が生成されます。例えば、2332を[(2, 3), (3, 2)]と表して、 [] [] [(3, 1)] [(2, 1)] [(5, 1)] [(3, 1)] [] [] [(3, 1)] [(2, 1)] [(5, 1)] ---…