Ruby解题分享--Sqrt(x),二分搜寻演算法。

老歌了~

宅男开YouTube来看,永远不缺手游广告...

最近有个广告台词,开局一定要选拳法,如果开局选心法,血多但是攻击力不够,开局如果选拳法,杀伤力高,拓荒才会快。

如果拳法代表各语言自己的特殊语法,心法代表各种逻辑或是数学公式,那还真的有拳法较实用的感觉,尤其对新手而言。

但高手最後常常还是比拼内力深厚,所以偶尔练练心法吧....
~~如果没跟李寻欢一样帅,只练飞刀也不会是主角的...~~

Sqrt(x)

题目连结:https://leetcode.com/problems/sqrtx/
题目:求平方根整数部分。

整理

def my_sqrt(x)
end

p my_sqrt(4) #=> 2
p my_sqrt(8) #=> 2

提示部分希望我们不要用函式库等特殊语法。

所以跟以下解法说掰掰

def my_sqrt(x)
  (x ** 0.5).floor
  # Math.sqrt(x).floor
end

另外迭代也不行,因为考虑到所花时间(资源),程序码出现迭代处理的都会无法运行。
所以下面解法也掰掰

def my_sqrt(x)
  (1..x).each do |num|
    return num if num * num == x
    return num - 1 if num * num > x
  end
end
#数字大一点就会发现答案出来明显慢了,虽然大家现在电脑都很快....

二分搜寻演算法

有请wiki帮忙解释....
好的,即使我很菜,我也自豪地认为有人跟我一样看不懂 XD
那我们看简单一点的二分法

我们就以,指的是将一个整体事物分割成两部分。也即是说，这两部分必须是互补事件，即所有事物必须属於双方中的一方，且互斥，即没有事物可以同时属於双方。这段来解这题。

先来看一个很古老的游戏,猜数字。
猜1~100其中一个数字,正确答案一定是 1 < n < 100, 1与100可以想像成边界。
1..100等於整个事件,比1大比100小就是那互补事件,不可能大於1又大於100。
假设 ans == 39, 我们猜num = 50,那50 > 39又 50 < 100,50就取代大的边界成为了 1 < n < 50。
我们再猜20, 20 < 39, 1 < 20,20取代小边界成为了 20 < n < 50。
到最後,n其实就是两个边界的中间值。38 < 39 < 40。

边界部分有人用上下或左右来称呼,就看个人吧。

def my_sqrt(x)
  #需要左边界
  #需要右边界
  #设定回圈起始条件
  #设定回圈做啥
  #设定回圈终止条件
end

def my_sqrt(x)
  start_num = 0 #左边
  end_num = x  #右边
  
  #设定回圈起始条件
  while start_num <= end_num  #<= 是因为考虑 x == 0
    ans = (end_num + start_num)/2 #求中间值
    if ans**2 <= x && x < (ans+1)**2  #以8举例 2*2 < 8 , (2+1)*(2+1) > 8
      return ans
    elsif x < ans**2  #这边就是找不到答案 改边界值
      end_num = ans - 1
    else
      start_num = ans + 1
    end
  end
end

不过求二分法中间值,程序编码中会有准确度更高的公式,l == 左, r == 右。

MID = l + (r - l)/2

我们将公式代入,至於公式为何长这样,准确在哪,菜鸟的我就不献丑了。

def my_sqrt(x)
  start_num = 0 
  end_num = x  
  
  while start_num <= end_num  
    ans = start_num + (end_num - start_num)/2 
    if ans**2 <= x && x < (ans+1)**2  
      return ans
    elsif x < ans**2  
      end_num = ans - 1
    else
      start_num = ans + 1
    end
  end
end