次は積を生成してそれが回文数になっているか判定します。
PriorityQueue
積を生成するのは簡単ですが、それを降順に並べなければなりません。それを簡単にしかも速く可能にするのがPriorityQueueです。
import scala.collection.mutable.PriorityQueue val pq = new PriorityQueue[Int] pq.enqueue(3) pq.enqueue(1) println (pq.dequeue) // 3 pq.enqueue(4) println (pq.dequeue) // 4 println (pq.dequeue) // 1
この問題では、キューに追加しながら取り出すのでキューはmutableでなければなりません。Scalaではmutableなコレクションも用意されていますが、immutableなコレクションを使うことが推奨されていてデフォルトではmutableなコレクションは使えません。import文を書く必要があります。
キューに投入するメソッドはenqueue、キューから取り出すのはdequeueです。
イメージ的にはこんな風に積を生成します。
999*999┳999*998━999*997━…
┗998*998┳998*997━…
┗997*997┳…
┗…まず、999*999をキューに投入します。999*999がキューから取り出されたら、乗数の方をデクリメントした999*998をキューに投入します。また、被乗数と乗数が等しければ両方1小さい、ここでは998*998もキューに投入します。そうすると、降順に積を取り出すことができます。キューに投入する積は、(積, 被乗数, 乗数)という形にするとうまく動きます。タプルの左から順に大小を判定されるからです。Pythonなどと同じですね。
回文数の判定は、ひっくり返して同じか、でよいでしょう。
import Stream.cons import scala.collection.mutable.PriorityQueue def pow(n :Int, e :Int) :Int = if(e == 0) 1 else n * pow(n, e - 1) def reverse(n :Int, m :Int = 0) :Int = if(n == 0) m else reverse(n / 10, m * 10 + n % 10) def is_palindrome(n :Int) = reverse(n) == n def product_stream(pq :PriorityQueue[(Int,Int,Int)]) :Stream[Int] = { val (p, m, n) = pq.dequeue pq.enqueue((m * (n - 1), m, n - 1)) if(m == n) pq.enqueue(((m - 1) * (m - 1), m - 1, m - 1)) cons(p, product_stream(pq)) } val N = 3 val M = pow(10, N) - 1 val pq = new PriorityQueue[(Int,Int,Int)] pq.enqueue((M * M, M, M)) println (product_stream(pq).filter(is_palindrome).head)
