0

Image Description

荆文征

Zhidu Inc.


你好,再见

球在矩形内弹射的题目思考

  • 小酒馆老板
  • /
  • 2018/3/6 11:33:0


H2

题目



Image Description
面试题 示意图

如图所示,在证书坐标系内有一个矩形(高M,宽N。M,N是随机整数值,大小不确定),现在从矩形内原点(0,0)以45° ,向上发射一个点(点的大小忽略),词典在矩形内做直线运动,碰到矩形边后完全弹性碰撞反弹,现假设此点在矩形内一直重复做碰撞运动,(即碰撞次数无限),请设计一个程序打印出这个点与矩形每次碰撞的坐标,精确到整数。PS:可使用伪代码或者任意编程语言实现。

今天上班的时候,同时给我发了一下这个题目,一开始觉的难点在于数学计算上,慢慢的发现并不是。接下来我们就来看看这道题的解题思路把。

以下代码,均为 Swift4 版本。


H2

解题思路

其实这个问题看着感觉无从下手,其实我们一步步地分析起来还是很简单的


H3

设置点的类型

首先我们来假设这个Point为一种类型,所以有以下代码,分别有X和Y点来假设球的坐标。

/// 弹射的每一个点的类型抽象
struct Point{
    let x:Int
    let y:Int
}

H3

思考点的弹射方向

接下来我们来思考球都会有哪些行为。球可以向上弹射,也可以向下,也可以向右,也可以向左,总结来看就是球可以做四种方向的运动。分别为
上左,上右,下左,下右。由此设计以下枚举

/// 球 弹射的方向
///
/// - topl: 上左
/// - topr: 上右
/// - bottoml: 下左
/// - bottomr: 下右
enum Dir{
    case topl
    case topr
    case bottoml
    case bottomr
}

H3

思考球碰壁的几种情况

这个时候,我们也会注意到,球碰壁的时候会有几种情况呢? 其实就是球的X,因为X才是限制球的位置的根本,所以X的情况:

  1. 正常的情况 0>X>N
  2. 非正常的晴空 X<0 以及 x>N
  3. 非常巧合的状况 X=0 以及 X=N

H2

根据方向来得出点以及情况

我们接下来,以第一次弹射(TopRight方向)来进行该题的实际解体。


H3

正常情况

如图所示



Image Description
正常情况 示意图

在这种情况下,下一个点的记录为 (x+n,y+m),并且我们可以预测到他的以下次碰撞的角度是 下右


H3

超出范围的情况



Image Description
超出范围的情况 示意图

我们根据图可以看到,我们想要的点在 (n,y+(n-x))。我们可以预测下一次发射角度为 上左


H3

正好撞在角上



Image Description
撞在角上 示意图

我们根据图中可以看出,下一次的点在 (n,m) 。下一次撞击方向为 下左


H3

其他三种角度

其他三种角度,这里就不一一赘述了,总是利用这个方法我们可以得以下4个方法

extension Point{

    /// 将此 Point 按照 上右方向发射
    func topr() -> (Point,Dir) {
        let x = self.x + m
        let y = self.y + m
        if x > n {
            return (Point(x: n, y: n-self.x),.topl)
        }else if x < n{
            return (Point(x: x, y: y),.bottomr)
        }else{
            return (Point(x: x, y: y),.bottoml)
        }
    }

    /// 将此 Point 按照 上左方向发射
    func topl() -> (Point,Dir) {
        let x = self.x - (m-self.y)
        let y = self.y + (m-self.y)
        if x < 0 {
            return (Point(x: 0, y: self.x),.topr)
        }else if x > 0{
            return (Point(x: x, y: y),.bottoml)
        }else{
            return (Point(x: 0, y: m),.bottomr)
        }
    }

    /// 将此 Point 按照 下左方向发射
    func bottoml() -> (Point,Dir) {
        let x = self.x - m
        let y = self.y - m
        if x < 0 {
            return (Point(x: 0, y: m-self.x),.bottomr)
        }else if x > 0{
            return (Point(x: x, y: y),.topl)
        }else{
            return (Point(x: 0, y: 0),.topr)
        }
    }

    /// 将此 Point 按照 下右方向发射
    func bottomr() -> (Point,Dir) {
        let x = self.x + m
        let y = self.y - m
        if x > n {
            return (Point(x: n, y: m-self.x),.bottoml)
        }else if x < n{
            return (Point(x: x, y: y),.topr)
        }else{
            return (Point(x: x, y: y),.topl)
        }
    }
}

H2

完整例子

//: Playground - noun: a place where people can play

import UIKit

/// X - Y 的极限数值
let n = 24
let m = 10

/// 弹射次数
var count = 10

/// 弹射的每一个点的类型抽象
struct Point{
    let x:Int
    let y:Int
}

extension Point{

    /// 将此 Point 按照 上右方向发射
    func topr() -> (Point,Dir) {
        let x = self.x + m
        let y = self.y + m
        if x > n {
            return (Point(x: n, y: n-self.x),.topl)
        }else if x < n{
            return (Point(x: x, y: y),.bottomr)
        }else{
            return (Point(x: x, y: y),.bottoml)
        }
    }

    /// 将此 Point 按照 上左方向发射
    func topl() -> (Point,Dir) {
        let x = self.x - (m-self.y)
        let y = self.y + (m-self.y)
        if x < 0 {
            return (Point(x: 0, y: self.x),.topr)
        }else if x > 0{
            return (Point(x: x, y: y),.bottoml)
        }else{
            return (Point(x: 0, y: m),.bottomr)
        }
    }

    /// 将此 Point 按照 下左方向发射
    func bottoml() -> (Point,Dir) {
        let x = self.x - m
        let y = self.y - m
        if x < 0 {
            return (Point(x: 0, y: m-self.x),.bottomr)
        }else if x > 0{
            return (Point(x: x, y: y),.topl)
        }else{
            return (Point(x: 0, y: 0),.topr)
        }
    }

    /// 将此 Point 按照 下右方向发射
    func bottomr() -> (Point,Dir) {
        let x = self.x + m
        let y = self.y - m
        if x > n {
            return (Point(x: n, y: m-self.x),.bottoml)
        }else if x < n{
            return (Point(x: x, y: y),.topr)
        }else{
            return (Point(x: x, y: y),.topl)
        }
    }
}


/// 球 弹射的方向
///
/// - topl: 上左
/// - topr: 上右
/// - bottoml: 下左
/// - bottomr: 下右
enum Dir{
    case topl
    case topr
    case bottoml
    case bottomr
}

func run(d:Dir,point:Point){
    var res:(Point,Dir)!
    switch d {
        case .topr: res = point.topr()
        case .topl: res = point.topl()
        case .bottoml: res = point.bottoml()
        case .bottomr: res = point.bottomr()
    }
    count -= 1
    if count < 0 { return }
    print("x:",res.0.x,",y:",res.0.y)
    run(d: res.1, point: res.0)
}

let point = Point(x: 0, y: 0)
run(d: .topl, point: point)

这些就是全部的代码,包含了,次数的限制,否则无限递归,会陷入死循环。

运行上方代码结果为

x: 0 ,y: 0
x: 10 ,y: 10
x: 20 ,y: 0
x: 24 ,y: 4
x: 18 ,y: 10
x: 8 ,y: 0
x: 0 ,y: 8
x: 10 ,y: 18
x: 20 ,y: 8
x: 24 ,y: 4

结果我没有特别的演算过,主要是还是这个思路。如果有什么问题,告诉我,我会及时修改。

专栏: 杂谈
标签: 面试题目 递归