????????正好做到這里，覺(jué)得這題有點(diǎn)兒意思，也復(fù)習(xí)到以前寫(xiě)的一些算法題目，于是我就想把我的思路放在這，僅供參考。

????????先說(shuō)兩個(gè)名詞：

????????????????第一個(gè)是斐波那契數(shù)列；

????????????????第二個(gè)是字符串加法；

說(shuō)到這是不是有點(diǎn)思路了呢？

題目如下：

????????一只小蜜蜂在如下圖所示的蜂窩上爬行。它爬行時(shí)，只能從一個(gè)格爬到相鄰的大號(hào)格子中。例如，從 1 號(hào)格子可以爬到 2 號(hào)或者 3 號(hào)格子，從 2 號(hào)則可以爬到 3 號(hào)或者 4 號(hào)格子。

?

請(qǐng)問(wèn)從一個(gè)格子 a 爬到一個(gè)格子 b 一共有多少種可行的路線(xiàn)。

輸入：

分別是起始點(diǎn) a 和終止點(diǎn) b 的編號(hào)。（ a 和 b 在 1~100 之間，且 a<b 。）

輸出：

方案數(shù)量。

????????首先是斐波那契數(shù)列，不難發(fā)現(xiàn)，起點(diǎn)與終點(diǎn)兩個(gè)數(shù)字輸入后，總滿(mǎn)足他們之間的差值正好是斐波那契數(shù)列中的某一項(xiàng)，這里不過(guò)多贅述，可以自己嘗試一下。

? ? ? ? 然后是字符串加法，從實(shí)例中不難發(fā)現(xiàn)，當(dāng)輸入1和100的時(shí)候，位數(shù)達(dá)到了驚人的21位，而最大的long long類(lèi)型也只能存儲(chǔ)20位數(shù)據(jù)，這個(gè)時(shí)候就需要利用字符串進(jìn)行所謂的加法操作。

????????這里給出主要算法，一個(gè)是斐波那契數(shù)列的遞歸，一個(gè)是字符串加法的實(shí)現(xiàn)。

? ? ? ? warning：我要開(kāi)始加難度了。

一、字符串加法

? ? ? ? 說(shuō)到加法，我們不妨回憶一下小時(shí)候?qū)W的豎式加法，尾數(shù)對(duì)齊，滿(mǎn)十進(jìn)一什么的馬上就想到了吧！好了，我們要開(kāi)始實(shí)現(xiàn)了：

? ? ? ? 由于是要對(duì)字符串不斷加法，我們需要返回一個(gè)字符串的指針，方便多次調(diào)用和操作。

? ? ? ? malloc：在內(nèi)存堆區(qū)開(kāi)辟一段存儲(chǔ)空間，由于是堆區(qū)，就可以在函數(shù)結(jié)束的時(shí)候不至于被系統(tǒng)刪除，具體聲明格式可以自己搜索和學(xué)習(xí)，這里不多說(shuō)（我說(shuō)的不好，沒(méi)有其他大佬說(shuō)得好）

? ? ? ? 整體算法難度不大，可以自己調(diào)試一下，摸索一下。

char* solve(char* s, char* t ) {int lens = strlen(s);int lent = strlen(t);int lenresult = (lens > lent ? lens : lent) + 2; // 這里加二，創(chuàng)建一頭一尾多兩個(gè)位置int curresult = lenresult - 1; // 一來(lái)字符結(jié)尾的\0，二來(lái)首位可能進(jìn)一int temp, flag = 0;char* result = (char*)malloc(sizeof(char) * (lenresult));result[curresult] = 0; // 字符里面的0其實(shí)就是\0while(lens || lent){temp = flag; // 后一位的進(jìn)一，繼承到前一位計(jì)算 // 如果沒(méi)有進(jìn)一，那就是0，也是一種初始化if(lent){temp += t[--lent] - '0'; // 過(guò)渡到整數(shù)的運(yùn)算 }if(lens){temp += s[--lens] - '0';}flag = temp / 10; // 逢十進(jìn)一 temp %= 10; // 得到尾數(shù)存儲(chǔ)入字符串 result[--curresult] = temp + '0'; // 將整數(shù)返還給字符形式 ，存儲(chǔ)入字符串 }result[0] = flag + '0'; // 這里得到最高位的數(shù)字，用于繼承到字符串首位 return flag ? result : result + 1; // 如果最高位還進(jìn)一了，那就返回字符串首地址，如果沒(méi)有，返回下一位 }

?

二、斐波那契數(shù)列

? ? ? ? 由于是字符串的加法，我們所有的加法結(jié)果都存儲(chǔ)在字符串里面，那好，斐波那契數(shù)列怎么讓他循環(huán)計(jì)算值。

? ? ? ? 打表？我叭叭給你兩拳

? ? ? ? 不妨考慮這樣一個(gè)點(diǎn)，F(n+2)=F(n+1)+F(n)，如果保持前后的關(guān)系，利用一個(gè)循環(huán)，問(wèn)題就解決了，算法如下：

? ? ? ? 很精簡(jiǎn)，很優(yōu)雅。

int a=1; // 第一項(xiàng) int b=1; // 第二項(xiàng) int c=0; // 循環(huán)項(xiàng) while(n--) {c=a+b;a=b;b=c; }

到這里，字符串怎么計(jì)算，等來(lái)等去的字符串可不行。

現(xiàn)在再介紹一個(gè)函數(shù)：strcpy。

函數(shù)作用就是：復(fù)制字符串

將源所指向的 C 字符串復(fù)制到目標(biāo)所指向的數(shù)組中，包括終止空字符（并在該點(diǎn)停止）。

稍微調(diào)整一下上面循環(huán)的代碼，于是就可以得到下面這個(gè)算法

int a=0;int b=0;scanf("%d %d",&a,&b);char res[30]="1";int n=b-a-1;char arr[30]="1";char brr[30]="1";while(n--){strcpy(res,solve(arr,brr)); // solve函數(shù)返回的也是一個(gè)指針strcpy(arr,brr);strcpy(brr,res);}

?

總結(jié)：

? ? ? ? 這道題的關(guān)鍵就是字符串加法這個(gè)做法，其次的斐波那契數(shù)列只是在字符串的基礎(chǔ)上增加了一些新的花樣。

總結(jié)

以上是生活随笔為你收集整理的H8：小蜜蜂的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。