大数据技术之_16_Scala学习_10_使用递归的方式去思考，去编程+作业07/08/09

黑泽君

发布于 2019-04-17 17:14:45

1K0

发布于 2019-04-17 17:14:45

第十四章使用递归的方式去思考，去编程 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和作业09 14.9.1 作业07 14.9.2 作业08 14.9.2 作业09

第十四章使用递归的方式去思考，去编程

14.1 基本介绍

14.2 Scala 提倡函数式编程(递归思想)

编程范式

14.3 应用案例1-求和

scala 中循环不建议使用 while 和 do…while，而建议使用递归。 计算1-50的和 示例代码如下：

package com.atguigu.chapter14

import java.text.SimpleDateFormat
import 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:44
res=4999999950000000
date2=2019-04-03 10:11:49

示例代码如下：

package com.atguigu.chapter14

import java.text.SimpleDateFormat
import 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:59
res=4999999950000000
date2=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)))
  }
}

输出结果如下：

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))
  }
}

输出结果如下：

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.chapter14

import 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 {
      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 None def g(x: Double) = if (x != 1) Some(1 / ( x - 1)) else None val h = compose(f, g) h(2) 将得到 Some(1)，而 h(1) 和 h(0) 将得到 None。

示例代码如下：

package com.atguigu.chapter14.homework.hw03

import 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)，而 h(1) 和 h(0) 将得到 None。
  *
  */
object Exercise02 {
  def main(args: Array[String]): Unit = {
    val h = compose(f, g)
    println(h(2))
  }

  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) =>
      if (f(x) == None || g(x) == None) None else g(x)
  }
}

输出结果如下：

Some(1)

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
  }
}

输出结果如下：

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 (_ * _)
  }
}

输出结果如下：

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
  }
}

输出结果如下：

25
25

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)
  }
}

输出结果如下：

42
Vector((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!")
  }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-04-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度