Yet Another Scala Problems

●問題11

自然数 n (Long) を素因数分解する関数 factorization を定義してください。返り値は List[(Long, Long)] で、タプル (p, q) は \(p^q\) を表します。

def factorization(n: Long): List[(Long, Long)]

scala> factorization(24)
val res0: List[(Long, Long)] = List((2,3), (3,1))

scala> factorization(12345678)
val res1: List[(Long, Long)] = List((2,1), (3,2), (47,1), (14593,1))

scala> factorization(123456789)
val res2: List[(Long, Long)] = List((3,2), (3607,1), (3803,1))

scala> factorization(1234567890)
val res3: List[(Long, Long)] = List((2,1), (3,2), (5,1), (3607,1), (3803,1))

scala> factorization(1111111111)
val res4: List[(Long, Long)] = List((11,1), (41,1), (271,1), (9091,1))

●問題12

自然数 n の約数の個数を求める関数 divisorNum を定義してください。

def divisorNum(n: Long): Long

scala> divisorNum(24)
val res0: Long = 8

scala> divisorNum(12345678)
val res1: Long = 24

scala> divisorNum(123456789)
val res2: Long = 12

scala> divisorNum(1234567890)
val res3: Long = 48

scala> divisorNum(1111111111)
val res4: Long = 16

●問題13

自然数 n の約数の合計値を求める関数 divisorSum を定義してください。

def divisorSum(n: Long): Long

scala> divisorSum(24)
val res0: Long = 60

scala> divisorSum(12345678)
val res1: Long = 27319968

scala> divisorSum(123456789)
val res2: Long = 178422816

scala> divisorSum(1234567890)
val res3: Long = 3211610688

scala> divisorSum(1111111111)
val res4: Long = 1246404096

●問題14

自然数 n の約数をリストに格納して返す関数 divisor を定義してください。

def divisor(n: Long) List[Long]

scala> divisor(24)
val res0: List[Long] = List(1, 2, 3, 4, 6, 8, 12, 24)

scala> divisor(12345678)
val res1: List[Long] = List(1, 2, 3, 6, 9, 18, 47, 94, 141, 282, 423, 846, 14593,
 29186, 43779, 87558, 131337, 262674, 685871, 1371742, 2057613, 4115226, 6172839,
 12345678)

scala> divisor(123456789)
val res2: List[Long] = List(1, 3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421,
 41152263, 123456789)

scala> divisor(1234567890)
val res3: List[Long] = List(1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90, 3607, 3803, 
 7214, 7606, 10821, 11409, 18035, 19015, 21642, 22818, 32463, 34227, 36070,
 38030, 54105, 57045, 64926, 68454, 108210, 114090, 162315, 171135, 324630,
 342270, 13717421, 27434842, 41152263, 68587105, 82304526, 123456789, 137174210,
 205761315, 246913578, 411522630, 617283945, 1234567890)

scala> divisor(1111111111)
val res4: List[Long] = List(1, 11, 41, 271, 451, 2981, 9091, 11111, 100001, 122221,
372731, 2463661, 4100041, 27100271, 101010101, 1111111111)

●問題15

完全数 - Wikipedia によると、『完全数（かんぜんすう，perfect number）とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。』とのことです。自然数 n 以下の完全数を求める関数 perfectNumber を定義してください。

def perfectNumber(n: Long): Unit

scala> perfectNumber(10000)
6
28
496
8128

●問題16

友愛数 - Wikipedia によると、『友愛数（ゆうあいすう）とは、異なる2つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう。』とのことです。自然数 n 以下の友愛数を求める関数 yuuaiNumber を定義してください。

def yuuaiNumber(n: Long): Unit

scala> yuuaiNumber(100000)
(220,284)
(1184,1210)
(2620,2924)
(5020,5564)
(6232,6368)
(10744,10856)
(12285,14595)
(17296,18416)
(63020,76084)
(66928,66992)
(67095,71145)
(69615,87633)
(79750,88730)

●問題17

リスト xs を n 番目で二分割する関数 splitAt, 引数の述語 f の真偽で二分割する関数 partition, 述語 f が偽を返すところでリストを二分割する関数 span を定義してください。

def splitAt[A](xs: List[A], n: Int): (List[A], List[A])
def partition[A](f: A => Boolean, xs: List[A]): (List[A], List[A])
def span[A](f: A => Boolean, xs: List[A]): (List[A], List[A])

scala> splitAt(List(1, 2, 3, 4, 5, 6, 7, 8), 0)
val res0: (List[Int], List[Int]) = (List(),List(1, 2, 3, 4, 5, 6, 7, 8))

scala> splitAt(List(1, 2, 3, 4, 5, 6, 7, 8), 4)
val res1: (List[Int], List[Int]) = (List(1, 2, 3, 4),List(5, 6, 7, 8))

scala> splitAt(List(1, 2, 3, 4, 5, 6, 7, 8), 8)
val res2: (List[Int], List[Int]) = (List(1, 2, 3, 4, 5, 6, 7, 8),List())

scala> partition((x: Int)=> x % 2 == 0, List(1, 2, 3, 4, 5, 6, 7, 8))
val res3: (List[Int], List[Int]) = (List(2, 4, 6, 8),List(1, 3, 5, 7))

scala> partition((x: Int)=> x % 3 == 0, List(1, 2, 3, 4, 5, 6, 7, 8))
val res4: (List[Int], List[Int]) = (List(3, 6),List(1, 2, 4, 5, 7, 8))

scala> partition((x: Int)=> x % 10 == 0, List(1, 2, 3, 4, 5, 6, 7, 8))
val res5: (List[Int], List[Int]) = (List(),List(1, 2, 3, 4, 5, 6, 7, 8))

scala> span((x: Int) => x < 5, List(1, 2, 3, 4, 5, 6, 7, 8))
val res6: (List[Int], List[Int]) = (List(1, 2, 3, 4),List(5, 6, 7, 8))

scala> span((x: Int) => x < 0, List(1, 2, 3, 4, 5, 6, 7, 8))
val res7: (List[Int], List[Int]) = (List(),List(1, 2, 3, 4, 5, 6, 7, 8))

scala> span((x: Int) => x < 10, List(1, 2, 3, 4, 5, 6, 7, 8))
val res8: (List[Int], List[Int]) = (List(1, 2, 3, 4, 5, 6, 7, 8),List())

●問題18

分数を小数に直すことを考えます。1 / 2, 1 / 5, 1 / 8, 1 / 10 などは　0.5, 0.2, 0.125, 0.1 のように途中で割り切れて、有限な桁で表すことができます。これを「有限小数」といいます。ところが、1 / 3, 1 / 6, 1 / 7 は、次のように有限な桁では表すことができません。

\(\begin{array}{l} \dfrac{1}{3} = 0.333333\ldots \\ \dfrac{1}{6} = 0.166666\ldots \\ \dfrac{1}{7} = 0.142857142857142857\ldots \end{array}\)

1 / 3 は 3 を無限に繰り返し、1 / 6 は 0.1 のあと 6 を無限に繰り返し、1 / 7 は数列 142857 を無限に繰り返します。このような少数を「循環小数 (repeating decimal) 」といい、繰り返される数字の列を「循環節」といいます。分数を小数に直すと、有限小数か循環小数のどちらかになります。

循環小数は次のように循環節の始めと終わりを点で示します。

\(\begin{array}{l} \dfrac{1}{3} = 0.\dot{3} \\ \dfrac{1}{6} = 0.1\dot{6} \\ \dfrac{1}{7} = 0.\dot{1}4285\dot{7} \end{array}\)

このほかに、循環節に下線を引いたり、カッコで囲む表記法もあります。

それでは問題です。分数 (p / q) を循環小数に変換する関数 repdec を定義してください。

def repdec(p: Long, q: Long): (List[Long], List[Long])

返り値は 2 つのリストで、先頭のリストが冒頭の小数部分を、次のリストが循環節の部分を表します。途中で割り切れる場合は循環節を (0) とします。

scala> repdec(1, 2)
val res0: (List[Long], List[Long]) = (List(0, 5),List(0))

scala> repdec(1, 3)
val res1: (List[Long], List[Long]) = (List(0),List(3))

scala> repdec(1, 7)
val res2: (List[Long], List[Long]) = (List(0),List(1, 4, 2, 8, 5, 7))

scala> repdec(1, 9)
val res3: (List[Long], List[Long]) = (List(0),List(1))

scala> repdec(355, 113)
val res4: (List[Long], List[Long]) = (List(3),List(1, 4, 1, 5, 9, 2, 9, 2, 0, 3, 5,
 3, 9, 8, 2, 3, 0, 0, 8, 8, 4, 9, 5, 5, 7, 5, 2, 2, 1, 2, 3, 8, 9, 3, 8, 0, 5, 3,
 0, 9, 7, 3, 4, 5, 1, 3, 2, 7, 4, 3, 3, 6, 2, 8, 3, 1, 8, 5, 8, 4, 0, 7, 0, 7, 9,
 6, 4, 6, 0, 1, 7, 6, 9, 9, 1, 1, 5, 0, 4, 4, 2, 4, 7, 7, 8, 7, 6, 1, 0, 6, 1, 9,
 4, 6, 9, 0, 2, 6, 5, 4, 8, 6, 7, 2, 5, 6, 6, 3, 7, 1, 6, 8))

●問題19

循環小数から分数を求める関数 fromRepdec を定義してください。

def fromRepdec(xs: List[Long], ys: List[Long]): (Long, Long)

引数のリスト xs が冒頭の小数部分を、リスト ys が循環節の部分を表します。

scala> val (a, b) = repdec(1, 2)
val a: List[Long] = List(0, 5)
val b: List[Long] = List(0)

scala> fromRepdec(a, b)
val res0: (Long, Long) = (1,2)

scala> val (a, b) = repdec(1, 3)
val a: List[Long] = List(0)
val b: List[Long] = List(3)

scala> fromRepdec(a, b)
val res1: (Long, Long) = (1,3)

scala> val (a, b) = repdec(1, 7)
val a: List[Long] = List(0)
val b: List[Long] = List(1, 4, 2, 8, 5, 7)

scala> fromRepdec(a, b)
val res2: (Long, Long) = (1,7)

scala> val (a, b) = repdec(1, 11)
val a: List[Long] = List(0)
val b: List[Long] = List(0, 9)

scala> fromRepdec(a, b)
val res3: (Long, Long) = (1,11)

scala> val (a, b) = repdec(355, 113)
val a: List[Long] = List(3)
val b: List[Long] = List(1, 4, 1, 5, 9, 2, 9, 2, 0, 3, 5, 3, 9, 8, 2, 3, 0, 0, 8, 8,
 4, 9, 5, 5, 7, 5, 2, 2, 1, 2, 3, 8, 9, 3, 8, 0, 5, 3, 0, 9, 7, 3, 4, 5, 1, 3, 2
, 7, 4, 3, 3, 6, 2, 8, 3, 1, 8, 5, 8, 4, 0, 7, 0, 7, 9, 6, 4, 6, 0, 1, 7, 6, 9,
9, 1, 1, 5, 0, 4, 4, 2, 4, 7, 7, 8, 7, 6, 1, 0, 6, 1, 9, 4, 6, 9, 0, 2, 6, 5, 4,
 8, 6, 7, 2, 5, 6, 6, 3, 7, 1, 6, 8)

scala> fromRepdec(a, b)
val res4: (Long, Long) = (355,113)

●問題20

 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   いちばん小さいデータが決定する
 +               残りのデータに対して同様な操作を行う

        図 : バブルソート

バブルソート (buble sort) は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がります。これをデータ数だけ繰り返せばソートが完了します。

配列 buff をバブルソートする関数 bubleSort を定義してください。

def bubleSort[A <% Ordered[A]](buff: List[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> bubleSort(a)

scala> a
val res0: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

●解答11

リスト : 素因数分解

  def factorization(n: Long): List[(Long, Long)] = {
    // m で割り切れる回数を求める
    def factorSub(n: Long, m: Long, c: Long): (Long, Long) =
      if (n % m != 0) (c, n) else factorSub(n / m, m, c + 1)

    // 奇数列の生成
    def iter(i: Long, n: Long, a: List[(Long, Long)]): List[(Long, Long)] =
      if (n == 1) a.reverse
      else if (n < i * i) ((n, 1L)::a).reverse
      else {
        val (c, m) = factorSub(n, i, 0)
        if (c == 0) iter(i + 2, n, a)
        else iter(i + 2, m, (i, c)::a)
      }

    //
    val (c, m) = factorSub(n, 2, 0)
    if (c > 0) iter(3, m, (2L, c)::Nil) else iter(3, n, Nil)
  }

素因数分解は素数 2, 3, 5, ... で順番に割り算していけばいいのですが、いちいち素数を求めるのは大変なので、2 と 3 以上の奇数列で割り算していきます。局所関数 factorSub は n を m で割り算します。このとき、m で割り切れる回数を求めます。factorSub は m で割った回数と商をタプルに格納して返します。

局所関数 iter は再帰呼び出しで奇数列を生成します。引数 a は結果を格納するリストです。n が 1 になる、または √n < i になったら素因数分解を終了して結果を返します。そうでなければ、factorSub を呼び出して n を i で割り算します。奇数列には素数ではないものがありますが、その前に小さな素数で素因数分解されているので、n がその値で割り切れることはありません。

あとは、factorSub を呼び出して n を 2 で割り算し、それから iter を呼び出します。なお、これはとても単純なアルゴリズムなので、大きな整数の素因数分解には適していません。巨大な合成数の素因数分解はとても難しい問題です。興味のある方は素因数分解について調べてみてください。

●解答12

n の素因数分解ができると、約数の個数を求めるのは簡単です。\(n = p^a \times q^b \times r^c\) とすると、約数の個数は \((a + 1) \times (b + 1) \times (c + 1)\) になります。たとえば、12 は \(2^2 \times 3^1\) になるので、約数の個数は 3 * 2 = 6 になります。実際、12 の約数は 1, 2, 3, 4, 6, 12 の 6 個です。

プログラムは次のようになります。

リスト : 約数の個数

  def divisorNum(n: Long): Long = {
    var a = 1L
    for ((_, q) <- factorization(n)) a *= q + 1
    a
  }

  // 別解
  def divisorNum1(n: Long): Long =
    factorization(n).foldLeft(1L)((a: Long, x: (Long, Long)) => a * (x._2 + 1))

divisorNum は for ループでスライスの要素を順番に取り出し、q + 1 を a に掛け算していくだけです。別解はメソッド foldLeft で書き直したものです。

●解答13

n の素因数分解ができると、約数の合計値を求めるのは簡単です。n の素因数分解が \(p^a\) だった場合、その約数の合計値は次の式で求めることができます。

\( \sigma(p, a) = p^a + p^{a-1} + \cdots + p^2 + p + 1 \)

たとえば、8 の素因数分解は \(2^3\) になり、素数の合計値は \(8 + 4 + 2 + 1 = 15\) になります。

\(p^a\) の約数の合計値を \(\sigma(p, a)\) で表すことにします。\(n = p^a \times q^b \times r^c\) の場合、n の約数の合計値は \(\sigma(p, a) \times \sigma(q, b) \times \sigma(r, c)\) になります。たとえば、12 は \(2^2 \times 3\) に素因数分解できますが、その合計値は (4 + 2 + 1) * (3 + 1) = 28 となります。12 の約数は 1, 2, 3, 4, 6, 12 なので、その合計値は確かに 28 になります。

プログラムは次のようになります。

リスト : 約数の合計値

  // 累乗
  def pow(x: Long, y: Long): Long =
    if (y == 0)
      1
    else {
      val z = pow(x, y / 2)
      if (y % 2 == 0) z * z else z * z * x
    }

  // σ(p, n) を求める
  def sigma(p: Long, n: Long): List[Long] =
    (0L to n).toList.map(pow(p, _))

  def divisorSum(n: Long): Long = {
    var a = 1L
    for ((p, q) <- factorization(n)) a *= sigma(p, q).sum
    a
  }

  // 別解
  def divisorSum1(n: Long): Long =
    factorization(n).foldLeft(1L)((a: Long, x: (Long, Long)) => a * sigma(x._1, x._2).sum)

関数 sigma は \(\sigma(p, n)\) を計算します。あとは for ループで sigma の合計値を累積変数 a に掛け算していくだけです。別解は foldLeft で書き直したものです。

●解答14

p が素数の場合、p^a の約数は次のように簡単に求めることができます。

\( p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1 \)

n の素因数分解が p^a * q^b だったとすると、その約数は次のようになります。

\(\begin{array}{l} (p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1) \times q^b, \\ (p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1) \times q^{b-1}, \\ \quad \quad \cdots \cdots \\ (p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1) \times q^2, \\ (p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1) \times q, \\ (p^a, \ p^{a-1}, \ \ldots \ p^2, \ p, 1) \times 1, \\ \end{array}\)

たとえば、12 の約数は \(2^2\) = (1, 2, 4) と 3 = (1, 3) から、(1, 2, 4) * 1 と (1, 2, 4) * 3 のすべての要素 (1, 2, 4, 3, 6, 12) になります。

プログラムは次のようになります。

リスト : 約数をすべて求める

  // 直積集合を求め、2 つの要素を乗算する
  def product(xs: List[Long], ys: List[Long]): List[Long] =
    for (x <- xs; y <- ys) yield x * y

  def divisor(n: Long): List[Long] = {
    val (p1, x1)::xs = factorization(n)
    xs.foldLeft(sigma(p1, x1))((a: List[Long], x: (Long, Long)) => product(sigma(x._1, x._2), a)).sorted
  }

関数 product は 2 つのリスト xs、ys の直積集合を求め、その要素を掛け合わせたものをリストに格納して返します。divisor は、最初に factorization で n を素因数分解して、先頭の要素 (p1, x1) と残りのリスト xs に分解します。あとは foldLeft で xs から要素を順番に取り出し、sigma でリストに変換して、それを product で累積変数 a のリストと掛け合わせていくだけです。

●解答15

リスト : 完全数

  def perfectNumber(n: Long): Unit = {
    (2L to n).foreach(x => if (divisorSum(x) - x == x) println(x))
  }

完全数を求める perfectNumber は簡単です。x の約数の合計値を divisorSum で求め、その値から x を引いた値が x と等しければ完全数です。println で x を表示します。今回はメソッド foreach を使いましたが、for 式でも簡単にプログラムすることができます。

●解答16

リスト : 友愛数

  def yuuaiNumber(n: Long): Unit = {
    (2L to n).foreach(x => {
        val m = divisorSum(x) - x
        if (x < m && x == divisorSum(m) - m) println((x, m))
      })
  }

友愛数を求める yuuaiNumber も簡単です。divisorSum で x の約数の合計値を求め、その値から x を引いた値を変数 m にセットします。m の約数の合計値から m を引いた値が x と等しければ、x と m は友愛数です。println で x と m を表示します。同じ組を表示しないようにするため、x < m を条件に入れています。

●解答17

リスト : リストの分割

  def splitAt[A](xs: List[A], n: Int): (List[A], List[A]) =
    (xs, n) match {
      case (Nil, _) | (_, 0) => (Nil, xs)
      case (x::xs1, _) => {
        val (a, b) = splitAt(xs1, n - 1)
        (x::a, b)
      }
    }

  def partition[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) = 
    xs match {
      case Nil => (Nil, Nil)
      case x::xs1 => {
        val (a, b) = partition(f, xs1)
        if (f(x)) (x::a, b) else (a, x::b)
      }
    }

  def span[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) =
    xs match {
      case Nil => (Nil, Nil)
      case (ys @ x::xs1) if (!f(x)) => (Nil, ys)
      case x::xs1 => {
        val (a, b) = span(f, xs1)
        (x::a, b)
      }
    }

  // 別解
  def splitAt1[A](xs: List[A], n: Int): (List[A], List[A]) =
    (xs.take(n), xs.drop(n))

  def partition1[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) =
    (for (x <- xs if (f(x))) yield x, for (x <- xs if (!f(x))) yield x)

  def span1[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) = {
    val a = xs.takeWhile(f)
    (a, xs.drop(a.length))
  }

splitAt は再帰呼び出しでリストを分割します。xs が空リストまたは n が 0 になったならば、(Nil, xs) を返します。そうでなければ、xs を x :: xs1 に分割して、splitAt を再帰呼び出しします。そして、a の先頭に x を追加して、b といっしょにタプルに格納して返します。

splitAt の別解は take と drop を使っています。take で先頭から n 個の要素を取り出し、drop で先頭から n 個の要素を取り除きます。そして、2 つのリストをタプルに格納して返します。

partition も再帰呼び出しでリストを分割します。xs が空リストになったならば (Nil, Nil) を返します。そうでなければ、xs を x :: xs1 に分割して、partition を再帰呼び出しします。そして、f(x) が真ならば x を a に追加し、偽を返すならば b に追加します。別解は for 内包表記を使ったものです。リストを 2 回走査することに注意してください。

span も再帰呼び出しでリストを分割します。xs が空リストになったならば (Nil, Nil) を返します。そうでなければ xs を (ys @ x :: xs1) に分割して、f(x) が偽ならば (Nil, ys) を返します。f(x) が真の場合は span を再帰呼び出しして、a に x を追加して返します。別解は takeWhile でリストを取り出し、その長さだけ drop で要素を取り除きます。

●解答18

分数を循環小数に直すのは簡単です。筆算と同じように計算していくだけです。次の図を見てください。

     0 1 4 2 8 5 7
   ----------------
 7 ) 1
     0
    ----- 
     1 0  <-- 余り 1
       7
    ------- 
       3 0
       2 8
      -------
         2 0
         1 4
        -------
           6 0
           5 6
          -------
             4 0
             3 5
            -------
               5 0
               4 9
              -----
                 1  <-- 余り 1

7 で割った余り 1 が 2 回現れていますね。これから先は同じ数列を繰り返すことがわかります。7 の剰余は 0 から 6 まであり、剰余が 0 の場合は割り切れるので循環小数にはなりません。現れる余りの数が限られているので、割り切れなければ循環することになるわけです。また、このことから循環節の長さは分母の値よりも小さいことがわかります。

リスト : 循環小数を求める

  def repdec(m: Long, n: Long): (List[Long], List[Long]) = {
    def iter(m: Long, xs: List[Long], ys: List[Long]): (List[Long], List[Long]) = {
      val p = m / n
      val q = m % n
      if (q == 0) ((p::ys).reverse, List(0))
      else if (xs contains q) {
        val a = xs.reverse.takeWhile(_ != q)
        (p::ys).reverse.splitAt(a.length + 1)
      } else iter(q * 10, q::xs, p::ys)
    }
    //
    iter(m, Nil, Nil)
  }

関数 repdec(m, n) は m / n を循環小数に変換します。返り値は 2 つのリストを格納したタプルで、先頭のリストが冒頭の小数部分を、次のリストが循環節の部分を表します。途中で割り切れる場合は循環節を List(0) とします。これ以降、冒頭の小数部分を有限小数部分と記述することにします。

実際の処理は局所関数 iter で行います。第 2 引数 xs が余りを格納するリスト、第 3 引数 ys が商を格納するリストです。最初に m と n の商と余りを計算して、変数 p と q にセットします。q が 0 ならば割り切れたので有限小数です。p::ys を reverse で反転し、それと List(0) をタプルに格納して返します。

割り切れない場合、余り q が xs にあるか contains でチェックします。同じ値が無ければ iter を再帰呼び出しします。同じ値を見つけた場合、reverse で xs を反転し、takeWhile で先頭から q の手前までの要素を取り出し、変数 a にセットします。有限小数部分は a の長さ +1 までなので、メソッド splitAt で商のリスト (p::ys).reverse を分割して返します。

●解答19

循環小数を分数に直すことも簡単にできます。循環小数 - Wikipedia によると、有限小数部分を a、循環節の小数表記を b、節の長さを n とすると、循環小数 x は次の式で表すことができる、とのことです。

\(\begin{eqnarray} x &=& a + b\left(1 + \dfrac{1}{10^n} + \dfrac{1}{10^{2n}} + \dfrac{1}{10^{3n}} + \cdots\right) \\ &=& a + b\dfrac{10^n}{10^n - 1} \end{eqnarray}\)

ここで、カッコの中は初項 1, 公比 1 / (10^n) の無限等比級数になるので、その和は次の公式より求めることができます。

\( \displaystyle \sum_{n=0}^{\infty} ar^n = \dfrac{a}{1-r}, \quad (|r| \lt 1) \)

簡単な例を示しましょう。

\(\begin{array}{l} 0.\dot{1}4285\dot{7} = 0.142857 \times \dfrac{10^6}{10^6 - 1} = \dfrac{142857}{999999} = \dfrac{1}{7} \\ 0.1\dot{6} = 0.1 + 0.06 \times \dfrac{10}{9} = \dfrac{1}{10} + \dfrac{6}{100} \times \dfrac{10}{9} = \dfrac{15}{90} = \dfrac{1}{6} \end{array}\)

プログラムを作る場合、次のように考えると簡単です。

有限小数部分を表すリストを xs とすると

有限小数部分 = p / q
ただし p = xs を整数に変換
       q = 10 ^ (len(xs) - 1)

循環節を表すリストを ys とすると

循環節 = p' / q'
ただし p' = ys を整数に変換
       q' = (10 ^ len(ys)) - 1

            p       p'       p * q' + p'
循環小数 = --- + -------- = -------------
            q     q * q'        q * q'

冒頭の有限小数部分を分数に変換するのは簡単ですね。先頭が整数部分になるので、小数部分の桁はリスト xs の長さ - 1 になります。循環節だけを分数に変換する場合、たとえば 1 / 7 の循環節は [1,4,2,8,5,7] になりますが、分子 p' は 0.142857 * 10^6 = 142857 となるので、循環節を表すリストを整数に変換するだけでよいことがわかります。有限小数部分がある場合は、その桁数だけ循環節の部分を右シフトすればよいので、p' / q' に 1 / q を掛けるだけです。

リスト : 循環小数を分数に直す

  def fromRepdec(xs: List[Long], ys: List[Long]): (Long, Long) = {
    def toNum(xs: List[Long]): BigInt =
      xs.foldLeft(0: BigInt)((a: BigInt, x: Long) => a * 10 + x)

    val p = toNum(xs)
    val q = (10: BigInt) pow (xs.length - 1)

    val p1 = toNum(ys)
    val q1 = ((10: BigInt) pow (ys.length)) - 1

    val a = q * q1
    val b = q1 * p + p1
    val c = a gcd b
    ((b / c).toLong, (a / c).toLong)
  }

計算は BigInt で行っています。あとは、アルゴリズムをそのままプログラムしただけなので、とくに難しいところは無いと思います。

●解答20

リスト : バブルソート

  def bubleSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
    val k = buff.size - 1
    for (i <- 0 until k) {
      for (j <- k until i by -1) {
        if (buff(j - 1) > buff(j)) {
          val tmp = buff(j - 1)
          buff(j - 1) = buff(j)
          buff(j) = tmp
        }
      }
    }
  }

最初のループで k 回 (データの個数 - 1) だけ繰り返します。2 番目のループで buff の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。

●プログラムリスト

//
// yasp02.scala : Yet Another Scala Problems
//
//                Copyright (C) 2014-2024 Makoto Hiroi
//
import scala.math.Ordered.orderingToOrdered

object yasp02 {
  // Q11
  def factorization(n: Long): List[(Long, Long)] = {
    //
    def factorSub(n: Long, m: Long, c: Long): (Long, Long) =
      if (n % m != 0) (c, n) else factorSub(n / m, m, c + 1)
    //
    def iter(i: Long, n: Long, a: List[(Long, Long)]): List[(Long, Long)] =
      if (n == 1) a.reverse
      else if (n < i * i) ((n, 1L)::a).reverse
      else {
        val (c, m) = factorSub(n, i, 0)
        if (c == 0) iter(i + 2, n, a)
        else iter(i + 2, m, (i, c)::a)
      }
    //
    val (c, m) = factorSub(n, 2, 0)
    if (c > 0) iter(3, m, (2L, c)::Nil) else iter(3, n, Nil)
  }

  // Q12
  def divisorNum(n: Long): Long = {
    var a = 1L
    for ((_, q) <- factorization(n)) a *= q + 1
    a
  }

  // 別解
  def divisorNum1(n: Long): Long =
    factorization(n).foldLeft(1L)((a: Long, x: (Long, Long)) => a * (x._2 + 1))

  // Q13

  // 累乗
  def pow(x: Long, y: Long): Long =
    if (y == 0)
      1
    else {
      val z = pow(x, y / 2)
      if (y % 2 == 0) z * z else z * z * x
    }

  def sigma(p: Long, n: Long): List[Long] =
    (0L to n).toList.map(pow(p, _))

  def divisorSum(n: Long): Long = {
    var a = 1L
    for ((p, q) <- factorization(n)) a *= sigma(p, q).sum
    a
  }

  // 別解
  def divisorSum1(n: Long): Long =
    factorization(n).foldLeft(1L)((a: Long, x: (Long, Long)) => a * sigma(x._1, x._2).sum)

  // Q14
  def product(xs: List[Long], ys: List[Long]): List[Long] =
    for (x <- xs; y <- ys) yield x * y

  def divisor(n: Long): List[Long] = {
    val (p1, x1)::xs = factorization(n)
    xs.foldLeft(sigma(p1, x1))((a: List[Long], x: (Long, Long)) => product(sigma(x._1, x._2), a)).sorted
  }

  // Q15
  def perfectNumber(n: Long): Unit = {
    (2L to n).foreach(x => if (divisorSum(x) - x == x) println(x))
  }

  // Q16
  def yuuaiNumber(n: Long): Unit = {
    (2L to n).foreach(x => {
        val m = divisorSum(x) - x
        if (x < m && x == divisorSum(m) - m) println((x, m))
      })
  }

  // Q17
  def splitAt[A](xs: List[A], n: Int): (List[A], List[A]) =
    (xs, n) match {
      case (Nil, _) | (_, 0) => (Nil, xs)
      case (x::xs1, _) => {
        val (a, b) = splitAt(xs1, n - 1)
        (x::a, b)
      }
    }

  def partition[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) =
    xs match {
      case Nil => (Nil, Nil)
      case x::xs1 => {
        val (a, b) = partition(f, xs1)
        if (f(x)) (x::a, b) else (a, x::b)
      }
    }

  def span[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) =
    xs match {
      case Nil => (Nil, Nil)
      case (ys @ x::xs1) if (!f(x)) => (Nil, ys)
      case x::xs1 => {
        val (a, b) = span(f, xs1)
        (x::a, b)
      }
    }

  // 別解
  def splitAt1[A](xs: List[A], n: Int): (List[A], List[A]) =
    (xs.take(n), xs.drop(n))

  def partition1[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) =
    (for (x <- xs if (f(x))) yield x, for (x <- xs if (!f(x))) yield x)

  def span1[A](f: A => Boolean, xs: List[A]): (List[A], List[A]) = {
    val a = xs.takeWhile(f)
    (a, xs.drop(a.length))
  }

  // Q18
  def repdec(m: Long, n: Long): (List[Long], List[Long]) = {
    def iter(m: Long, xs: List[Long], ys: List[Long]): (List[Long], List[Long]) = {
      val p = m / n
      val q = m % n
      if (q == 0) ((p::ys).reverse, List(0))
      else if (xs contains q) {
        val a = xs.reverse.takeWhile(_ != q)
        (p::ys).reverse.splitAt(a.length + 1)
      } else iter(q * 10, q::xs, p::ys)
    }
    //
    iter(m, Nil, Nil)
  }

  // Q19
  def fromRepdec(xs: List[Long], ys: List[Long]): (Long, Long) = {
    def toNum(xs: List[Long]): BigInt =
      xs.foldLeft(0: BigInt)((a: BigInt, x: Long) => a * 10 + x)

    val p = toNum(xs)
    val q = (10: BigInt) pow (xs.length - 1)

    val p1 = toNum(ys)
    val q1 = ((10: BigInt) pow (ys.length)) - 1

    val a = q * q1
    val b = q1 * p + p1
    val c = a gcd b
    ((b / c).toLong, (a / c).toLong)
  }

  // Q20
  def bubleSort[A](buff: Array[A])(implicit f: A => Ordered[A]): Unit = {
    val k = buff.size - 1
    for (i <- 0 until k) {
      for (j <- k until i by -1) {
        if (buff(j - 1) > buff(j)) {
          val tmp = buff(j - 1)
          buff(j - 1) = buff(j)
          buff(j) = tmp
        }
      }
    }
  }
}

Yet Another Scala Problems (2)

●問題11

●問題12

●問題13

●問題14

●問題15

●問題16

●問題17

●問題18

●問題19

●問題20

●解答11

●解答12

●解答13

●解答14

●解答15

●解答16

●解答17

●解答18

●解答19

●解答20

●プログラムリスト