iT邦幫忙

1

Ruby解題分享--Climbing Stairs

  • 分享至 

  • xImage
  •  

當開始可以發現韓國女團,每個人長得都不一樣時,就代表你長大了...
Yes


Climbing Stairs

不養羊或兔子之後,開始爬樓梯....

很多語言都會用到斐波那契數,不認識沒關係,我們等等用觀察法來解。
學程式語言,數學不用好,但學程式後,數學可能會進步...

遞迴(遞歸)

wiki

有一天主持人抽獎,喊了:[第5排那位紅色衣服的阿宅,你得獎了]。
我剛好是穿紅衣也是阿宅,但我不知道我第幾排,所以我向我前面的正妹問,請問她是第幾排,她也不知道,所以她向他前面比我還肥宅的肥宅問他是第幾排,一直問到了第一排。

{我: "不知道", 正妹: "不知道", 比我肥宅: "不知道", 路人一: "不知道", 路人二: "第一排"}

到了第一排的路人二號,終於知道自己是第一排的觀眾,但他很酷的的回答路人一,我只知道我在第一排。
好險路人二到我沒笨到不會加法,於是從路人二開始回頭看。

{
 路人二: "我是第一排,那你是我下一位",
 路人一: "前面一,所以我是二,後面的我是二",
 比我肥宅: "前面是二,所以我是三,後面的我是三",
 正妹: "前面是三,所以我是四,後面的我是四",
 我: "前面是四,所以我是五,後面的我是五",
}
#找到自己位置的方法,就是知道前面的人的位置。

以上便是遞迴最簡單的想法。

開始觀察

方法只有兩種,一步或兩步。

#一階時 method一種
n = 1 
1. 1 step

#二階時 method二種
n = 2 
#爬法
1. 1 step + 1 step
2. 2 steps

#三階時 method三種
n = 3
1. 1 step + 1 step + 1 step
2. 2 steps + 1 step
3. 1 step + 2 steps

#四階時 method五種
n = 4
1. 1 step + 1 step + 1 step + 1 step
2. 2 seep + 1 step + 1 step
3. 1 setp + 2 setp + 1 step
4. 1 step + 1 step + 2 setp
5. 2 setp + 2 setp

# 這邊不是觀察算式,而是發現到最後方法只有最後一步是1的方法,加上最後一步是2的方法,等於總方法數。
# 最後一步是1時 == n - 1 , 最後一步是2時 == n - 2。
# 另外整理答案 hash = {"1": 1, "2": 2, "3": 3, "4": 5}
hash[1] = 1 
hash[2] = 2
hash[3] = 4 
hash[4] = 5 #從三四階時開始符合 n = (n - 1) + (n - 2)
# 養動物達人公式就出現了 f(x) = f(x-1) + f(x-2)

解答

def climb_stairs(n)
  methods = {}
  methods[1] = 1
  methods[2] = 2
  3.upto(n) do |n|
    methods[n] = methods[n - 2] + methods[n - 1]
  end
  methods[n]
end

另外可用default_proc = -> 語法

def climb_stairs(n)
    fibona_hash = { 0 => 0, 1 => 1, 2 => 2, 3 => 3 }  
    fibona_hash.default_proc = ->(hash, n) {hash[n] = hash[n-1] + hash[n-2]} 
    fibona_hash[n]
end
# "->", lambda。
# 嗯,我沒分享過block,proc及lambda....

請先看https://ruby-doc.org/core-3.0.2/Hash.html#method-i-default_proc


再進化一點...

def climb_stairs(n)
  return 0 if n == 0
  a, b = 0, 1
  n.times { a, b = b, b + a }
  b
end

補充:

2.7.3 :013 > arr = [1, 2, 3]
 => [1, 2, 3] 
2.7.3 :014 > arr[0] = arr[1]
 => 2 
2.7.3 :015 > arr
 => [2, 2, 3] 
2.7.3 :016 > arr = [1, 2, 3]
 => [1, 2, 3] 
2.7.3 :017 > arr[0] ,arr[1] = arr[1], arr[0]
 => [2, 1] 
2.7.3 :018 > arr
 => [2, 1, 3] 

雖然就是費波納,但是觀察爬樓梯爬高點就會發現了。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言