kitty猫的基因编码

时间：2010-10-08 来源：Arthur Peng

Problem

kitty的基因编码如下定义： kitty的基因由一串长度2^k（k<=8)的01序列构成，为了方便研究，需要把,01序列转换为ABC编码。用T（s)来表示01序列s的ABC编码 T(s)＝‘A'（当S全由'0'组成） T(s)＝‘B'（当s全由'1'组成） T(s)＝‘C'+T（s1)+T（s2) s1,s2为把s等分为2个长度相等的子串比如 T（'00')='A' T('00001111')='CAB'

Input

一行，长度为2^k，为kitty猫的01基因编码，有多个数据

Output

一行，由ABC构成的ABC编码

Sample Input

01001011

Sample Output

CCCABACCBAB

解题思路：其实就是一个二叉树的中序遍历问题。可以用递归的方法来做。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 vector<char>  dna;
 5 
 6  char is_A_B_C(string tep)
 7 {
 8     if(tep.find_first_not_of("0")==string::npos)
 9     {
10         return 'A';
11     }
12     else if(tep.find_first_not_of("1")==string::npos)
13     {
14         return 'B';
15     }
16     else
17     {
18         return 'C';
19     }
20 }
21 
22  void sort_dna(string s1)
23 {
24     char test=is_A_B_C(s1);
25     dna.push_back(test);
26     if(test=='C')
27     {
28         string ss1(s1.begin(),s1.begin()+s1.size()/2);
29         sort_dna(ss1);
30         string ss2(s1,s1.size()/2);
31         sort_dna(ss2);
32     }
33 }
34 
35 int main()
36 {
37     string kitty_dna;
38     cin>>kitty_dna;
39     sort_dna(kitty_dna);
40     for(vector<char>::iteratorit=dna.begin();it!=dna.end();it++)
41     {
42         cout<<*it;
43     }
44     cout<<endl;
45 }