当前位置: 首页>Python>正文

漢諾塔-小青蛙

漢諾塔-小青蛙

漢諾塔問題

漢諾塔的解法在于將問題分解

可以說漢諾塔只有三步

?

?

?

?

代碼寫過程

def hanoi(n, A, B, C):""":param n: 問題規模:param A: 起始盤子:param B: 路過盤子:param C: 目標盤子:return:"""if n > 0:hanoi(n-1, A, C, B) # 打開冰箱門,把B當做目標盤子print("%s->%s" % (A, C)) # 把大象裝進冰箱,進入冰箱的大象肯定是從上向下的hanoi(n-1, B, A, C) # 關上冰箱門,B是起始盤子

代碼寫次數

def func(n):if n<=1:return nelse:return func(n-1)+1+func(n-1)

算數寫次數

總次數:2**n-1

小青蛙問題

本質:問題的拆解+累加

青蛙跳臺階算法,每次可以跳1級或兩級,請問有n級臺階,有多少種跳法

用Fib(n)表示青蛙跳上n階臺階的跳法數,青蛙一次性跳上n階臺階的跳法數1(n階跳),設定Fib(0) = 1;

當n = 1 時, 只有一種跳法,即1階跳:Fib(1) = 1;

當n = 2 時, 有兩種跳的方式,一階跳和二階跳:Fib(2) = Fib(1) + Fib(0) = 2;

當n = 3 時,有三種跳的方式,第一次跳出一階后,后面還有Fib(3-1)中跳法; 第一次跳出二階后,后面還有Fib(3-2)中跳法;第一次跳出三階后,后面還有Fib(3-3)中跳法

Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;

當n = n 時,共有n種跳的方式,第一次跳出一階后,后面還有Fib(n-1)中跳法; 第一次跳出二階后,后面還有Fib(n-2)中跳法..........................第一次跳出n階后, 后面還有 Fib(n-n)中跳法.

Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)

又因為Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

兩式相減得:Fib(n)-Fib(n-1)=Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 2

def climbStairs(n):if n==1:return 1elif n==2:return 2else:return self.climbStairs(n-1)+self.climbStairs(n-2)

使用循環

def climbStairs(n):if n==1 or n==2:return na=1;b=2;c=3for i in range(3,n+1):c=a+b;a=b;b=creturn c

  

轉載于:https://www.cnblogs.com/wwg945/p/8921779.html

https://www.nshth.com/python/338730.html
>

相关文章:

  • 國二python難嗎,python字符串(二)
  • 電腦軟件下載app,在電腦上體驗了 16 款手機 App 后,我很失望
  • elasticsearch中文文檔,Elastic安全分析新利器 —— Event Query Language (EQL) 介紹
  • 數據結構與算法python,[FreeCodeCamp筆記] Python 數據結構和算法1 二分搜索 Binary Search
  • 黑蘋果macOS系統鏡像工具,MacOS Monterey 12.2.1 (21D62) OC 0.7.8 / Cl 5144 / PE 三分區原版黑蘋果鏡像
  • 51單片機畢業設計論文,【畢業設計】基于單片機無線充電的4軸飛行器 -物聯網 嵌入式 stm32
  • 數據庫基礎知識整理,數據庫筆記整理
  • python運行不報錯又無任何結果輸出,linux 正確錯誤輸出_報告錯誤的正確方法
  • 計算機組成原理第六版課后答案,杭電計算機組成原理實驗九R-I,杭電計組實驗9-實現R-I型指令的CPU設計實驗.doc
  • python面向對象,Python零基礎速成班-第10講-Python面向對象編程(下),Property屬性、特殊方法、設計模式、鏈表應用
  • 數據庫視圖是什么,【SpringMVC】SpringMVC模型數據+視圖解析器
  • mp3格式轉換器,FFmpeg支持的音頻和視頻編解碼格式
  • 音樂學校招生要求,學校的音樂樓
  • c語言輸入兩個數輸出較大數,C語言求兩個數的較大值
  • 定義一個函數求三個數的最大值,輸入兩個整數,要求輸出其中值較大者。要求用函數求出最大值
  • MySQL學習 DAY1
  • 一個眼神一個微笑就讓人滿足,看得到的微笑
  • centos7安裝MySQL,centos7下載spark連接mysql數據庫提取數據(pyspark,Scala,python獨立執行)
  • node.js開發,從零開始nodejs系列文章-nodejs到底能干什么
  • python控制軟件自動化,Python實現網站自動登錄---傻瓜教程
  • get all of,resent = msg.get_all('Resent-Date') AttributeError: 'str' object h
  • opencv人體動作識別,torchvision使用keypoint rcnn 進行人體關鍵點定位
  • 深度卷積神經網絡原理與實踐,卷積神經網絡resent網絡實踐
  • 服務器,win服務器系統路由器,Windows server 2012 之路由功能
  • 小青蛙走迷宮的問題
  • 漢諾塔-小青蛙
  • 小青蛙oracle跟蹤,在小青蛙TOAD中用oracle語句寫
  • 音頻頻譜分析儀安卓版,[Android]自定義繪制一個簡易的音頻條形圖,附上對MP3音頻波形數據的采集與展現
  • 連乘符號∏的運算法則,∏這個是什么符號?
  • 用例失敗jenkins卻構建成功,jenkins 構建異常_jenkins構建失敗的原因是什么?