電卓プログラムの改良 (2)
今回はベクタを使って簡単なサンプルプログラムを作ってみましょう。
●ライブラリのロード
まず最初に、ライブラリをロードする機能を追加します。次のプログラムを見てください。
リスト : ライブラリのロード
func loadLib(name string) {
var lex Lex
file, err := os.Open(name)
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
defer func(){
err := recover()
file.Close()
if err != nil {
fmt.Fprintf(os.Stderr, "%s: %v, %s\n", name, err, lex.Position)
os.Exit(1)
}
}()
lex.Init(file)
for {
lex.getToken()
if lex.Token == scanner.EOF {
break
} else if lex.Token == DEF {
defineFunc(&lex)
} else {
e := expression(&lex)
if lex.Token != ';' {
panic(fmt.Errorf("invalid expression"))
}
e.Eval(nil)
}
}
}
func main() {
initKeyTable()
initFunc()
for _, name := range os.Args[1:] {
loadLib(name)
}
var lex Lex
lex.Init(os.Stdin)
for {
if toplevel(&lex) { break }
}
}
ライブラリはコマンドラインで指定します。
$ calc6 file1 file2 ...
複数のファイルを指定することができます。関数 main で Args からファイル名を取り出し、それを関数 loadLib に渡します。loadLib の処理は Open で名前 name のファイルをオープンし、ファイル構造体 file を let.Init に渡して scanner を初期化します。そのあとの処理は関数 toplevel とほとんど同じですが、ファイルの終了 (scanner.EOF) を検出したら for ループを脱出することに注意してください。ファイルのクローズは defer 文で行います。
エラーが発生した場合、scanner の Position にはファイルを読み込んだ最後の位置 (行番号 : カラム番号) が記憶されているので、それを表示します。エラーの位置とは必ずしも一致しませんが、ライブラリを修正するときの参考になると思います。
●ベクタの合計値
それではベクタを操作するプログラムを作りましょう。まずは最初に、ベクタの合計値を求める関数 sum を作ります。
リスト : ベクタの合計値を求める
def sum(xs)
let
a = 0, i = 0
in
while i < len(xs) do
a = a + xs[i],
i = i + 1
end,
a
end
end
ベクタの要素を変数 a に加算していくだけなので、難しいところはないでしょう。
簡単な実行例を示します。
Calc> sum([1,2,3,4,5,6,7,8,9,10]); 55 Calc> sum(vector(10, 10)); 100
●最大値と最小値
次は、ベクタの中から最大値を求める関数 maximum と最小値を求める minimum を作ります。
リスト : 最大値と最小値を求める
def max(a, b)
if a > b then
a
else
b
end
end
def min(a, b)
if a < b then
a
else
b
end
end
def maximum(xs)
let
a = xs[0],
i = 1
in
while i < len(xs) do
a = max(a, xs[i]),
i = i + 1
end,
a
end
end
def minimum(xs)
let
a = xs[0],
i = 1
in
while i < len(xs) do
a = min(a, xs[i]),
i = i + 1
end,
a
end
end
関数 max は大きいほうの引数を返し、関数 min は小さいほうの引数を返します。maximum は変数 a に xs[0] の要素をセットし、残りの要素と a を max で比較して、大きなほうを a にセットします。minimum も同様です。
簡単な使用例を示します。
Calc> maximum([5,4,6,3,7,2,8,1,9,0]); 9 Calc> minimum([5,4,6,3,7,2,8,1,9,0]); 0
●データの探索
次はデータの探索処理を作ります。ベクタの中からデータを「線形探索」する処理は次のようになります。
リスト : データの探索
def find(x, v)
let
i = 0, k = len(v)
in
while i < k and v[i] != x do
i = i + 1
end,
i < k
end
end
関数 find はベクタ v の中から引数 x と等しいデータを探します。while 文でリストの要素を一つずつ順番に取り出して x と比較します。等しい場合は繰り返しを中断します。そして、最後に i < k をチェックします。i と k が等しい場合、ベクタの中に x と等しい要素はないので偽 (0) を返します。そうでなければ真 (1) を返します。
簡単な実行例を示します。
Calc> find(0, [1,2,3,4,5,6,7,8]); 0 Calc> find(1, [1,2,3,4,5,6,7,8]); 1 Calc> find(5, [1,2,3,4,5,6,7,8]); 1 Calc> find(8, [1,2,3,4,5,6,7,8]); 1 Calc> find(9, [1,2,3,4,5,6,7,8]); 0
関数 position は見つけた要素の位置を返します。次のリストを見てください。
リスト : 位置を返す
def position(x, v)
let
i = 0, k = len(v)
in
while i < k and v[i] != x do
i = i + 1
end,
if i < k then i else -1 end
end
end
position の処理は find とほぼ同じです。while 文のあとで i < k をチェックします。真であれば位置 i を返し、そうでなければ -1 を返します。
簡単な実行例を示します。
Calc> position(0, [1,2,3,4,5,6,7,8]); ~1 Calc> position(1, [1,2,3,4,5,6,7,8]); 0 Calc> position(5, [1,2,3,4,5,6,7,8]); 4 Calc> position(8, [1,2,3,4,5,6,7,8]); 7 Calc> position(9, [1,2,3,4,5,6,7,8]); ~1
position は最初に見つけた要素の位置を返しますが、同じ要素がベクタに複数個あるかもしれません。そこで、要素の個数を数える関数を作ってみましょう。次のリストを見てください。
リスト : 個数を返す
def count(x, v)
let
i = 0, c = 0, k = len(v)
in
while i < k do
if v[i] == x then c = c + 1 end,
i = i + 1
end,
c
end
end
局所変数 c を 0 に初期化し、x と等しい要素を見つけたら c の値を +1 します。最後に c を返します。
簡単な実行例を示します。
Calc> count(1, [1,1,2,1,2,3,1,2,3,4]); 4 Calc> count(2, [1,1,2,1,2,3,1,2,3,4]); 3 Calc> count(3, [1,1,2,1,2,3,1,2,3,4]); 2 Calc> count(4, [1,1,2,1,2,3,1,2,3,4]); 1 Calc> count(5, [1,1,2,1,2,3,1,2,3,4]); 0
このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかります。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間かかかるのであれば、次に取り上げる「二分探索」や他の高速な探索アルゴリズム [*1] を使ってみてください。
[*1] 基本的なところでは、「ハッシュ法」や「二分探索木」などがあります。
●二分探索
次は、高速なデータ探索アルゴリズムである「二分探索（バイナリサーチ：binary searching）」を作りましょう。線形探索の実行時間は要素数 N に比例するので、数が多くなると時間がかかるようになります。これに対し二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく必要があります。このため、二分探索は線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。
上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
それでは、ベクタからデータを二分探索するプログラムを作ってみましょう。二分探索は簡単にプログラムできます。次のリストを見てください。
リスト : 二分探索
def bsearch(x, v, low, high)
let
result = 0
in
while low <= high and result == 0 do
let
mid = (low + high) / 2
in
if v[mid] == x then
result = 1
else
if v[mid] < x then
low = mid + 1
else
high = mid - 1
end
end
end
end,
result
end
end
def binarySearch(x, v)
bsearch(x, v, 0, len(v) - 1)
end
実際の処理は関数 bsearch で行います。引数 low と high は探索する区間を表します。そして、while ループで探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて mid にセットします。if 文で v[mid] と x を比較し、等しい場合は探索成功です。result に 1 をセットします。これで while ループを脱出することができます。
x が大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、x が小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し、最後に reuslt を返します。
簡単な実行例を示します。
Calc> binarySearch(50, [10,20,30,40,50,60,70,80,90,100]); 1 Calc> binarySearch(10, [10,20,30,40,50,60,70,80,90,100]); 1 Calc> binarySearch(100, [10,20,30,40,50,60,70,80,90,100]); 1 Calc> binarySearch(0, [10,20,30,40,50,60,70,80,90,100]); 0 Calc> binarySearch(110, [10,20,30,40,50,60,70,80,90,100]); 0 Calc> binarySearch(55, [10,20,30,40,50,60,70,80,90,100]); 0
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。
したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
●バブルソート
次は簡単なソートプログラムを作ってみましょう。「バブルソート (buble sort)」は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。
隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がってきます。これをデータ数だけ繰り返せばソートが完了します。
9 5 3 7 6 4 8 交換しない
~~~
9 5 3 7 6 4 8 交換する
~~~
9 5 3 7 4 6 8 交換する
~~~
9 5 3 4 7 6 8 交換しない
~~~
9 5 3 4 7 6 8 交換する
~~~
9 3 5 4 7 6 8 交換する
~~~
3 9 5 4 7 6 8 いちばん小さいデータが決定する
+ 残りのデータに対して同様な操作を行う
図 : バブルソート
これをそのままプログラムすると次のようになります。
リスト : バブルソート
def bubleSort(v)
let
i = 0, k = len(v) - 1
in
while i < k do
let
j = k
in
while i < j do
if v[j - 1] > v[j] then
let tmp = v[j] in
v[j] = v[j - 1],
v[j - 1] = tmp
end
end,
j = j - 1
end
end,
i = i + 1
end
end,
v
end
最初のループで k 回 (データの個数 - 1) だけ繰り返します。2 番目のループで v の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。とても簡単ですね。
簡単な実行例を示しましょう。
Calc> bubleSort([5,6,4,7,2,8,1,9,3,0]); [0 1 2 3 4 5 6 7 8 9] Calc> bubleSort([9,8,7,6,5,4,3,2,1,0]); [0 1 2 3 4 5 6 7 8 9] Calc> bubleSort([0,1,2,3,4,5,6,7,8,9]); [0 1 2 3 4 5 6 7 8 9]
●単純挿入ソート
次は単純挿入ソートを作ります。基本的な考え方はとても簡単です。ソート済みのベクタに新しいデータを挿入していくことでソートを行います。次の図を見てください。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
プログラムは次のようになります。
リスト : 挿入ソート
def insertSort(v)
let
i = 1, k = len(v)
in
while i < k do
let
j = i, tmp = v[i]
in
while j > 0 and v[j - 1] >= tmp do
v[j] = v[j - 1],
j = j - 1
end,
v[j] = tmp
end,
i = i + 1
end
end,
v
end
len(v) でベクタの長さを求めて変数 k にセットします。最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行っていて、このときデータの移動も同時に行っています。
それでは実行してみましょう。
Calc> insertSort([5,6,4,7,2,8,1,9,3,0]); [0 1 2 3 4 5 6 7 8 9] Calc> insertSort([9,8,7,6,5,4,3,2,1,0]); [0 1 2 3 4 5 6 7 8 9] Calc> insertSort([0,1,2,3,4,5,6,7,8,9]); [0 1 2 3 4 5 6 7 8 9]
バブルソート、選択ソート、挿入ソートはデータ数が多くなると実行時間がかかります。データ数を N とすると、実行時間は N の 2 乗に比例します。これらのソートは簡単ですが遅いアルゴリズムなのです。
●クイックソート
次は高速なソートアルゴリズムとして有名な「クイックソート (quick sort)」を作ります。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々の区間を同様に分割して 2 つの区間に分けます。最後は区間の要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つの区間について再び同様な分割を行う
図 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は中央にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つの区間に適用します。これは再帰定義を使えば簡単に実現できます。分割した区間の要素数が 1 になったときが再帰の停止条件になります。
これをそのままプログラムすると次のようになります。
リスト : クイックソート
def qsort(v, low, high)
let
pivot = v[(low + high) / 2],
flag = 1,
i = low,
j = high
in
while flag do
while v[i] < pivot do i = i + 1 end,
while pivot < v[j] do j = j - 1 end,
if i < j then
let tmp = v[i] in
v[i] = v[j],
v[j] = tmp,
i = i + 1,
j = j - 1
end
else
flag = 0
end
end,
if low < i - 1 then qsort(v, low, i - 1) end,
if j + 1 < high then qsort(v, j + 1, high) end
end
end
def quickSort(v)
qsort(v, 0, len(v) - 1),
v
end
関数 qsort の引数 v がソートするベクタ、low が区間の下限値、high が区間の上限値です。qsort は v の low から high までの区間をソートします。まず最初に、区間の中央にあるデータを枢軸 pivot として選び、pivot を基準にして区間を 2 つに分けます。
while ループの中の最初の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。flag を 0 に書き換えて while ループを終了します。そうでなければお互いの要素を交換します。
次に、分割した区間に対して qsort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
簡単な実行例を示します。
Calc> quickSort([5,6,4,7,2,8,1,9,3,0]); [0 1 2 3 4 5 6 7 8 9] Calc> quickSort([9,8,7,6,5,4,3,2,1,0]); [0 1 2 3 4 5 6 7 8 9] Calc> quickSort([0,1,2,3,4,5,6,7,8,9]); [0 1 2 3 4 5 6 7 8 9]
●エラトステネスの篩
次は素数を求めるプログラムを作りましょう。最初に、2 から N までの整数列を生成します。先頭の 2 は素数なので、この整数列から 2 で割り切れる整数を取り除き除きます。2 で割り切れる整数が取り除かれたので、残った要素の先頭が素数になります。先頭要素は 3 になるので、今度は 3 で割り切れる整数を取り除けばいいのです。このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩 (ふるい)」といいます。
プログラムは次のようになります。
リスト : エラトステネスの篩
def sieveSub(n, m, buff)
let
i = n + n
in
while i <= m do
buff[i] = 1,
i = i + n
end
end
end
def printPrime(n)
print(n), print(" ")
end
def sieve(n)
let
hurui = vector(n + 1, 0),
i = 3
in
sieveSub(2, n, hurui),
while i * i < n do
if hurui[i] == 0 then
sieveSub(i, n, hurui)
end,
i = i + 2
end,
printPrime(2),
i = 3,
while i <= n do
if hurui[i] == 0 then
printPrime(i)
end,
i = i + 2
end
end
end
関数 sieve の変数 hurui で整数列を表します。vector で大きさ n + 1 のベクタを生成し、それを hurui にセットします。0 で素数を表し、素数でない場合は 1 をセットします。vector で初期値に 0 を指定しているので、最初はすべての数が素数ということになります。
次に、関数 sieveSub を呼び出して 2 の倍数を削除します。sieveSub の引数 n が素数、m がベクタの大きさ、buff がベクタです。最初に、局所変数 i を n + n に初期化します。そして、while ループで buff[i] を 1 に書き換えて i に n を加算していけば、n の倍数を削除することができます。
あとは 3 から始まる奇数列を while ループで生成し、hurui[i] が 0 ならば sieveSub で i の倍数を削除します。最後の while ループで、hurui の中に残った素数を表示します。
簡単な実行例を示します。
Calc> sieve(100); 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 0
最後の 0 は sieve の返り値 (while 式の値) です。
●素因数分解
エラトステネスの篩と同じ考え方で素因数分解を行うことができます。素因数分解とは、素数でない整数 (合成数) を素数の積の形に書き表すことです。たとえば、12 は 2 * 2 * 3 と素因数分解することができます。プログラムは次のようになります。
リスト : 素因数分解
def factorization(n)
while n % 2 == 0 do
print(2),
print(" "),
n = n / 2
end,
let
i = 3
in
while i * i <= n do
while n % i == 0 do
print(i),
print(" "),
n = n / i
end,
i = i + 2
end,
if n > 1 then println(n) end,
1
end
end
最初に 2 で割り算してから、奇数で割り算していきます。割り算するときは、その数で割り切れるあいだは割り算を続けることに注意してください。たとえば、27 を素因数分解すると 3 * 3 * 3 になりますが、3 を一回だけしか割り算しないと、結果は 3 * 9 のように素数ではない数が含まれてしまいます。
実行結果は次のようになります。
Calc> factorization(12); 2 2 3 1 Calc> factorization(12345678); 2 3 3 47 14593 1 Calc> factorization(1234567890); 2 3 3 5 3607 3803 1
最後の 1 は factorization() の返り値です。どの数も素数で、2 * 3 * 3 * 5 * 3607 * 3803 を計算すると 1234567890 になります。なお、これはとても単純なアルゴリズムなので、大きな整数の素因数分解には適していません。巨大な合成数の素因数分解はとても難しい問題です。興味のある方は素因数分解について調べてみてください。
●木の操作関数
次はベクタを木とみなして、要素 (葉) を数える関数 countLeaf を作ります。
リスト : 要素 (葉) の個数を求める
def countLeaf(v)
let
c = 0, i = 0, k = len(v)
in
while i < k do
if isVec(v[i]) then
c = c + countLeaf(v[i])
else
c = c + 1
end,
i = i + 1
end,
c
end
end
countLeaf も簡単です。局所変数 c に要素の個数を格納します。v[i] がベクタならば countLeaf を再帰呼び出しし、その返り値を c に加算します。そうでなければ、c を +1 します。
簡単な実行例を示します。
Calc> countLeaf([1,[2,[3,[4,[5],6],7],8],9]); 9
最後に、ベクタを木とみなして、木を平坦化する関数 flattern を作ります。
リスト : 平坦化
def flatSub(v, flat, i)
let
j = 0, k = len(v)
in
while j < k do
if isVec(v[j]) then
i = flatSub(v[j], flat, i)
else
begin flat[i] = v[j], i = i + 1 end
end,
j = j + 1
end,
i
end
end
def flatten(v)
let
flat = vector(countLeaf(v), 0)
in
flatSub(v, flat, 0),
flat
end
end
電卓プログラムのベクタは「可変長配列」ではないので、あらかじめ countLeaf で要素数を数え、その大きさのベクタを vector で生成して変数 flat にセットします。実際の処理は関数 flatSub で行います。引数 i は flat に書き込む位置を表します。flatSub は flat に書き込む位置を返すことに注意してください。あとは、flatSub で木を巡回して、要素 v[j] を flat[i] に書き込みます。最後に flat を返します。
簡単な実行例を示します。
Calc> flatten([1,[2,[3,[4,[5],6],7],8],9]); [1 2 3 4 5 6 7 8 9]
今回はここまでです。次回は電卓プログラムに関数型言語の機能を追加してみましょう。具体的には、関数を値として扱うことができるように修正し、新しい機能として「クロージャ (closure)」を追加します。
●プログラムリスト
//
// vector.cal : ベクタ用操作関数
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
// 最大値と最小値
def max(a, b)
if a > b then
a
else
b
end
end
def min(a, b)
if a < b then
a
else
b
end
end
def maximum(xs)
let
a = xs[0],
i = 1
in
while i < len(xs) do
a = max(a, xs[i]),
i = i + 1
end,
a
end
end
def minimum(xs)
let
a = xs[0],
i = 1
in
while i < len(xs) do
a = min(a, xs[i]),
i = i + 1
end,
a
end
end
// 合計値
def sum(xs)
let
a = 0, i = 0
in
while i < len(xs) do
a = a + xs[i],
i = i + 1
end,
a
end
end
// ベクタの探索
def find(x, v)
let
i = 0, k = len(v)
in
while i < k and v[i] != x do
i = i + 1
end,
i < k
end
end
def position(x, v)
let
i = 0, k = len(v)
in
while i < k and v[i] != x do
i = i + 1
end,
if i < k then i else -1 end
end
end
def count(x, v)
let
i = 0, c = 0, k = len(v)
in
while i < k do
if v[i] == x then c = c + 1 end,
i = i + 1
end,
c
end
end
// バブルソード
def bubleSort(v)
let
i = 0, k = len(v) - 1
in
while i < k do
let
j = k
in
while i < j do
if v[j - 1] > v[j] then
let tmp = v[j] in
v[j] = v[j - 1],
v[j - 1] = tmp
end
end,
j = j - 1
end
end,
i = i + 1
end
end,
v
end
// 単純挿入ソート
def insertSort(v)
let
i = 1, k = len(v)
in
while i < k do
let
j = i, tmp = v[i]
in
while j > 0 and v[j - 1] >= tmp do
v[j] = v[j - 1],
j = j - 1
end,
v[j] = tmp
end,
i = i + 1
end
end,
v
end
// クイックソート
def qsort(v, low, high)
let
pivot = v[(low + high) / 2],
flag = 1,
i = low,
j = high
in
while flag do
while v[i] < pivot do i = i + 1 end,
while pivot < v[j] do j = j - 1 end,
if i < j then
let tmp = v[i] in
v[i] = v[j],
v[j] = tmp,
i = i + 1,
j = j - 1
end
else
flag = 0
end
end,
if low < i - 1 then qsort(v, low, i - 1) end,
if j + 1 < high then qsort(v, j + 1, high) end
end
end
def quickSort(v)
qsort(v, 0, len(v) - 1),
v
end
// 二分探索
def bsearch(x, v, low, high)
let
result = 0
in
while low <= high and result == 0 do
let
mid = (low + high) / 2
in
if v[mid] == x then
result = 1
else
if v[mid] < x then
low = mid + 1
else
high = mid - 1
end
end
end
end,
result
end
end
def binarySearch(x, v)
bsearch(x, v, 0, len(v) - 1)
end
// 素数
def sieveSub(n, m, buff)
let
i = n + n
in
while i <= m do
buff[i] = 1,
i = i + n
end
end
end
def printPrime(n)
print(n), print(" ")
end
def sieve(n)
let
hurui = vector(n + 1, 0),
i = 3
in
sieveSub(2, n, hurui),
while i * i < n do
if hurui[i] == 0 then
sieveSub(i, n, hurui)
end,
i = i + 2
end,
printPrime(2),
i = 3,
while i <= n do
if hurui[i] == 0 then
printPrime(i)
end,
i = i + 2
end
end
end
// 素因数分解
def factorization(n)
while n % 2 == 0 do
print(2),
print(" "),
n = n / 2
end,
let
i = 3
in
while i * i <= n do
while n % i == 0 do
print(i),
print(" "),
n = n / i
end,
i = i + 2
end,
if n > 1 then println(n) end,
1
end
end
// 葉の個数を求める
def countLeaf(v)
let
c = 0, i = 0, k = len(v)
in
while i < k do
if isVec(v[i]) then
c = c + countLeaf(v[i])
else
c = c + 1
end,
i = i + 1
end,
c
end
end
// 平坦化
def flatSub(v, flat, i)
let
j = 0, k = len(v)
in
while j < k do
if isVec(v[j]) then
i = flatSub(v[j], flat, i)
else
begin flat[i] = v[j], i = i + 1 end
end,
j = j + 1
end,
i
end
end
def flatten(v)
let
flat = vector(countLeaf(v), 0)
in
flatSub(v, flat, 0),
flat
end
end
改訂 2021 年 12 月 22 日