假设有一圈石子，从1到n比较。然后依次每隔一个石子选出一个，直到剩余一个；问最后选出的石子的编号是多少；

（至少）有三种方法可以解决这个问题；如下面的代码所示：

object App extends App {  def native(n: Int): Int = {    def dispatch(pre: List[Int], list: List[Int]): List[Int] =      list match {        case Nil => pre        case h :: Nil => pre.tail :+ h        case h :: x :: tail => dispatch(pre :+ h, tail)      }    def play(list: List[Int]): Int =      if(list.size == 1) list.head      else {        play(dispatch(Nil, list))      }    play((1 to n).toList)  }  def smart(n: Int): Int = {    val j = Array.fill(n + 1)(1)    def calc(k: Int): Unit = {      if(k <= n) {        if(k % 2 == 0) {          j(k) = 2 * j(k / 2) - 1        } else {          j(k) = 2 * j(k / 2) + 1        }        calc(k + 1)      }    }    calc(2)    j(n)  }  def best(n: Int): Int = {    def binaryRep(n: Int): List[Int] = {      if(n == 0) {        Nil      } else if(n == 1) {        List(1)      } else {        (n % 2) :: binaryRep(n >> 1)      }    }    val br = binaryRep(n).reverse    var cycleLeftShift = br.tail :+ br.head    def toDecimal(list: List[Int], base: Int, result: Int): Int = {      list match {        case Nil => result        case h :: tail => toDecimal(tail, base * 2, result + h * base)      }    }    toDecimal(cycleLeftShift.reverse, 1, 0)  }  for {    i <- 1 until 15  } {    println(s"native: J($i) = " + native(i))  }  for {    i <- 1 until 15  } {    println(s"smart:  J($i) = " + smart(i))  }  for {    i <- 1 until 15  } {    println(s"best:  J($i) = " + best(i))  }}

这三种方法依次是是模拟，数学计算，还有利用该问题本身的特性；

1. 模拟的方法比较直观，迭代多次，直到剩余一个元素为止；每次迭代都依次剔除一个元素；需要注意的时，但有奇数个石子的时候，在头部的石子也需要被剔除掉。因为是个环么~~~

2. 数学的方法是基于以下的观察：

   a. 当n = 1时，J(1) = 1， 

   b. 假设n = 2k时， 假设最后编号为J(n)的石子留了下来；经过第一轮剔除，编号为偶数的石子都被剔除了，所以所有的石子（除去编号1）的位置都往前移动，比如编号3到位置2，编号5到位置3，等等。原有编号与新编号之间的关系为x = 2 * y - 1; 所以有J(n) = 2 * J(k) - 1;

   c. 当n = 2 * k + 1的时候，经过第一轮剔除，除了偶数编号的石子要被移除掉，编号为1的石子也会被移除；所以原有编号3变为移动到位置1，编号5移动到位置2，等等。可以得到关系x = 2 * y + 1; 所以有J(n) = 2 * J(k) + 1;

3. 第三种方法，我也不知道为什么~~~~~~