老歌了~

宅男開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

我還是要開局選拳法....

另外此題牛頓迭代解法,略...