倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ!

Scalaアルゴリズム事典

素数の Lucas テスト

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回はメルセンヌ数(Mersenne Number)が素数であるかどうかを判定するリュカ・テスト (Lucas–Lehmer primality test) を見ていきます。メルセンヌ数とは を素数とし…

素因数分解

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 前回、素数列を生成するアルゴリズムを見ましたが、今回は素因数分解 (factorization into primes) をするアルゴリズムを見ていきます。参考 『Javaによるアルゴリズ…

素数

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 ちょっと別用で素数 (prime number) を生成するコードを書いたので、こちらのブログで整理しておきます。 別用記事で見たように Int や Long に対してなら2行で書けま…

最大公約数

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は最大公約数(GCD, Greatest Common Divsor)を求めるアルゴリズムを見ていきます。 最大公約数はアルゴリズムと言えばのユークリッド互除法で求められます。こ…

組合せの個数 その1

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ。 今回は組合せの個数を計算するアルゴリズム。 その1では、あまり実用的ではないです…

階乗と順列の個数

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は再帰関数の例としてよく出てくる自然数の階乗と、それに関連する順列の個数を計算するアルゴリズムを見ていきます。 再帰関数の例としてよく出てくると言っても…

順列生成 その2

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は前回に引き続き、全順列を生成するアルゴリズムを見ていきます。 全開は『Java によるアルゴリズム事典』に載っている4つのアルゴリズムのうち1つ目のものを見…

順列生成 その1

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回はある定まった次数(並べるモノの個数。 コード中では degree とする)の全順列を生成するアルゴリズムを見ていきます。 『Java によるアルゴリズム事典』には4…

順列の辞書順序による番号付け ~階乗進法編~

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は順列に辞書順序で番号を付けたとき、与えられた順列とその番号との相互の変換を考えます。 ただし番号は Int などの通常の整数値ではなく、階乗進法で表された…

階乗進法

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は、階乗進法 (factorial representation) という数の表し方を見ていきます。階乗進法10進法が10を基数にしている、つまり10の累乗の級数で表されるのに対して、…

次の順列

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 以前に置換のアルゴリズムを扱ったときに、『Java によるアルゴリズム事典』に「置換の生成」がなくておかしいなぁと思ってたら、「順列」「順列の生成」の項目にある…

チェックサムと ISBN 番号

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 『Java によるアルゴリズム事典』で、関数型プログラミングで書きやすそうなアルゴリズムがあったので Scala で書いてみた。 今回は、データに誤りが無いかチェックす…

全置換の生成

『Java によるアルゴリズム事典』には載ってなかったんですが、n 個のモノの全置換を生成するコードを見ていきます(目次)。Scala では List などの順序付きのコレクション(正確には scala.collection.SeqLike トレイトのサブ型)では permutations() メソ…

置換の符号

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 今回は指定された置換の符号を計算するアルゴリズム。 ここでは Java や Scala のコードで扱い易くするため、n 個の置換は1から n の整数ではなく、0から n-1 の整数…

Scala アルゴリズム事典

『Java によるアルゴリズム事典』に載ってるコードを Scala かつ再帰(できる限り末尾再帰)で書いていこうシリーズ。 と言っても、他のことで使うコードでこの本に載ってるアルゴリズムを使うときに記事更新するので、たまにしか記事書かないと思います。数…