柚子快报激活码778899分享：大数据技术之
第十四章 使用递归的方式去思考，去编程14.1 基本介绍14.2 Scala 提倡函数式编程(递归思想)14.3 应用案例1-求和14.4 应用案例2-求最大值14.5 应用案例3-翻转字符串14.6 应用案例4-求阶乘14.7 应用案例5-求x的n次方14.8 应用案例6-求斐波那契数14.9 作业07、作业08和作业0914.9.1 作业0714.9.2 作业0814.9.2 作业09
第十四章 使用递归的方式去思考，去编程
14.1 基本介绍
14.2 Scala 提倡函数式编程(递归思想)
编程范式
14.3 应用案例1-求和
scala 中循环不建议使用 while 和 do…while，而建议使用递归。计算1-50的和示例代码如下：
package com.atguigu.chapter14import java.text.SimpleDateFormatimport java.util.Date/** * 1、计算1-50的和。使用常规的方式解决。 */object RecursiveDemo01 { def main(args: Array[String]): Unit = { // 方式一：使用常规的方式解决。 val now1: Date = new Date() val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss") val date1 = dateFormat.format(now1) println("date1=" + date1) // 输出时间 var res = BigInt(0) // 存放计算的结果 var num = BigInt(1) // 变化的数 val maxVal = BigInt(99999999l) // 测试效率使用大数 while (num <= maxVal) { res += num // 累加 num += 1 // 变量的叠加 } println("res=" + res) val now2: Date = new Date() val date2 = dateFormat.format(now2) println("date2=" + date2) // 输出时间 }}
输出结果如下：
date1=2019-04-03 10:11:44res=4999999950000000date2=2019-04-03 10:11:49
示例代码如下：
package com.atguigu.chapter14import java.text.SimpleDateFormatimport java.util.Date/** * 1、计算1-50的和。递归的方式来解决 */object RecursiveDemo02 { def main(args: Array[String]): Unit = { val now1: Date = new Date() val dateFormat: SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss") val date1 = dateFormat.format(now1) println("date1=" + date1) // 输出时间 // 测试 var num = BigInt(1) var sum = BigInt(0) var res = mx(num, sum) println("res=" + res) val now2: Date = new Date() val date2 = dateFormat.format(now2) println("date2=" + date2) // 输出时间 } // 使用递归的方式来解决 def mx(num: BigInt, sum: BigInt): BigInt = { if (num <= 99999999l) return mx(num + 1, sum + num) else return sum }}
输出结果如下：
date1=2019-04-03 10:11:59res=4999999950000000date2=2019-04-03 10:12:05
14.4 应用案例2-求最大值
求最大值示例代码如下：
package com.atguigu.chapter14/** * 2、求最大值 */object RecursiveDemo03 { def main(args: Array[String]): Unit = { def mymax(xs: List[Int]): Int = { if (xs.isEmpty) throw new java.util.NoSuchElementException if (xs.size == 1) xs.head else if (xs.head > mymax(xs.tail)) xs.head else mymax(xs.tail) } println(mymax(List(1, 2, 3, 4, 5))) }}
输出结果如下：
5
14.5 应用案例3-翻转字符串
翻转字符串示例代码如下：
package com.atguigu.chapter14/** * 3、翻转字符串 */object RecursiveDemo04 { def main(args: Array[String]): Unit = { def myreverse(xs: String): String = if (xs.length == 1) xs else myreverse(xs.tail) + xs.head println(myreverse("abc")) }}
输出结果如下：
cba
14.6 应用案例4-求阶乘
求阶乘示例代码如下：
package com.atguigu.chapter14/** * 4、求阶乘 */object RecursiveDemo05 { def main(args: Array[String]): Unit = { def myfactorial(n: BigInt): BigInt = if (n == 0) 1 else n * myfactorial(n - 1) println(myfactorial(5)) }}
输出结果如下：
120
14.7 应用案例5-求x的n次方
示例代码如下：
package com.atguigu.chapter14/** * 5、求x的n次方 */object RecursiveDemo06 { def main(args: Array[String]): Unit = { println(mi(2.5, 3)) } // 递归的妙用：求 x 的 n 次方，厉害啊！！！ def mi(x: Double, n: Int): Double = { if (n == 0) 1 // x 的 0 次方等于 1 else if (n > 0) x * mi(x, n - 1) else 1 / mi(x, -n) }}
输出结果如下：
15.625
14.8 应用案例6-求斐波那契数
示例代码如下：
package com.atguigu.chapter14import scala.io.StdIn/** * 6、给你一个整数n，求出它的斐波那契数（1,1,2,3,5,8,13...） */object RecursiveDemo07 { def main(args: Array[String]): Unit = { var count = BigInt(0) // 研究下递归求斐波那契数的递归次数的增长情况：指数爆炸式增长 def fbn(n: Int): Int = { count += 1 if (n == 1 || n == 2) { 1 } else { fbn(n - 1) + fbn(n - 2) // 因为我们这里调用了2次递归，出现了重复计算，需要考虑优化：方案一：改递归为迭代，方案二：减少递归次数。 } } println("请输入一个正整数：") val n = StdIn.readInt() printf("%d的斐波那契数是：%d", n, fbn(n)) println() println("调用的次数=" + count) }}
关于斐波那契数列的优化：https://blog.csdn.net/dadai_/article/details/50209511作为算法工程师/科学家，名校公开课程或者考研课程《数值分析》需要学习。
14.9 作业07、作业08和作业09
14.9.1 作业07
数据结构(集合)1、编写一段代码，将 a 设置为一个 n 个随机整数的数组，要求随机数介于 0 和 n 之间。
2、编写一个循环，将整数数组中相邻的元素置换。比如 Array(1, 2, 3, 4, 5) 置换后为 Array(2, 1, 4, 3, 5)。
3、给定一个整数数组，产出一个新的数组，包含原数组中的所有正值，以原有顺序排列，之后的元素是所有零或负值，以原有顺序排列。
4、设置一个映射，其中包含你想要的一些装备，以及它们的价格。然后根据这个映射构建另一个新映射，采用同一组键，但是价格上打9折。
5、编写一个函数 minmax(values: Array[Int]), 返回数组中最小值和最大值的对偶。
6、编写一个函数，从一个整型链表中去除所有的零值。
7、编写一个函数，接受一个字符串的集合，以及一个从字符串到整数值的映射。返回整形的集合，其值为能和集合中某个字符串相对应的映射的值。举例来说，给定 Array("Tom", "Fred", "Harry") 和 Map("Tom"->3, "Dick"->4, "Harry"->5)，返回 Array(3, 5)。提示：用 flatMap 将 get 返回的 Option 值组合在一起。
8、实现一个函数，作用与 mkStirng 相同，提示：使用 reduceLeft 实现。
9、给定整型列表lst，(lst :\ List[Int]())(_ :: _)得到什么？(List[Int]() /: lst)(_ :+ _)又得到什么？如何修改他们中的一个，以对原列表进行反向排列？
10、编写一个函数，将 Double 数组转换成二维数组。传入列数作为参数。具体来说，传入 Array(1, 2, 3, 4, 5, 6) 和 3 列，返回 Array(Array(1, 2, 3), Array(4, 5, 6))。
示例代码链接：xxx
14.9.2 作业08
类型参数1、定义一个不可变类 Pair1[T, S]，带一个 swap 方法，返回组件交换过位置的新对偶。2、定义一个可变类 Pair2[T]，带一个 swap 方法，交换对偶中组件的位置。3、给定类 Pair3[T, S]，编写一个泛型方法 swap，接受对偶作为参数并返回组件交换过位置的新对偶。4、给定可变类 Pair4[S, T]，使用类型约束定义一个 swap 方法，当类型参数相同时可以被调用。
示例代码如下：
package com.atguigu.chapter14.homework.hw02/** * 类型参数 * 1、定义一个不可变类 Pair1[T, S]，带一个 swap 方法，返回组件交换过位置的新对偶。 * 2、定义一个可变类 Pair2[T]，带一个 swap 方法，交换对偶中组件的位置。 * 3、给定类 Pair3[T, S]，编写一个泛型方法 swap，接受对偶作为参数并返回组件交换过位置的新对偶。 * 4、给定可变类 Pair4[S, T]，使用类型约束定义一个 swap 方法，当类型参数相同时可以被调用。 */object Exercise01 { def main(args: Array[String]): Unit = { }}// 1、定义一个不可变类 Pair1[T, S]，带一个 swap 方法，返回组件交换过位置的新对偶。final class Pair1[T, S](val t: T, val s: S) { def swap() = { new Pair1(s, t) }}// 2、定义一个可变类 Pair2[T]，带一个 swap 方法，交换对偶中组件的位置。class Pair2[T](val t: T, val s: T) { def swap() = { new Pair2(s, t) }}// 3、给定类 Pair3[T, S] ，编写一个泛型方法 swap，接受对偶作为参数并返回组件交换过位置的新对偶。class Pair3[T, S](val t: T, val s: S) { def swap[T, S](t: T, s: S) = { new Pair3(s, t) }}// 4、给定可变类 Pair4[S, T]，使用类型约束定义一个 swap 方法，当类型参数相同时可以被调用。class Pair4[S, T](val s: S, val t: T) { def swap(implicit env2: S =:= T) = { new Pair4(t, s) }}
14.9.2 作业09
模式匹配1、利用模式匹配，编写一个 swap 函数，接受一个整数的对偶，返回对偶的两个组成部件互换位置的新对偶。2、利用模式匹配，编写一个 swap 函数，交换数组中的前两个元素的位置，前提条件是数组长度至少为 2。3、编写一个函数，计算 List[Option[Int]] 中所有非 None 值之和。不得使用 match 语句。
示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 模式匹配 * 1、利用模式匹配，编写一个 swap 函数，接受一个整数的对偶，返回对偶的两个组成部件互换位置的新对偶。 * 2、利用模式匹配，编写一个 swap 函数，交换数组中的前两个元素的位置，前提条件是数组长度至少为 2。 * 3、编写一个函数，计算 List[Option[Int]] 中所有非 None 值之和。不得使用 match 语句。 */object Exercise01 { def main(args: Array[String]): Unit = { println(swap1(100, "hello")) val arr = swap2(Array(1, 2, 4, 5)) for (item <- arr) { println(item + " ") } val x = List(Some(1), None, Some(2), None, Some(3)) println(sum(x)) } // 1、利用模式匹配，编写一个 swap1 函数，接受一个整数的对偶，返回对偶的两个组成部件互换位置的新对偶。 def swap1[S, T](tup: (S, T)) = { tup match { case (a, b) => (b, a) } } // 2、利用模式匹配，编写一个 swap2 函数，交换数组中的前两个元素的位置，前提条件是数组长度至少为 2。 def swap2(array: Array[Any]) = { array match { // @ 表示法将嵌套的值绑定到变量。*_ 绑定剩余元素到 rest。 case Array(first, second, rest @ _*) => Array(second, first) ++ rest // ++ 表示拼接 case _ => array } } // 3、编写一个函数，计算 List[Option[Int]] 中所有非 None 值之和。不得使用 match 语句。 def sum(lst: List[Option[Int]]) = lst.map(_.getOrElse(0)).sum}
输出结果如下：
(hello,100)2 1 4 5 6
高阶函数1、编写一个 compose 函数，将两个类型为 Double => Option[Double] 的函数组合在一起，产生另一个同样类型的函数。如果其中一个函数返回 None，则组合函数也应返回 None。例如：def f(x: Double) = if (x > 0) Some(sqrt(x)) else Nonedef g(x: Double) = if (x != 1) Some(1 / ( x - 1)) else Noneval h = compose(f, g)h(2) 将得到 Some(1)，而 h(1) 和 h(0) 将得到 None。
示例代码如下：
package com.atguigu.chapter14.homework.hw03import scala.math.sqrt/** * 高阶函数 * 1、编写一个 compose 函数，将两个类型为 Double => Option[Double] 的函数组合在一起，产生另一个同样类型的函数。如果其中一个函数返回 None，则组合函数也应返回 None。例如： * def f(x: Double) = if (x > 0) Some(sqrt(x)) else None * def g(x: Double) = if (x != 1) Some(1 / ( x - 1)) else None * val h = compose(f, g) * h(2) 将得到 Some(1.0)，而 h(1) 和 h(0) 将得到 None。 * */object Exercise02 { def main(args: Array[String]): Unit = { val h = compose(f, g) println(h(2)) println(h(1)) println(h(0)) } def f(x: Double) = if (x > 0) Some(sqrt(x)) else None def g(x: Double) = if (x != 1) Some(1 / (x - 1)) else None def compose(f: Double => Option[Double], g: Double => Option[Double]) = { // 返回一个匿名函数 (x: Double) => // 如果其中一个函数返回 None，则组合函数也应返回 None if (f(x) == None || g(x) == None) None else g(x) }}
输出结果如下：
Some(1.0)NoneNone
2、编写函数 values(fun: (Int) => Int, low: Int, high: Int)，该函数输出一个集合，对应给定区间内给定函数的输入和输出。比如，values(x => x * x, -5, 5) 应该产出一个对偶的集合 (5,25)(4,16)(3,9),…,(-4,16)(-5,25)示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 2、编写函数 values(fun: (Int) => Int, low: Int, high: Int)，该函数输出一个集合，对应给定区间内给定函数的输入和输出。 * 比如，values(x => x * x, -5, 5) 应该产出一个对偶的集合 (5,25)(4,16)(3,9),...,(-4,16)(-5,25) */object Exercise03 { def main(args: Array[String]): Unit = { println(values(x => x * x, -5, 5).mkString) } def values(fun: (Int) => Int, low: Int, high: Int) = { var array = List[(Int, Int)]() low to high foreach { x => array = (x, fun(x)) :: array } array }}
输出结果如下：
(5,25)(4,16)(3,9)(2,4)(1,1)(0,0)(-1,1)(-2,4)(-3,9)(-4,16)(-5,25)
3、如何用 reduceLeft 得到数组 Array(1, 333, 4, 6, 4, 4, 9, 32, 6, 9, 0, 2) 中的最大元素？示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 3、如何用 reduceLeft 得到数组 Array(1, 333, 4, 6, 4, 4, 9, 32, 6, 9, 0, 2) 中的最大元素？ */object Exercise04 { def main(args: Array[String]): Unit = { val arr = Array(1, 333, 4, 6, 4, 4, 9, 32, 6, 9, 0, 2) println(arr.reduceLeft(f1)) // 简写形式 // println(arr.reduceLeft((l, r) => if (l > r) l else r)) } def f1(l: Int, r: Int): Int = { if (l > r) l else r }}
输出结果如下：
333
4、用 to 和 reduceLeft 实现阶乘函数，不得使用循环或递归。示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 4、用 to 和 reduceLeft 实现阶乘函数，不得使用循环或递归。 */object Exercise05 { def main(args: Array[String]): Unit = { println(factorial(5)) } def factorial(n: Int): Int = { // 1 to n reduceLeft ((n1: Int, n2: Int) => n1 * n2) // 1 to n reduceLeft ((n1, n2) => n1 * n2) 1 to n reduceLeft (_ * _) }}
输出结果如下：
120
5、编写函数 largest(fun: (Int) => Int, inputs: Seq[Int])，输出在给定输入序列中给定函数的最大值。举例来说，largest(x => 10 * x - x * x, 1 to 10) 应该返回 25。不得使用循环或递归。示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 5、编写函数 largest(fun: (Int) => Int, inputs: Seq[Int])，输出在给定输入序列中给定函数的最大值。 * 举例来说，largest(x => 10 * x - x * x, 1 to 10) 应该返回 25。不得使用循环或递归。 */object Exercise06 { def main(args: Array[String]): Unit = { println(largest1(x => 10 * x - x * x, 1 to 10)) println(largest2(x => 10 * x - x * x, 1 to 10)) } def largest1(fun: (Int) => Int, inputs: Seq[Int]) = { inputs.foldLeft(1)((a, b) => if (fun(b) > a) fun(b) else a) } def largest2(fun: (Int) => Int, inputs: Seq[Int]) = { inputs.map(fun(_)).max }}
输出结果如下：
2525
6、要得到一个序列的对偶很容易，比如:val pairs = (1 to 10) zip (11 to 20)编写函数 adjustToPair，该函数接受一个类型为 (Int, Int) => Int 的函数作为参数，并返回一个等效的，可以以对偶作为参数的函数。举例来说就是：adjustToPair(_ * _)((6, 7)) 应得到 42。然后用这个函数通过 map 计算出各个对偶的元素之和。示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 6、要得到一个序列的对偶很容易，比如: * val pairs = (1 to 10) zip (11 to 20) * 编写函数 adjustToPair，该函数接受一个类型为 (Int, Int) => Int 的函数作为参数，并返回一个等效的，可以以对偶作为参数的函数。 * 举例来说就是：adjustToPair(_ * _)((6, 7)) 应得到 42。然后用这个函数通过 map 计算出各个对偶的元素之和。 */object Exercise07 { def main(args: Array[String]): Unit = { def adjustToPair(fun: (Int, Int) => Int) = { (x: (Int, Int)) => fun(x._1, x._2) } val x = adjustToPair(_ * _)((6, 7)) println(x) val pairs = (1 to 10) zip (11 to 20) println(pairs) val y = pairs.map(adjustToPair(_ + _)) println(y) }}
输出结果如下：
42Vector((1,11), (2,12), (3,13), (4,14), (5,15), (6,16), (7,17), (8,18), (9,19), (10,20))Vector(12, 14, 16, 18, 20, 22, 24, 26, 28, 30)
7、实现一个 unless 控制抽象，工作机制类似 if，但条件是反过来的。示例代码如下：
package com.atguigu.chapter14.homework.hw03/** * 7、实现一个 unless 控制抽象，工作机制类似 if，但条件是反过来的。 */object Exercise08 { def main(args: Array[String]): Unit = { } def unless(conditon: => Boolean)(block: => Unit) = { if (!conditon) { block } } unless(0 > 1) { println("Unless!") }}
柚子快报激活码778899分享：大数据技术之
发表评论