使用递归确定有效的DNA序列

Question

我被这个问题困住了很长时间，我需要解决一个学校的作业，一个多星期了，我仍然不知道该怎么做。DNA构成了我们基因序列的基石。DNA由两条核苷酸链组成。每个核苷酸是四种可能性之一:

A - Adenine 
T - Thymine
C - Cytosine
G - Guanine 

在DNA序列中结合时，A和T可以结合，C和G可以结合。其他组合无效。对于这个赋值，您将要求用户输入两个序列，然后通过比较序列中的相应位置返回有效对的数量。换句话说，您将查看每个文件中的第一个字符。如果这是A &T或C;G，它是一对有效的。然后，你将转向第二对。您可以忽略任何无效字符，但不应假设序列的长度相等。

我不知道如何写一个递归语句来帮助这个赋值。我不确定我将如何去寻找这个问题的基本情况，并使用递归返回到基本情况的函数。

#include "util.h"
using namespace std; 
int valid(string first, string second)
{
int valid_pairs; 

return valid_pairs; 
}
int main()
{

string first;
string second; 

cout << "Please enter the first sequence: "; 
cin >> first; 

cout << "Please enter the second sequence: "; 
cin >> second; 

cout << "Valid pairs: " << valid(first, second) << endl; 

return 0;
}

Answer 1

递归主要是写下可能的情况，然后依次为每一种情况做正确的事情。

在你的例子中，这些可能性是

1. 至少有一个字符串是空的(在这种情况下根本没有对)
2. first[0]和second[0]为有效对
3. first[0]和second[0]不构成有效对

既然您知道valid(first.substr(1), second.substr(1))将是不包含两个初始字符的有效对的数量，那么您现在可以写下解决方案。
作为练习。

(首先写函数bool is_valid(char c1, char c2)来确定两个字符是否构成一个有效的字符对，这将简化这个函数。)