このページは M.Hiroi が Scala の勉強で作成した簡単なプログラムをまとめたものです。拙作のページ Yet Another Prolog Problems や Yet Another Scheme Problems などの Scala バージョンになります。同じような問題が多くなると思いますが、あしからずご了承くださいませ。
整数 n から m までの和、二乗の和、三乗の和を求める関数 sumOfInt, sumOfSquare, sumOfCube を定義してください。
def sumOfInt(n: Int, m: Int): BigInt def sumOfSquare(n: Int, m: Int): BigInt def sumOfCube(n: Int, m: Int): BigInt
scala> sumOfInt(1, 1000) val res0: BigInt = 500500 scala> sumOfSquare(1, 1000) val res1: BigInt = 333833500 scala> sumOfCube(1, 1000) val res2: BigInt = 250500250000
点を多角形の形に並べたとき、その総数を「多角数 (polygonal number) 」といいます。三角形に配置したものを三角数、四角形に配置したものを四角数、五角形に配置したものを五角数といいます。三角数、四角数、五角数を下図に示します。
１ ３ ６ 10 15
● ● ● ● ●
●● ●● ●● ●●
●●● ●●● ●●●
●●●● ●●●●
●●●●●
図 : 三角数
|
１ ４ ９ 16 25
● ●● ●●● ●●●● ●●●●●
●● ●●● ●●●● ●●●●●
●●● ●●●● ●●●●●
●●●● ●●●●●
●●●●●
図 : 四角数
|
１ ５ 12 22
● ● ● ●
● ● ● ● ● ●
● ● ● ●
● ● ● ● ● ●
● ● ● ● ●
● ● ●
● ● ● ●
● ● ● ●
● ● ● ●
図 : 五角数
n 番目の p 角数を求める関数 polygonalNum を定義してください。
def polygonalNum(p : Int, n: Int) Int
scala> polygonalNum(3, 1) val res0: Int = 1 scala> polygonalNum(3, 2) val res1: Int = 3 scala> polygonalNum(3, 3) val res2: Int = 6 scala> polygonalNum(4, 1) val res3: Int = 1 scala> polygonalNum(4, 2) val res4: Int = 4 |
scala> polygonalNum(4, 3) val res5: Int = 9 scala> polygonalNum(5, 1) val res6: Int = 1 scala> polygonalNum(5, 2) val res7: Int = 5 scala> polygonalNum(5, 3) val res8: Int = 12 |
次の公式を使って平方根の整数部分を求める関数 sqrtInt を定義してください。
式 (1) は、奇数 1 から 2n - 1 の総和は \(n^2\) になることを表しています。式 (2) のように、整数 m の値が \(n^2\) より大きくて \((n + 1)^2\) より小さいのであれば、\(m\) の平方根の整数部分は \(n\) であることがわかります。これは \(m\) から奇数 \(1, 3, 5, \ldots, (2n - 1), (2n + 1)\) を順番に引き算していき、引き算できなくなった時点の \(\frac{2n + 1}{2} = n\) が m の平方根になります。参考文献『平方根計算法』によると、この方法を「めのこ平方」と呼ぶそうです。
def sqrtInt(n: Int) Int
scala> sqrtInt(100) val res0: Int = 10 scala> sqrtInt(1000) val res1: Int = 31 scala> sqrtInt(10000) val res2: Int = 100 scala> sqrtInt(123456789) val res3: Int = 11111
実数 \(a\) の平方根 \(\sqrt a\) の値を Newton (ニュートン) 法で求めてください。
def sqrt(n: Double): Double
scala> sqrt(2) val res0: Double = 1.414213562373095 scala> sqrt(3) val res1: Double = 1.7320508075688772 scala> sqrt(4) val res2: Double = 2.0 scala> sqrt(123456789) val res3: Double = 11111.111060555555
方程式を f(x), その導関数を f'(x) とすると、ニュートン法は次の漸化式の値が収束するまで繰り返す方法です。
平方根を求める場合、導関数は \(f'(x) = 2x\) になるので、漸化式は次のようになります。
参考文献『Ｃ言語による最新アルゴリズム事典』によると、\(\sqrt a\) より大きめの初期値から出発し、置き換え x <- (x + a / x) / 2 を減少が止まるまで繰り返すことで \(\sqrt a\) の正確な値を求めることができるそうです。
リスト xs の中から最小値を求める関数 minimum と最大値を求める関数 maximum を定義してください。
def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A
scala> maximum(List(1, 2, 3, 4, 5, 6, 7, 8)) val res0: Int = 8 scala> minimum(List(1, 2, 3, 4, 5, 6, 7, 8)) val res1: Int = 1 scala> maximum(List(1.1, 2.2, 3.3, 4.4)) val res2: Double = 4.4 scala> minimum(List(1.1, 2.2, 3.3, 4.4)) val res3: Double = 1.1
リスト xs の中から x と等しい要素をひとつ削除する関数 remove と述語 f が真を返す要素をひとつ削除する関数 removeIf を定義してください。
def remove[A](x: A, xs: List[A]): List[A] def removeIf[A](f: A => Boolean, xs: List[A]): List[A]
scala> remove(2, List(1, 2, 3, 1, 2, 3)) val res0: List[Int] = List(1, 3, 1, 2, 3) scala> removeIf((x:Int) => x > 4, List(1, 2, 3, 4, 5, 6)) val res1: List[Int] = List(1, 2, 3, 4, 6)
リスト xs から重複要素を取り除く関数 distinct, リストを集合とみなして、集合の和を求める関数 union, 集合の積を求める関数 intersection, 集合の差を求める関数 difference を定義してください。
def distinct[A](xs: List[A]): List[A] def union[A](xs: List[A], ys: List[A]): List[A] def intersection[A](xs: List[A], ys: List[A]): List[A] def difference[A](xs: List[A], ys: List[A]): List[A]
scala> distinct(List(1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5)) val res0: List[Int] = List(1, 2, 3, 4, 5) scala> union(List(1, 2, 3, 4), List(3, 4, 5, 6)) val res1: List[Int] = List(1, 2, 3, 4, 5, 6) scala> intersection(List(1, 2, 3, 4), List(3, 4, 5, 6)) val res2: List[Int] = List(3, 4) scala> difference(List(1, 2, 3, 4), List(3, 4, 5, 6)) val res3: List[Int] = List(1, 2)
2 つのリスト xs, ys を受け取り、同じ位置にある要素をタプルにまとめ、それをリストに格納して返す関数 zip, zip したリストを元に戻す関数 unzip, 連想リスト xs からキー x とその値を探索する関数 assoc, 連想リスト xs から述語 f が真を返すキーと値を求める関数 assocIf を定義してください。
def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] def unzip[A, B](xs: List[(A, B)]): (List[A], List[B]) def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)] def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)]
scala> val a = zip(List("a", "b", "c", "d"), List(1, 2, 3, 4))
val a: List[(String, Int)] = List((a,1), (b,2), (c,3), (d,4))
scala> unzip(a)
val res0: (List[String], List[Int]) = (List(a, b, c, d),List(1, 2, 3, 4))
scala> assoc("a", a)
val res1: Option[(String, Int)] = Some((a,1))
scala> assoc("d", a)
val res2: Option[(String, Int)] = Some((d,4))
scala> assoc("e", a)
val res3: Option[(String, Int)] = None
scala> assocIf((_: String) > "c", a)
val res4: Option[(String, Int)] = Some((d,4))
選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初は、すべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は、buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。
[9 5 3 7 6 4 8] 3 と 9 を交換する
+ +
3 [5 9 7 6 4 8] 5 と 4 を交換する
+ +
3 4 [9 7 6 5 8] 9 と 5 を交換する
+ +
3 4 5 [7 6 9 8] 7 と 6 を交換する
+ +
3 4 5 6 [7 9 8] 7 と 7 を交換する
+
3 4 5 6 7 [9 8] 9 と 8 を交換してソート終了
+ +
図 : 選択ソート
配列 buff を選択ソートする関数 selectSort を定義してください。
def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit
scala> val a = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) val a: Array[Int] = Array(5, 6, 4, 7, 3, 8, 2, 9, 1, 0) scala> selectSort(a) scala> a val res0: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
リスト xs を選択ソートする関数 selectSortList を定義してください。
def selectSortList[A](xs: Array[A])(implicit f: A => Ordered[A]): Unit
scala> selectSortList(List(5, 6, 4, 7, 2, 3, 8, 9, 1, 0)) val res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) scala> selectSortList(List(5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0)) val res1: List[Int] = List(0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5)
整数の和、二乗の和、三乗の和は、高階関数 sumOf を定義すると簡単です。
リスト : 整数の和、二乗の和、三乗の和
// 二乗
def square(n: BigInt): BigInt = n * n
// 三乗
def cube(n: BigInt): BigInt = n * n * n
// 高階関数
def sumOf(f: BigInt => BigInt)(n: Int, m: Int, a: BigInt = 0): BigInt =
if (n > m) a
else sumOf(f)(n + 1, m, a + f(n))
// 整数の和
def sumOfInt(n: Int, m: Int): BigInt = sumOf(identity)(n, m)
// 二乗の和
def sumOfSquare(n: Int, m: Int): BigInt = sumOf(square)(n, m)
// 三乗の和
def sumOfCube(n: Int, m: Int): BigInt = sumOf(cube)(n, m)
関数 sumOf は n から m までの整数に関数 f を適用して、その結果の総和を求めます。sumOf に恒等関数 identity を渡せば整数の和を、square を渡せば二乗の和を、cube を渡せば三乗の和を求めることができます。
sumOf は末尾再帰でプログラムしていますが、次のように n から m までの数列を生成して、メソッド map と sum で解を求めることもできます。
リスト : 関数 sumOf の別解
def sumOf1(f: BigInt => BigInt)(n: Int, m: Int): BigInt =
(BigInt(n) to m).map(f).sum
ところで、数列の和を求める公式を使うと、プログラムはもっと簡単になります。
リスト : 別解
def sumOfInt1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * (x + 1) / 2
f(m) - f(n - 1)
}
def sumOfSquare1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * (x + 1) * (2 * x + 1) / 6
f(m) - f(n - 1)
}
def sumOfCube1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * x * (x + 1) * (x + 1) / 4
f(m) - f(n - 1)
}
局所関数 f が公式を表しています。あとは f(m) から f(n - 1) を引き算すれば解を求めることができます。
多角数の点の増分を表に示すと、次のようになります。
n 三角数 四角数 五角数
---+-----------------------------------------------------------
1 | 1 1 1
2 | 3 = 1+2 4 = 1+3 5 = 1+4
3 | 6 = 1+2+3 9 = 1+3+5 12 = 1+4+7
4 | 10 = 1+2+3+4 16 = 1+3+5+7 22 = 1+4+7+10
5 | 15 = 1+2+3+4+5 25 = 1+3+5+7+9 35 = 1+4+7+10+13
6 | 21 = 1+2+3+4+5+6 36 = 1+3+5+7+9+11 51 = 1+4+7+10+13+16
・・・・・・ ・・・・・・・ ・・・・・
n | n(n + 1) / 2 n^2 n(3n - 1) / 2
表を見ればお分かりのように、三角数は公差 1、四角数は公差 2、五角数は公差 3、p 角数は公差 p - 2 の等差数列の和になります。初項を a, 公差を d とすると、等差数列の和 \(S_n\) は次式で求めることができます。
a = 1, d = p - 2 を代入して計算すると、多角数 \(P_{p,n}\) は次式で求めることができます。
この式を Scala でプログラムすると、次のようになります。
リスト : 多角数 def polygonalNum(p: Int, n: Int): Int = ((p - 2) * n * n - (p - 4) * n) / 2
簡単な実行例を示します。
scala> for (p <- 3 to 8) {
| for (n <- 1 to 20) {
| print(s"${polygonalNum(p, n)} ")
| }
| println("")
| }
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400
1 5 12 22 35 51 70 92 117 145 176 210 247 287 330 376 425 477 532 590
1 6 15 28 45 66 91 120 153 190 231 276 325 378 435 496 561 630 703 780
1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616 697 783 874 970
1 8 21 40 65 96 133 176 225 280 341 408 481 560 645 736 833 936 1045 1160
p 角数の初項は 1 で、第 2 項は p になります。多角数 - Wikipedia によると、多角数にはいろいろな面白い性質があるようです。
リスト : めのこ平方
def sqrtInt(n: Int, m: Int = 1): Int =
if (n < m) m / 2 else sqrtInt(n - m, m + 2)
アルゴリズムをそのままプログラムしただけなので、とくに難しいところは無いと思います。この方法はとても簡単ですが、数が大きくなると時間がかかるようになります。そこで、整数を 2 桁ずつ分けて計算していくことにします。次の図を見てください。
整数 6789 を 67 と 89 に分ける 1 + 3 + ... + 15 = 82 < 67 両辺を 100 倍すると 802 < 6700 < 6789 802 = 1 + 3 + ... + 159 (= 2 * 80 - 1) 161 + 163 < (6789 - 6400 = 389) < 161 + 163 + 165
整数 6789 を 67 と 89 に分けます。最初に 67 の平方根を求めます。この場合は 8 になり、82 < 67 を満たします。次に、この式を 100 倍します。すると、802 < 6700 になり、6700 に 89 を足した 6789 も 802 より大きくなります。802 は 1 から 159 までの奇数の総和であることはすぐにわかるので、6789 - 6400 = 389 から奇数 161, 163, ... を順番に引き算していけば 6789 の平方根を求めることができます。
プログラムは次のようになります。
リスト : めのこ平方 (改良版)
def sqrtInt1(n: Int): Int =
if (n < 100)
sqrtInt(n)
else {
val m = 10 * sqrtInt1(n / 100)
sqrtInt(n - m * m, 2 * m + 1)
}
sqrtInt1 は n の平方根の整数部分を求めます。n が 100 未満の場合は sqrtInt で平方根を求めます。これが再帰呼び出しの停止条件になります。n が 100 以上の場合は、n の下位 2 桁を取り除いた値 (n / 100) の平方根を sqrtInt1 で求め、その値を 10 倍して変数 m にセットします。そして、sqrInt で n - m * m から奇数 2 * m + 1, 2 * m + 3 ... を順番に引き算していって n の平方根を求めます。
リスト : 平方根を求める
def sqrt(n: Double): Double = {
def init(s: Double, x: Double): Double =
if (s >= x) s
else init(s * 2, x / 2)
def iter(p: Double): Double = {
val q = (p + n / p) / 2
if (q >= p) p else iter(q)
}
if (n < 0) throw new Exception("sqrt: domain error")
else if (n == 0) 0
else iter(if (n > 1) init(1, n) else 1)
}
局所関数 init は \(\sqrt x\) よりも大きめの初期値を求めます。たとえば、\(\sqrt {123456}\) を求める場合、初期値の計算は次のようになります。
s x ------------------- 1.0 123456.0 2.0 61728.0 4.0 30864.0 8.0 15432.0 16.0 7716.0 32.0 3858.0 64.0 1929.0 128.0 964.5 256.0 482.25 512.0 241.125 √123456 = 351.363060095964
s を 2 倍、x を 1 / 2 していき、s >= x となったときの s が初期値 (512) となります。4, 16, 64, 256, ... 22n の平方根はこれだけで求めることができます。
あとは漸化式を計算して変数 q にセットし、q がひとつ前の値 p 以上になったら p を返すだけです。\(\sqrt {123456}\) を求めたときの p と q の値を示します。
p q -------------------------------------- 512.0 376.5625 376.5625 352.20622925311204 352.20622925311204 351.3640693544162 351.3640693544162 351.3630600974135 351.3630600974135 351.363060095964 351.363060095964 351.363060095964 √123456 = 351.363060095964
6 回の繰り返しで \(\sqrt {123456}\) を求めることができます。
リスト : 最小値と最大値
def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
def min(xs: List[A], a: A): A =
xs match {
case Nil => a
case y::ys => if (y < a) min(ys, y) else min(ys, a)
}
//
min(xs.tail, xs.head)
}
def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
def max(xs: List[A], a: A): A =
xs match {
case Nil => a
case y::ys => if (y > a) max(ys, y) else max(ys, a)
}
//
max(xs.tail, xs.head)
}
// 別解
def minimum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x < a) x else a)
def maximum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x > a) x else a)
実際の処理は局所関数 max, min で行います。どちらの関数も再帰呼び出しで最大値 (最小値) を求めます。第 2 引数 a に最大値 (最小値) を格納します。最初は先頭要素 x.head が初期値になります。あとは、残りのリスト xs.tail の要素と a を比較して、a よりも大きい (小さい) 要素 y が見つかれば、a の値を y に置き換えます。別解はメソッド foldLeft で書き直したものです。
リスト : 要素の削除
def remove[A](x: A, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (x == y) ys else y :: remove(x, ys)
}
def removeIf[A](f: A => Boolean, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (f(y)) ys else y :: removeIf(f, ys)
}
remove と removeIf は最初に見つけた要素だけを削除します。remove の場合、x と要素 y が等しければ、残りのリスト ys を返します。removeIf の場合は、f(y) が真を返したら残りのリスト ys を返します。これで y だけを削除することができます。
リスト : 集合演算
def distinct[A](xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (ys contains y) distinct(ys) else y::distinct(ys)
}
def union[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => ys
case (x::xs1) => if (ys contains x) union(xs1, ys) else x::union(xs1, ys)
}
def intersection[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => Nil
case (x::xs1) => if (ys contains x) x::intersection(xs1, ys) else intersection(xs1, ys)
}
def difference[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => Nil
case (x::xs1) => if (ys contains x) difference(xs1, ys) else x::difference(xs1, ys)
}
// 別解
def distinct1[A](xs: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (a contains x) a else x::a)
def union1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(ys)((a: List[A], x: A) => if (a contains x) a else x::a)
def intersection1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) x::a else a)
def difference1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) a else x::a)
distinct はリストを分解して、先頭要素 y が残りのリスト ys に含まれていなければ、distinct(ys) の返り値に y を追加します。そうでなければ y を追加しません。union は xs が空リストになったら ys を返します。次に、リスト xs を x::xs1 に分解して、x が ys に含まれていなければ、union(xs1, ys) の返り値に x を追加します。そうでなければ x を追加しません。
intersection は xs が空リストになったら Nil を返します。次に、xs を x::xs1 に分解して、x が ys に含まれていれば、intersection(xs1, ys) の返り値に x を追加します。そうでなければ x を追加しません。difference は intersection とは逆に、x が ys に含まれていなければ、difference(xs1, ys) の返り値に x を追加します。
別解はメソッド foldLeft で書き直したものです。簡単な実行例を示します。
scala> distinct1(List(1,2,3,1,2,3,4,1,2,3,4,5)) val res5: List[Int] = List(5, 4, 3, 2, 1) scala> union1(List(1,2,3,4), List(3,4,5,6)) val res6: List[Int] = List(2, 1, 3, 4, 5, 6) scala> intersection1(List(1,2,3,4), List(3,4,5,6)) val res7: List[Int] = List(4, 3) scala> difference1(List(1,2,3,4), List(3,4,5,6)) val res8: List[Int] = List(2, 1)
リスト : 連想リスト
def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
(xs, ys) match {
case (Nil, _) | (_, Nil) => Nil
case (x::xs, y::ys) => (x, y)::zip(xs, ys)
}
def unzip[A, B](xs: List[(A, B)]): (List[A], List[B]) =
xs match {
case Nil => (Nil, Nil)
case (x, y)::zs => {
val (xs1, ys1) = unzip(zs)
(x::xs1, y::ys1)
}
}
def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)] =
xs match {
case Nil => None
case (k, v)::ys => if (k == x) Some((k, v)) else assoc(x, ys)
}
def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)] =
xs match {
case Nil => None
case (k, v)::ys => if (f(k)) Some((k, v)) else assocIf(f, ys)
}
zip はリストの要素 x, y を取り出してタプルにまとめ、それを返り値のリストに追加していくだけです。どちらかの引数が空リストになったときが再帰呼び出しの停止条件です。unzip は引数が空リストの場合、2 つの空リストを格納したタプルを返します。これが再帰の停止条件になります。次に、unzip を再帰呼び出しして、変数 xs1, ys1 に返り値のリストを受け取ります。あとは、xs1 に x を、ys1 に y を追加してタプルに格納して返すだけです。
assoc, assocIf は引数のリストが空リストの場合は None を返します。そうでなければ、aasoc はタプルの先頭要素 k が x と等しいかチェックします。等しい場合は Some((k, v)) を返し、そうでなければ assoc を再帰呼び出しして次の要素をチェックします。assocIf は f(k) が真の場合に Some((k, v)) を返し、そうでなければ assocIf を再帰呼び出しします。
リスト : 選択ソート
def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
for (i <- 0 until buff.size) {
var min = i
for (j <- i + 1 until buff.size) {
if (buff(j) < buff(min)) min = j
}
var tmp = buff(i)
buff(i) = buff(min)
buff(min) = tmp
}
}
最初のループで変数 i の値は 0 から buff.size - 1 まで動きます。2 番目のループで buff(i) から buff(buff.size - 1) までの中から最小値を探します。最小値の位置は変数 min に格納します。初期値は i になります。2 番目のループを終了したら、buff(i) と buff(min) の値を交換します。
リスト : 選択ソート (リスト版)
def selectSortList[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
def sort(xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => ys
case z::zs => {
val x = maximum(xs)
sort(remove(x, xs), x::ys)
}
}
sort(xs, Nil)
}
実際の処理は局所関数 sort で行います。引数 xs の中から最大値 x を maximum で求め、それを引数 ys のリストに追加します。このとき、remove で xs から x を削除します。xs が空リストになったらソートが完了したので ys を返します。
選択ソートの実行時間はデータの個数の 2 乗に比例する遅いソートです。
//
// yasp01.scala : Yet Another Scala Problems (1)
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
import scala.math.Ordered.orderingToOrdered
object yasp01 {
// Q01
def square(n: BigInt): BigInt = n * n
def cube(n: BigInt): BigInt = n * n * n
def sumOf(f: BigInt => BigInt)(n: Int, m: Int, a: BigInt = 0): BigInt =
if (n > m) a
else sumOf(f)(n + 1, m, a + f(n))
def sumOf1(f: BigInt => BigInt)(n: Int, m: Int): BigInt =
(BigInt(n) to m).map(f).sum
def sumOfInt(n: Int, m: Int): BigInt = sumOf(identity)(n, m)
def sumOfSquare(n: Int, m: Int): BigInt = sumOf(square)(n, m)
def sumOfCube(n: Int, m: Int): BigInt = sumOf(cube)(n, m)
def sumOfInt1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * (x + 1) / 2
f(m) - f(n - 1)
}
// 別解
def sumOfSquare1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * (x + 1) * (2 * x + 1) / 6
f(m) - f(n - 1)
}
def sumOfCube1(n: Int, m: Int): BigInt = {
def f(x: BigInt): BigInt = x * x * (x + 1) * (x + 1) / 4
f(m) - f(n - 1)
}
// Q02
def sqrtInt(n: Int, m: Int = 1): Int =
if (n < m) m / 2 else sqrtInt(n - m, m + 2)
def sqrtInt1(n: Int): Int =
if (n < 100)
sqrtInt(n)
else {
val m = 10 * sqrtInt1(n / 100)
sqrtInt(n - m * m, 2 * m + 1)
}
// Q03
def sqrt(n: Double): Double = {
def init(s: Double, x: Double): Double =
if (s >= x) s
else init(s * 2, x / 2)
def iter(p: Double): Double = {
val q = (p + n / p) / 2
if (q >= p) p else iter(q)
}
if (n < 0) throw new Exception("sqrt: domain error")
else if (n == 0) 0
else iter(if (n > 1) init(1, n) else 1)
}
// Q04
def polygonalNum(p: Int, n: Int): Int =
((p - 2) * n * n - (p - 4) * n) / 2
// Q05
def minimum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
def min(xs: List[A], a: A): A =
xs match {
case Nil => a
case y::ys => if (y < a) min(ys, y) else min(ys, a)
}
//
min(xs.tail, xs.head)
}
def maximum[A](xs: List[A])(implicit f: A => Ordered[A]): A = {
def max(xs: List[A], a: A): A =
xs match {
case Nil => a
case y::ys => if (y > a) max(ys, y) else max(ys, a)
}
//
max(xs.tail, xs.head)
}
// 別解
def minimum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x < a) x else a)
def maximum1[A](xs: List[A])(implicit f: A => Ordered[A]): A =
xs.tail.foldLeft(xs.head)((a: A, x: A) => if (x > a) x else a)
// Q06
def remove[A](x: A, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (x == y) ys else y :: remove(x, ys)
}
def removeIf[A](f: A => Boolean, xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (f(y)) ys else y :: removeIf(f, ys)
}
// Q07
def distinct[A](xs: List[A]): List[A] =
xs match {
case Nil => Nil
case y::ys => if (ys contains y) distinct(ys) else y::distinct(ys)
}
def union[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => ys
case (x::xs1) => if (ys contains x) union(xs1, ys) else x::union(xs1, ys)
}
def intersection[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => Nil
case (x::xs1) => if (ys contains x) x::intersection(xs1, ys) else intersection(xs1, ys)
}
def difference[A](xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => Nil
case (x::xs1) => if (ys contains x) difference(xs1, ys) else x::difference(xs1, ys)
}
// 別解
def distinct1[A](xs: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (a contains x) a else x::a)
def union1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(ys)((a: List[A], x: A) => if (a contains x) a else x::a)
def intersection1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) x::a else a)
def difference1[A](xs: List[A], ys: List[A]): List[A] =
xs.foldLeft(Nil:List[A])((a: List[A], x: A) => if (ys contains x) a else x::a)
// Q08
def zip[A, B](xs: List[A], ys: List[B]): List[(A, B)] =
(xs, ys) match {
case (Nil, _) | (_, Nil) => Nil
case (x::xs, y::ys) => (x, y)::zip(xs, ys)
}
def unzip[A, B](xs: List[(A, B)]): (List[A], List[B]) =
xs match {
case Nil => (Nil, Nil)
case (x, y)::zs => {
val (xs1, ys1) = unzip(zs)
(x::xs1, y::ys1)
}
}
def assoc[A, B](x: A, xs: List[(A, B)]): Option[(A, B)] =
xs match {
case Nil => None
case (k, v)::ys => if (k == x) Some((k, v)) else assoc(x, ys)
}
def assocIf[A, B](f: A => Boolean, xs: List[(A, B)]): Option[(A, B)] =
xs match {
case Nil => None
case (k, v)::ys => if (f(k)) Some((k, v)) else assocIf(f, ys)
}
// Q09
def selectSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
for (i <- 0 until buff.size) {
var min = i
for (j <- i + 1 until buff.size) {
if (buff(j) < buff(min)) min = j
}
var tmp = buff(i)
buff(i) = buff(min)
buff(min) = tmp
}
}
// Q10
def selectSortList[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] = {
def sort(xs: List[A], ys: List[A]): List[A] =
xs match {
case Nil => ys
case z::zs => {
val x = maximum(xs)
sort(remove(x, xs), x::ys)
}
}
sort(xs, Nil)
}
}