那曲檬骨新材料有限公司

您好,歡迎來電子發燒友網! ,新用戶?[免費注冊]

您的位置:電子發燒友網>源碼下載>通訊/手機編程>

Swift算法實例分析之動態規劃

大小:0.5 MB 人氣: 2017-09-25 需要積分:1

  今天要講的動態規劃,其面對的問題通常是無法一蹴而就,需要把復雜的問題分解成簡單具體的小問題,然后通過求解簡單問題,去推出復雜問題的最終解。

  形象的理解就是為了推倒一系列紙牌中的第100張紙牌,那么我們就要先推倒第1張,再依靠多米諾骨牌效應,去推倒第100張。

  實例講解

  斐波拉契數列是這樣一個數列:1, 1, 2, 3, 5, 8, 。。. 除了第一個和第二個數字為1以外,其他數字都為之前兩個數字之和。現在要求第100個數字是多少。

  這道題目乍一看是一個數學題,那么要求第100個數字,很簡單,一個個數字算下去就是了。假設F(n)表示第n個斐波拉契數列的數字,那么我們易得公式F(n) = F(n - 1) + F(n - 2),n 》= 2,下面就是體力活。當然這道題轉化成代碼也不是很難,最粗暴的解法如下:

  func Fib() -》 Int {

  var prev = 0

  var curr = 1

  for _ in 1 。。《 100 {

  var temp = curr

  curr = prev + curr

  prev = temp

  }

  return curr

  }

  用動態規劃怎么寫呢?首先要明白動態規劃有以下幾個專有名詞:

  1. 初始狀態,即此問題的最簡單子問題的解。在斐波拉契數列里,最簡單的問題是,一開始給定的第一個數和第二個數是幾?自然我們可以得出是1

  2. 狀態轉移方程,即第n個問題的解和之前的 n - m 個問題解的關系。在這道題目里,我們已經有了狀態轉移方程F(n) = F(n - 1) + F(n - 2)

  所以這題要求F(100),那我們只要知道F(99)和F(98)就行了;想知道F(99),我們只要知道F(98)和F(97)就行了;想要知道F(98),我們需要知道F(97)和F(96)。。。,以此類推,我們最后只要知道F(2)和F(1)的值,就可以推出F(100)。而F(2)和F(1)正是我們所謂的初始狀態,即 F(2) = 1,F(1) =1。所以代碼如下:

  func Fib(n: Int) -》 Int {

  // 定義初始狀態

  guard n 》 0 else {

  return 0

  }

  if n == 1 || n == 2 {

  return 1

  }

  // 調用狀態轉移方程

  return Fib(n - 1) + Fib(n - 2)

  }

  print(Fib(100))

非常好我支持^.^

(0) 0%

不好我反對

(0) 0%

      發表評論

      用戶評論
      評價:好評中評差評

      發表評論,獲取積分! 請遵守相關規定!

      ?
      实战百家乐官网的玩法技巧和规则 | 真人游戏网站| 百家乐庄闲客户端| 网上百家乐官网必赢玩| 百家乐官网规则博彩正网| 娱乐场游戏| 大发888娱乐充值| 百家乐必赢法软件| 棋牌百家乐官网有稳赚的方法吗| 百家乐官网交流群号| 德州扑克过牌| 金龍百家乐的玩法技巧和规则| 有百家乐的游戏平台| 百家乐玩法的技巧| 真人百家乐官网最高赌注| 百家乐官网兑换棋牌| 娱乐城简介| 百家乐德州| 百家乐庄闲和收益| 至尊百家乐网| 视频百家乐试玩| 百家乐官网平注法规则| 网上百家乐官网娱乐平台| 百家乐官网的必胜方法| 日博365| 狮威国际娱乐| 葡京娱乐城姚记| 银河国际娱乐城| 永利| 崇礼县| 百家乐官网怎么玩了| 百家乐官网连输的时候| 新葡京百家乐官网现金网| 百家乐官网赢的方法| 尊龙体育| 888真人赌博| 利来娱乐网| 澳门足球博彩| 兴城市| 金盈会百家乐官网现金网| 百家乐官网秘诀|