題目描述

小可可選修了基礎生物基因學。教授告訴大家 Super Samuel 星球上 Kitty貓的基因的長度都是 2 的正整數次冪 )， 全是由兩種不同的基因單元組成的。 這兩種不同的基因單元分別記成 0 和 1，于是 Kitty 貓基因可以寫成一個 01 串表達式 。

為了便于分析和降低數據存儲量，教授發明了 ABC 編碼規則。該編碼規則是不斷地按照

對 Kitty 貓基因 01 串表達式 進行改寫， 直至最終被改寫成只含有字符 “ A”、“ B”、“ C”的符號串。

輸入格式

文件中以一行的形式存放了一個 Kitty 貓基因的 01 串表達式。

輸出格式

以一行的形式輸出這個 Kitty 貓基因的 ABC 編碼。

輸入輸出樣例

輸入 #1

00

輸出 #1

A

輸入 #2

01001011

輸出 #2

CCCABACCBAB

說明/提示

給出的01字符串長度Len\leq 256Len≤256

思路

?這里A和B相當于basecase(基線情況）

最下面一條式子是遞歸關系式T(s) = ‘C’ + T(s1) + T(s2) //也是T自己調用自己

#include <iostream> #include <string> using namespace std;void T(string s, int n); bool isA(string s); bool isB(string s);int main() {string s;cin >> s;T(s, s.length());return 0; }void T(string s, int n) {if (isA(s))//判斷是否都是0{cout << 'A';return;}else if (isB(s))//判斷是否都是1{cout << 'B';return;}else{cout << 'C';//遞歸關系式里的Cstring front = s.substr(0, n / 2);//取出前面一半string last = s.substr(n / 2);//后面一半T(front, n / 2);//遞歸關系式里的第二項T(last, n / 2);//遞歸關系里的第三項} }bool isA(string s) {for (int i = 0; i < s.length(); i++){if (s[i] != '0')return false;}return true; }bool isB(string s) {for (int i = 0; i < s.length(); i++){if (s[i] != '1')return false;}return true; }

總結

以上是生活随笔為你收集整理的P2562 [AHOI2002]Kitty猫基因编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。