当前位置: 首页>编程笔记>正文

小青蛙走臺階問題

小青蛙走臺階問題

小青蛙走臺階問題

題目說明

  • 小青蛙每次可以走1步,也可以走兩步。問,當小青蛙走到n層臺階的時候,一共有多少種走法!

分析

先從最簡單的開始分析。

  • 當n=1的時候;很明顯,只有一種走法!
  • 當n=2的時候;每次走一步有一種走法,每次走兩步也只有一種走法!

畫圖分析

在這里插入圖片描述

  • 那么當n>2的時候呢?

    • 不妨以n=3來分析,看看該如何思考此類問題!

    • 可以采用逆向分析的方法來求解此類問題。

畫圖分析

在這里插入圖片描述

  • 觸類旁通,n=4,n=5…都是相似的道理。

遞歸求解

  • 其實上述的小青蛙走臺階的問題本質上其實還是一個斐波那契數列的問題!我們可以通過遞歸思想來達到解題的目的!

代碼演示

#include <stdio.h>int Fib(int n)
{if (n <= 2){return n;}else{return Fib(n - 1) + Fib(n - 2);}
}int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);return 0;
}
  • 在博主遞歸思想一篇中提到過,當n的值比較大的時候,一些較小的數重復計算過很多次,使得代碼的執行效率不夠高。

代碼演示

#include <stdio.h>int count = 0;int Fib(int n)
{if (n == 1){count++;}if (n <= 2){return n;}else{return Fib(n - 1) + Fib(n - 2);}
}int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n%d", ret, count);return 0;
}

運行截圖

在這里插入圖片描述

  • 可以看出的是,當求走到30級臺階有多少種走法的時候,僅僅是求走到一級臺階的走法就求了高達317811種。故遞歸思想知只是作為一種解決問題的方法,并不是唯一的方法!

迭代求解

對計算機特定程序中需要反復執行的子程序*(一組指令),進行一次重復,即重復執行程序中的循環,直到滿足某條件為止,亦稱為迭代。

  • 這里的思路是:求某一項時(這里所指的是大于等于第3項的某項),就從第1項和第二項開始不斷地往后面加。

畫圖演示

在這里插入圖片描述

代碼演示

#include <stdio.h>int Fib(int n)
{int tmp = n;//第一項int a = 1;//第二項int b = 2; //最后要求的那一項int c = 0;while (tmp > 2){c = a + b;a = b;b = c;tmp--;}//判斷輸出if (n == 1){return a;}else if (n == 2){return b;}else {return c;}
}int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);return 0;
}

更多遞歸題型,請參考博主@遞歸思想。

https://www.nshth.com/bcbj/338727.html
>

相关文章:

  • pdf翻譯網站,1 Trillion Dollar Refund – How To Spoof PDF Signatures——欺騙PDF簽名
  • 如何創建一個抽象類,創建具體的產品,并繼承產品抽象類
  • 主從庫理論知識-主從同步如何實現?
  • Tomcat環境變量配置,Mybatis的配置文件參數詳解
  • I Am You,POJ 3130 How I Mathematician Wonder What You Are! 半平面交
  • 要學vue需要學什么基礎知識,第一章 Vue基礎入門
  • win7下安裝win10,win10下安裝Ubuntu18.10雙系統
  • vmplayer怎么使用烏邦圖,烏邦圖環境安裝
  • 計算機專業要不要考研——寫的很棒
  • redisson看門狗原理,記錄一次redis漏洞攻擊
  • 任意波形發生器,基于單片機信號波形發生器系統設計-畢設課設
  • 嵌入式驅動,嵌入式Linux驅動大全問世,十年磨一劍,視頻!服務!新老客戶都有大折扣!
  • socket連接器v2下載,Netty(一)基礎socketchannel,Buffer,selector黏包 半包解決 實戰
  • 大一c語言程序設計筆記,吉林大學2013級大一下學期程序設計作業:同學通訊錄系統
  • 暑期小學生計算機培訓班,青島小學生學習編程暑假
  • 熊貓毛小喵喵去哪里了,小西貝、何小喵看熊貓之觀察者設計模式
  • 如何用c語言比較兩個數的大小,如何用C語言求兩個數的較大值
  • 輾轉相除法求最小公倍數的方法,更相減損術--最大公約數
  • 輾轉相除法求最小公倍數的方法,如何求出兩個整數的最大公約數
  • 李新義的書畫藝術,中國現代書畫家——譚奇中、李義象、高俊鵬等
  • 海底撈張勇名言,致張勇先生一封信:海底撈的“七宗罪”!
  • WPF學習(12)動畫
  • ui自動化測試工具,移動端UI自動化之appium的使用(二)
  • 爬蟲網站,Search For Free —— 新聞爬蟲及爬取結果的查詢網站
  • tenda騰達無線設置,騰達F6路由器無線中繼功能設置
  • 斐波那契數列、小青蛙跳臺階
  • OJ每日一練——小青蛙上臺階
  • 小青蛙貝葉斯
  • 小青蛙走臺階問題
  • MySQL數據庫下載,NAVICAT FOR MYSQL存儲過程