Manchester- DNA(最容易理解-带图）

解题思路:

（这里A，B就是题目中的a，b）；

1.总的思路，把整个DNA的输出变成得到每一行，然后输出；

2.首先得到DNA的第一行，用字符数组记录；

3.第一行DNA的宽度就是A，即字符数组的有效长度为A，且第一行DNA的型式都是第一个字符和最后一个字符都是'X' 中间的为空格；

4.交换X得到下一行的DNA；（交换如图）k代表空格；

5.交换的注意事项在下面（注意事项里）；

6.把整个DNA的输出变成每一行的输出；

7.输出第一行，交换后；

8.再次递归处理，直到输出所有行；

9.每组DNA输出的行数等于A*B-(B-1);（即DNA的行数，也就是递归的次数，题目例子中如上图输出4组，就是A*B-(B-1)==17行）；



注意事项:
首先重复度并不是把上面图中内容，重复的输出几次；注意第一个重复度，与第二个之间公用一行，这也就是为什么行数等于

A*B-(B-1)；

1.交换并不是简单的，把第一个X和后面的空格交换，以及把最后一个X和它前面的空格交换；

2.交换时，必须先记录第一个位置（p）的X，和最后一个位置（q）的X；

3.然后让（p）位置的X，等于它后面的空格，让（q）位置的X等于它前面的空格；

4.然后再把前面记录的X，放到它们各自交换了的空格上；

if(p==A-1&&q==0)
这句代码，表示交换了一个来回了，需要重置p，q；

交换实现代码：

if(p==A-1&&q==0)
   {p=0;q=A-1;}

   termp=dna[p];
   termq=dna[q];

   dna[p]=dna[p+1];

   p++;

   dna[q]=dna[q-1];

   q--;

   dna[p]=termp;
   dna[q]=termq;

这样交换是因为：当交换到图中，绿色标记的X的位置时，会导致，它前后的交换不正确；具体为什么会不正确，你可以先随意的按照最简单的交换思路来试试，如下代码自己走一遍就知道为什么不行了；

   term=dna[p+1];
   dna[p+1]=dna[p];
   dna[p]=term;
   p++;

   term=dna[q-1];
   dna[q-1]=dna[q];
   dna[q]=term;
   q--;

参考代码:

#include <iostream>
using namespace std;

void output( int A, int N, int p, int q );    //输出每一行


char dna[40];
void initialize_dna( int A );           //得到第一行


/*--------------------------------------*/
int main()
{
    int N, A, B;

    cin >> N;
    for ( int i = 0; i < N; i++ )
    {
        cin >> A >> B;
        initialize_dna( A );
        output( A, A * B - (B - 1), 0, A - 1 );
    }

    return(0);
}


/*--------------------------------------*/
void initialize_dna( int A )
{
    dna[0]        = 'X';
    dna[A - 1]    = 'X';
    for ( int i = 1; i < A - 1; i++ )
        dna[i] = ' ';
}


/*--------------------------------------*/

void output( int A, int N, int p, int q )
{
    char termp, termq;

    if ( N == 0 )
    {
        cout << endl; return;
    }else

        for ( int i = 0; i < A; i++ )
            cout << dna[i];
    cout << endl;

    /*-------------------------------*/
    if ( p == A - 1 && q == 0 )              //输出一轮了，重置p，q
    {
        p = 0; q = A - 1;
    }

    termp    = dna[p];
    termq    = dna[q];

    dna[p] = dna[p + 1];

    p++;

    dna[q] = dna[q - 1];

    q--;

    dna[p]    = termp;
    dna[q]    = termq;
    /*-------------------------------*/

    output( A, N - 1, p, q );           //输出下一行
}

别忘点赞哦-.-