■
面白そうな問題を見つけたのでScalaで解いてみました。
問題はコチラ
http://nabetani.sakura.ne.jp/hena/ord13updowndouble/
/** * 増やす減らす二倍する 〜 横へな 2013.9.6 参考問題 * @see http://nabetani.sakura.ne.jp/hena/ord13updowndouble/ */ import scala.collection.mutable.ListBuffer object Ord13updowndouble { type 手 = Char // '+'/'-'/'*' case class 状態(val 数:Int = 0, val 手順:List[手] = Nil) { override def toString = 数 + " 手数=" + 手順.length + " 手順=" + { 手順.reverse.map{ _ match { case '+' => "+1" case '-' => "-1" case '*' => "*2" } }.mkString("[", " ", "]") } } /** 引数のそれぞれの状態に対して、次の状態を作成する。 */ def createNextStatus(stats: List[状態]): List[状態] = { val result = new ListBuffer[状態] for (s <- stats) { if (s.数 != 0) { result += new 状態(s.数 - 1, '-' :: s.手順) } result += new 状態(s.数 + 1, '+' :: s.手順) result += new 状態(s.数 * 2, '*' :: s.手順) } result.toList } /** 解く。同じ手数で複数の解があれば、すべて返す。 */ def solv(数:Int):List[状態] = { var list = List(new 状態()) while (true) { // 解けた状態を探す。 val solved = list.filter{s => s.数 == 数} if (solved.length != 0) return solved list = createNextStatus(list) } Nil } def main(args:Array[String]) { val solved = solv(59) solved foreach println } }
結果
59 手数=9 手順=[+1 +1 *2 *2 *2 -1 *2 *2 -1] 59 手数=9 手順=[+1 *2 *2 *2 *2 -1 *2 *2 -1]