Python編程作為現如今應用廣泛的編程語言之一,大量企業和機構已將其用于IT領域中。針對Python開發人員,做Python題目是一個必不可少的訓練方式。下面,讓我們一起來看一道Python真題以及答案。
題目描述: 一只青蛙想跳上一個高度為h的臺階。比如,該青蛙此時處于地面上,即高度為0。每次跳躍的步數都有限制,這個青蛙每次最多可以跳step步。那么,青蛙跳上這個位置最少需要跳躍多少次? 輸入格式: 一行數據,包括兩個整數,分別代表h和step 輸出格式: 輸出一個整數,表示青蛙跳上這個臺階的最少跳躍次數 樣例: 輸入: 10 2 輸出: 6 解釋: 1、每次跳躍最多可以跳step步,所以每次只能跳1步或2步; 2、1個最短路徑是:2 + 2 + 2 + 2 + 1 + 1 = 10,共跳了6次; 3、另一個最短路徑是:1 + 1 + 1 + 1 + 1 + 5 = 10,共跳了6次。 解題思路: 假設n為跳躍次數,那么在n步時,青蛙可能在臺階的1、2、3…n層上。對于第i層,該層所有跳躍步驟的可能性由1+2+…+step獲得,即F(i-1)+F(i-2)+…+F(i-step)。所以,青蛙跳躍至第n個臺階的所有可能性可以由以下公式計算得出:F(n)=F(n-1)+F(n-2)+…+F(n-step)。 Python代碼如下:
import sys def jumpFrog(h, step): if h == 1: return 1 if h == 2: return 2 if h == 0: return 0 res = [0] * (h + 1) res[1] = 1 res[2] = 2 for i in range(3, h + 1): min_val = sys.maxsize lst = [j for j in range(1, step + 1) if i >= j] for l in lst: tmp_res = res[i - l] + 1 if tmp_res< min_val: min_val = tmp_res res[i] = min_val return res[h] if __name__ == '__main__': h, step = map(int, input().split()) print(jumpFrog(h, step))
我們可以借助題目的思路以及Python的性質來完成該題。通過以上代碼,你可以練習Python語言,鞏固Python基礎,并深入理解動態規劃的思想。
上一篇css圖片和文字混排