kitty猫的基因编码

69 阅读 0 评论 46 点赞

我是靠谱客的博主爱听歌棉花糖，最近开发中收集的这篇文章主要介绍kitty猫的基因编码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 }

转载于:https://www.cnblogs.com/moupeng/archive/2010/10/08/1845521.html