2^i * 3^j * 5^k なる整数 in Scala DouKaku?

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

　[1..100]>>=penさんの投稿を参考に書いてみました。

class CHummingNumbers {
    def next(c:Int):Int = (BigInt(30).pow(c) % c).intValue match {
            case 0 => c
            case _ => next(c+1)
        }
    def take(n:Int,c:Int):List[Int] = n match {
            case 0 => List()
            case _ => next(c) match { case v => v::take(n-1,v+1) }
        }
    def take(n:Int):List[Int] = take(n,1)
}
object HummingNumbers {
    def main(args:Array[String]):Unit = {
        try {
            val    n:Int = args.length match {
                case 1 => args(0).toInt
                case _ => 100
            }
            println((new CHummingNumbers).take(n).mkString("\n"))
        } catch {
            case e => e.printStackTrace
        }
    }
}

　Streamを使って書いてみました。

object HammingNumbers {
    def from(n:Int):Stream[Int] = Stream.cons(n,from(n+1))
    def hammings(s:Stream[Int]):Stream[Int] = {
        def divide(n:Int,b:Int):Int = (n % b == 0) match {
                case false => n
                case _ => divide(n/b,b)
            }
        Stream.cons(s.head,hammings(s.tail.filter { n => List(2,3,5).foldLeft(n) { (v,b) => divide(v,b) } == 1 }))
    }
    def hammings():Stream[Int] = hammings(from(1))
    def main(args:Array[String]):Unit = {
        try {
            val    n:Int = args.length match {
                case 1 => args(0).toInt
                case _ => 100
            }
            println(hammings().take(n).mkString("\n"))
        } catch {
            case e => e.printStackTrace
        }
    }
}

　#7638と#7671のやり方で。

see: 「レッツ・チャレンジ！パソコン甲子園」第11回の解答例

import    scala.collection.immutable.SortedSet
import    scala.collection.immutable.TreeSet
abstract class CHammingNumbers {
    def take(n:Int):List[Int]
}
class CHammingNumbersG extends CHammingNumbers {
    def next(s:List[Int],h:List[Int]):Tuple2[List[Int],List[Int]] = {
        val    m:List[Int] = s.zip(List(2,3,5)).map { v => h.apply(v._1)*v._2 }
        val    n:Int = m.sort { (a,b) => a < b }.head
        (s.zip(m).map { v => (v._2 == n) match { case true => v._1 + 1; case _ => v._1 } },h+n)
    }
    def take(n:Int,s:List[Int],h:List[Int]):Tuple2[List[Int],List[Int]] = n match {
            case 0 => (s,h)
            case _ => next(s,h) match { case v => take(n-1,v._1,v._2) }
        }
    def take(n:Int):List[Int] = take(n-1,List(0,0,0),List(1))._2
}
class CHammingNumbersS extends CHammingNumbers {
    def next(c:SortedSet[Int]):Tuple2[Int,SortedSet[Int]] = (c.firstKey,(TreeSet(c.firstKey*2,c.firstKey*3,c.firstKey*5)++(c-c.firstKey)))
    def take(n:Int,c:SortedSet[Int]):List[Int] = n match {
            case 0 => List()
            case _ => next(c) match { case v => v._1::take(n-1,v._2) }
        }
    def take(n:Int):List[Int] = take(n,TreeSet(1))
}
object HammingNumbers {
    def main(args:Array[String]):Unit = {
        try {
            val    n:Int = args.length match {
                case 1 => args(0).toInt
                case _ => 100
            }
            List(new CHammingNumbersG,new CHammingNumbersS).foreach { h => println(h.take(n).mkString("\n")) }
        } catch {
            case e => e.printStackTrace
        }
    }
}

DouKaku?

2^i * 3^j * 5^k なる整数

Posted feedbacks - Scala

Index

Feed

Other

Link

Pathtraq