欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C 語言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問題

 更新時(shí)間:2021年09月14日 17:25:23   作者:吞吞吐吐大魔王  
這篇文章我們九里講講C 語言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問題,感興趣的小伙伴可以參考下面文章的具體內(nèi)容

一、青蛙跳臺(tái)階

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法

思路

遇見題目我們可以在紙上先動(dòng)手畫畫,把最簡(jiǎn)單的幾種方式列出來,作比較,找規(guī)律。


分析

按照上面表格可以從跳法次數(shù),過程,或者兩者結(jié)合找規(guī)律

1. 從跳法次數(shù)分析

  • 觀察表格,可以知道從n>=3時(shí),第n個(gè)數(shù)就是前兩個(gè)數(shù)的和(與斐波那契數(shù)列一樣)
  • 我們自己推論,當(dāng)臺(tái)階數(shù)為n時(shí),設(shè)跳法有f(n)次,如果青蛙先跳1階,則剩下的臺(tái)階數(shù)為n-1,即剩余跳法有f(n-1)次;如果青蛙先跳2階,則剩下的臺(tái)階數(shù)為n-2,即剩余跳法有f(n-2)次。
  • 故跳法次數(shù)f(n)=f(n-1)+f(n-2),因?yàn)榈忍?hào)右邊有兩個(gè)值,故當(dāng)n=1,n=2時(shí)為最后的特殊限制條件
  • 下面代碼為遞歸求法,如果想用非遞歸,可以將遞歸通項(xiàng)改成循環(huán)

代碼1(遞歸)

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

2. 從過程分析

  • 觀察表格,可以知道,跳n階臺(tái)階,跳兩階臺(tái)階次數(shù)可以為0到n/2次,而每一次跳兩階臺(tái)階的順序也是不定的??梢酝ㄟ^計(jì)數(shù)原理的組合數(shù)C(n,m),表示從n個(gè)數(shù)中選m個(gè)數(shù)排列。n表示每次需要跳的次數(shù),m表示一次跳兩階的次數(shù)
  • 組合數(shù)C(n,m),可以由n!/(m!*(n-m)!)求得
  • 下面代碼為非遞歸求法,如果想要寫成遞歸,可以根據(jù)循環(huán)修改

代碼2(非遞歸)

#include <stdio.h>
int fac(int m)
{
 int i = 0;
 int count = 1;
 for (i = 1; i <= m; i++)
 {
  count *= i;
 }
 return count;
}
int jump(int n)
{
 int i = 0;      //i為跳兩階臺(tái)階的次數(shù)
 int sum = 0;     //sum為計(jì)算跳法
 for (i = 0; i <= n / 2; i++)
 {
  int a = 0;
  a = n - i * 2 + i;   //a為跳到n階臺(tái)階跳的次數(shù) 
  sum += fac(a) / (fac(i)*fac(a - i));
 }
 return sum;
}
int main()
{
 int n;
 scanf("%d", &n);
 int ret = jump(n);
 printf("%d", ret);
 return 0;
}

二、青蛙跳臺(tái)階變式1

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階…也可以跳n級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法

分析

  • 根據(jù)原題推論,當(dāng)臺(tái)階數(shù)為n時(shí),設(shè)跳法有f(n)次,如果青蛙先跳1階,則剩下的臺(tái)階數(shù)為n-1,即剩余跳法有f(n-1)次;如果青蛙先跳2階,則剩下的臺(tái)階數(shù)為n-2,即剩余跳法有f(n-2)次。
  • 那么當(dāng)青蛙跳3階臺(tái)階,則剩下的臺(tái)階數(shù)為n-3,即剩余跳法有f(n-3)次…當(dāng)青蛙跳n階臺(tái)階,則剩下的臺(tái)階數(shù)為n-n,即剩余跳法有f(n-n)次
  • 故跳法次數(shù)f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
  • 由推論可得f(n-1)=f(n-2)+f(n-3)…+f(n-n),將其代入上面式子
  • 故跳法次數(shù)為f(n)=2*f(n-1),因?yàn)榈忍?hào)右邊只有一個(gè)值,故n=1為最后的特殊限制條件

代碼3(遞歸)

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

三、青蛙跳臺(tái)階變式2

題目

一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階…也可以跳m級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法(m<=n)

分析

  • 根據(jù)變式1推論得f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
  • 而這里最多一次只能跳m階,故f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-m)
  • 由推論得f(n-1)=f(n-2)+f(n-3)…+f(n-m)+f(n-m-1),代入上面式子
  • 故跳法次數(shù)為f(n)=2*f(n-1)-f(n-m-1)
  • 因?yàn)橥ㄟ^遞歸n的值在減少,當(dāng)n<m時(shí),其實(shí)最多就只能跳n階,與變式1就是一樣的問題了

代碼4(遞歸)

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

四、漢諾塔問題(求步數(shù))

題目

有A,B,C三個(gè)柱子,A柱子上從上到下,從小到大排列著n個(gè)圓盤?,F(xiàn)要求將A柱子上的n個(gè)圓盤全部移動(dòng)到C柱子上,依然按照從上到下,從小到大的順序排列。且對(duì)移動(dòng)過程要求如下:

a)一次只能移動(dòng)一個(gè)盤子。

b)移動(dòng)過程中大盤子不允許出現(xiàn)在小盤子上方。

問:總共需要移動(dòng)的步數(shù)是多少?

思路

因?yàn)榍蟮氖遣綌?shù),我們可以通過找前面幾組數(shù)據(jù),觀察是否有什么規(guī)律

分析

  • 通過表格觀察,可以知道盤子數(shù)為n時(shí),步數(shù)為20+21+…+2n-1,即2n-1
  • 我們可以通過下面這張圖片來推論:

  • 假設(shè)盤子數(shù)量為n,通過化繁為簡(jiǎn)思想,我們可以把盤子分成兩個(gè)部分。上面n-1個(gè)盤子,和最下面一個(gè)盤子。移動(dòng)步驟如下:
  1. 將最上面的n-1個(gè)盤子移動(dòng)到B柱上
  2. 將最下面的盤子移動(dòng)到C柱上
  3. 再將B柱上的n-1個(gè)盤子移動(dòng)到C柱上
  • 問題轉(zhuǎn)化成如何移動(dòng)最上面n-1個(gè)盤子。按照上面的思路解決n-1個(gè)盤子移動(dòng)的問題。
  • 假設(shè)移動(dòng)n個(gè)盤子需要的步數(shù)為f(n),則移動(dòng)n-1個(gè)盤子需要f(n-1)步。
  • 故移動(dòng)步數(shù)為f(n)=f(n-1)+1+f(n-1),即f(n)=2*f(n-1)+1
  • 通過等比數(shù)列變形又可以得到f(n)=2n-1

代碼5(非遞歸)

#include <stdio.h>
#include <math.h>
int main()
{
 int n;
 scanf("%d", &n);
 int count =0;
    count=(int)pow(2,n)-1;
 printf("%d", count);
 return 0;
}

代碼6(遞歸)

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

五、漢諾塔問題(求移動(dòng)過程)

題目

有A,B,C三個(gè)柱子,A柱子上從上到下,從小到大排列著n個(gè)圓盤?,F(xiàn)要求將A柱子上的n個(gè)圓盤全部移動(dòng)到C柱子上,依然按照從上到下,從小到大的順序排列。且對(duì)移動(dòng)過程要求如下:

a)一次只能移動(dòng)一個(gè)盤子。

b)移動(dòng)過程中大盤子不允許出現(xiàn)在小盤子上方。

問:打印移動(dòng)的方案 (例如, 移動(dòng)A柱最上面的圓盤到C柱, 則輸出"A -> C")

思路

因?yàn)榍蟮氖且苿?dòng)方案,所以我們可以將前幾組數(shù)據(jù)列出來,結(jié)合遞歸化簡(jiǎn)為繁的思想找共性和非共性


分析

  • 通過觀察得到:除了n=1,n>1時(shí),都是先將A柱上面n-1個(gè)盤子拿到B柱(粗字體為其過程),再將A柱最下面盤子拿到C柱。此時(shí)A柱變成輔助柱,再將B柱上的盤子放到C柱
  • 故將A柱最下面盤子移到C柱為中間過程
  • 上一步為將初始柱(A柱)上面n-1個(gè)盤子借助輔助柱(C柱)移到目標(biāo)柱(B柱)【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔,將A柱上的盤子移動(dòng)到B柱】
  • 下一步為將初始柱(B柱)上面n-1個(gè)盤子借助輔助柱(A柱)移到目標(biāo)柱(C柱)【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔,將B柱上的盤子移動(dòng)到C柱】
  • 而上一步,中間過程,下一布就是遞歸的核心思想
  • 而當(dāng)n=1時(shí),盤子數(shù)只有一個(gè),我們將其直接放到目標(biāo)柱即可(其為最終的限制條件)
  • 初始柱,輔助柱,目標(biāo)柱,其實(shí)就是把該步驟的移動(dòng)過程當(dāng)作一個(gè)單獨(dú)的漢諾塔問題,需要移動(dòng)盤子現(xiàn)在所在的位置為初始柱,要將其放到的位置就是目標(biāo)柱

代碼7(遞歸)

#include <stdio.h>
void hanio(int n, char x, char y, char z)
{
 if (n == 1)
  printf("%c->%c\n",x,z);  //當(dāng)盤子只剩一個(gè)時(shí),直接打印初始柱移動(dòng)到目標(biāo)柱的過程
 else
 {
  hanio(n - 1, x, z, y);  //將n-1個(gè)盤子從起始柱放到目標(biāo)柱(第一次A->B,第二次B->A,后面往復(fù))
        
  printf("%c->%c\n", x, z); //打印初始柱移動(dòng)到目標(biāo)柱的過程
        
  hanio(n - 1, y, x, z);  //將n-1個(gè)盤子從起始柱放到目標(biāo)柱(第一次B->C,第二次C->B,后面往復(fù))
 }
}
int main()
{
 int n;
 scanf("%d", &n);
 hanio(n,'A','B','C');
 return 0;
}

結(jié)語:

到此這篇關(guān)于C 語言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問題的文章就介紹到這了,更多相關(guān)C 語言實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 利用Matlab繪制一款專屬進(jìn)度條

    利用Matlab繪制一款專屬進(jìn)度條

    MATLAB自帶的進(jìn)度條是很簡(jiǎn)單的,這樣的進(jìn)度條顯得冷冰冰的。因此,本文將用Matlab來DIY一款專屬的進(jìn)度條,感興趣的小伙伴可以了解一下
    2022-02-02
  • 詳解C語言編程中預(yù)處理器的用法

    詳解C語言編程中預(yù)處理器的用法

    這篇文章主要介紹了C語言編程中預(yù)處理器的用法,包括介紹了C和C++混合編程的情況,需要的朋友可以參考下
    2016-02-02
  • C語言 OutputDebugString與格式化輸出函數(shù)OutputDebugPrintf案例詳解

    C語言 OutputDebugString與格式化輸出函數(shù)OutputDebugPrintf案例詳解

    這篇文章主要介紹了C語言 OutputDebugString與格式化輸出函數(shù)OutputDebugPrintf案例詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • 淺談C結(jié)構(gòu)和C++結(jié)構(gòu)之間的區(qū)別

    淺談C結(jié)構(gòu)和C++結(jié)構(gòu)之間的區(qū)別

    這篇文章主要介紹了淺談C結(jié)構(gòu)和C++結(jié)構(gòu)之間的區(qū)別,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-04-04
  • C語言代碼實(shí)現(xiàn)簡(jiǎn)易三子棋游戲

    C語言代碼實(shí)現(xiàn)簡(jiǎn)易三子棋游戲

    這篇文章主要為大家詳細(xì)介紹了C語言代碼實(shí)現(xiàn)簡(jiǎn)易三子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • 關(guān)于win32 gettimeofday替代方案

    關(guān)于win32 gettimeofday替代方案

    下面小編就為大家?guī)硪黄P(guān)于win32 gettimeofday替代方案。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2016-12-12
  • 一文搞懂C++多態(tài)的用法

    一文搞懂C++多態(tài)的用法

    C++多態(tài)是在繼承的基礎(chǔ)上實(shí)現(xiàn)的,了解多態(tài)之前我們需要掌握一定的C++繼承的知識(shí),本文將介紹C++中多態(tài)的概念,構(gòu)成條件以及用法,感興趣的可以學(xué)習(xí)一下
    2022-04-04
  • C語言結(jié)構(gòu)體鏈表和指針實(shí)現(xiàn)學(xué)生管理系統(tǒng)

    C語言結(jié)構(gòu)體鏈表和指針實(shí)現(xiàn)學(xué)生管理系統(tǒng)

    這篇文章主要介紹了C語言結(jié)構(gòu)體鏈表和指針實(shí)現(xiàn)學(xué)生管理系統(tǒng),包括學(xué)生檔案管理子系統(tǒng)和學(xué)生成績(jī)管理子系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • C++11/14 線程的創(chuàng)建與分離的實(shí)現(xiàn)

    C++11/14 線程的創(chuàng)建與分離的實(shí)現(xiàn)

    這篇文章主要介紹了C++11/14 線程的創(chuàng)建與分離的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-01-01
  • c_str()的用法詳細(xì)解析

    c_str()的用法詳細(xì)解析

    c_str()就是把string類對(duì)象轉(zhuǎn)換成和c兼容的char *類型。這是為了與c語言兼容,在c語言中沒有string類型,故必須通過string類對(duì)象的成員函數(shù)c_str()把string 對(duì)象轉(zhuǎn)換成c中的字符串樣式
    2013-09-09

最新評(píng)論