波斯公主选驸马模拟代码实现"/>
波斯公主选驸马模拟代码实现
上篇讲到”公主选驸马“,今天将实现的代码展示下。先列出题目:
波斯公主到了适婚年龄,要选驸马。候选男子100名,都是公主没有见过的。百人以随机顺序,从公主面前逐一经过。每当一位男子在公主面前经过时,公主要么选他为驸马,要么不选。如果选他,其余那些还没有登场的男子就都遣散回家,选驸马的活动也 over 了。如果不选,当下这名男子就离开,也就是 pass 掉此人,下一人登场。被pass 掉的,公主不可以反悔再从选。规则是,公主必须在这百人中选出一人做驸马,也就是说,如果前99人公主都看不中的话,她必须选择第100名男子为驸马,不管他有多么丑陋。
算法说明,我们设定一个数组,以值1-100表示王子的颜值,每次实验都随机打乱顺序。最后统计某次实验每个王子选中的次数和不同算法选中100王子的次数
// simulation(10000, 37)compare//洗牌算法def shuffle(arr: Array[Int]) = {val rnd = new scala.util.Random()for (i <- (1 to arr.length - 1).toArray.reverse)swap(arr, i, rnd.nextInt(i + 1))def swap(arr: Array[Int], a: Int, b: Int) = {val tmp = arr(a)arr(a) = arr(b)arr(b) = tmp}}//统计从某个数,所有王子被选择的次数def selectPrince(arr: Array[Int], n: Int): Int = {shuffle(arr)var max36 = 0;for (i <- 0 to n - 1)if (arr(i) > max36) max36 = arr(i)for (i <- n to 99)if (arr(i) > max36) return arr(i)return arr(99)}//模拟多少次def simulation(n: Int, index: Int): Unit = {val count = new Array[Int](101)for (i <- 1 to n) count(selectPrince((1 to 100).toArray, index)) += 1val out = new java.io.PrintWriter("indexCount.txt")count.foreach(x => if (x != 0) out.println(x))out.close()}//找出最优解def compare(): Unit = {val count = new Array[Int](99)for (i <- 1 to 99) {for (j <- 1 to 10000) {if (selectPrince((1 to 100).toArray, i) == 100) count(i - 1) += 1}}val out = new java.io.PrintWriter("solution.txt")count.foreach(out.println)out.close()}
最后列图:
更多推荐
波斯公主选驸马模拟代码实现
发布评论