题目: 产生指定长度的无连续重复部分的字符串(所有元素都由'1','2','3'这三个字母构成)输入: 指定的长度n输出: 无函数接口:void unoverlap(int n, char *p)//p是已经分配好了的,不用担心溢出.例如:输入5输出 p中的内容应为12312(或满足条件的其它串)(不能输出12323,因为23和23是连在一起的并且相同)当然只要输出一个满足条件字符串的就可以了。 最容易想到的是回溯法，每放一个数字判断是否会产生重复，按'1','2','3'的顺序放置，如果都不满足，则回退一个。代码1如下：（取材于poorb的代码） bool Cover(char *base, int top)//判断是否有连续重复序列 {    int p;    int k = (top + 1) / 2;     for (int step=1; step<=top; step++)    {        for (p=0; p<step; ++p)        {            if (base[top-p] != base[top-step-p])                break;        }         if (p == step)//产生重复            return true;     }     return false;} void unoverlap(int n, char *p){    int now = 1;    p[0] = '1';     while (now < n)    {        p[now] = '1';         while (Cover(p, now))//如果出现连续重复序列         {            while (p[now] == '3')//若当前位置对所有字符都不满足，回退一个             {                --now;            }            p[now]++;        }        now++;    }} 也有直接写出序列的方法，crossbow说本题实际上是求Thue序列，也就是不匹配正则表达式.*\(.+\)\1.*的串。Axel Thue证明了存在无穷长度的Thue序列。构造Thue序列的办法是这样（假设字母表是{N,O,P}）：从单个N开始，顺序扫描当前序列，见到一个N写下OP，见到一个O写下ONP，见到一个P写下N。新写下的序列就是一个更长的Thue序列。我们现在分别用1，2，3代替N，O，P，构造长度为n的Thue序列。类似倒水，对两个数组的分别求Thue序列，存储到新的数组中，将最后得到的Thue序列存储到p中 代码2如下： void unoverlap(int n, char *p){    char *a = new char[n+3];//临时数组，用来存储当前的Thue序列     int lable = 0;    int len = 0;    int top;    int i;        a[len++] = '1';//最初的Thue序列是单个的字符'1'     while (1)    {        top = 0;        for (i=0; i<len; ++i)//根据构造原理，由原Thue序列得到新的Thue序列，由a到p         {            if (a[i] == '1')            {                p[top++] = '2';                p[top++] = '3';            }            else if (a[i] == '2')            {                p[top++] = '2';                p[top++] = '1';                p[top++] = '3';            }            else                p[top++] = '1';                            if (top >= n)//如果已经得到足够长度的Thue序列，跳出循环                 break;        }        if (i < len)        {            lable = 1;//表示最终得到的Thue序列已经存储在数组p中             break;        }                    len = top;        top = 0;        for (i=0; i<len; ++i)//根据构造原理，由原Thue序列得到新的Thue序列，由p到a         {            if (p[i] == '1')            {                a[top++] = '2';                a[top++] = '3';            }            else if (p[i] == '2')            {                a[top++] = '2';                a[top++] = '1';                a[top++] = '3';            }            else                a[top++] = '1';                            if (top >= n)                break;        }        if (i < len)        {            lable = 2;//表示最终得到的Thue序列存储在数组a中，需要复制到p中             break;        }    }        if (lable == 2)//把Thue序列复制到p中     {        for (i=0; i<n; ++i)            p[i] = a[i];    }    p[n] = '\0';        delete []a;} yxs0001也提供了一种直接写入序列的方法，他是从01开始，0替换为01，1替换为10，继续下去得到无穷序列。将序列中的01写为'1',10写为'2',相同的写为'3'，即可得到序列。附：雨中飞燕对此算法进行了数学证明。 按照此算法，可得到代码3：void unoverlap(int n, char *p){    char *a = new char[n+2];//临时数组，用来存储当前的yxs序列     int lable = 0;    int len = 0;    int top;    int i;        a[len++] = '0';    a[len++] = '1';//最初的yxs序列是01     while (1)    {        top = 0;        for (i=0; i<len; ++i)//根据构造原理，由原yxs序列得到新的yxs序列，由a到p         {            if (a[i] == '0')            {                p[top++] = '0';                p[top++] = '1';            }            else            {                p[top++] = '1';                p[top++] = '0';            }                            if (top > n)//如果已经得到足够长度的yxs序列，跳出循环                 break;        }        if (i < len)        {            lable = 1;//表示最终得到的yxs序列已经存储在数组p中             break;        }                    len = top;        top = 0;        for (i=0; i<len; ++i)//根据构造原理，由原yxs序列得到新的yxs序列，由p到a         {            if (p[i] == '0')            {                a[top++] = '0';                a[top++] = '1';            }            else             {                a[top++] = '1';                a[top++] = '0';            }                            if (top > n)                break;        }        if (i < len)        {            lable = 2;//表示最终得到的yxs序列存储在数组a中，需要复制到p中             break;        }    }        if (lable == 2)//把yxs序列复制到p中     {        for (i=0; i<top; ++i)            p[i] = a[i];    }        for (i=0; i<top; ++i)//按照转换原理，由yxs序列得到实际需要的序列     {        if (p[i] == p[i+1])            p[i] = '3';        else if (p[i] == '0')            p[i] = '1';        else            p[i] = '2';    }        p[n] = '\0';        delete []a;} 在构造yxs序列时，yxs0001并没有采用代码3的方法，而是进行了巧妙的变化----毕竟倒水算法时间复杂度太高，而且需要辅助空间。yxs0001利用yxs序列的特点：2个变4个，4个变8个，。。。直接写入yxs序列。但是yxs0001在构造yxs序列没有对代码进行优化，造成了很多重复计算。代码4如下： void unoverlap(int n, char *p){    int i, j;    p[0] = '0';    p[1] = '1';        for (i=2; i<=n/2; i*=2)//i表示当前yxs序列的长度，每处理一次，长度增倍     {        for (j=i-1; j>=0; j--)//出现重复计算，实际上j的值不必到0，只要到i/2就好了         {                        if (p[j] == '0')            {                p[2*j] = '0';                p[2*j+1] = '1';            }            else            {                p[2*j] = '1';                p[2*j+1] = '0';            }        }    }        if ((n & 1) == 0)//如果yxs序列的长度为偶数，需要多写一个元素     {        p[n] = p[n/2];    }        //补充没有被填写的空位，这里也有重复计算，实际上i的值只要取[n/4，(n-1)/2]就好了     for (i=(n-1)/2; i>=0; i--)    {        if (p[i] == '0')        {            p[2*i] = '0';            p[2*i+1] = '1';        }        else        {            p[2*i] = '1';            p[2*i+1] = '0';        }    }        for(int i = 0;i<n;i++)//按照转换原理，由yxs序列得到实际需要的序列     {        if (p[i] == p[i+1])            p[i] = '0';        else            p[i] = (p[i] - '0')*2 + p[i+1];           ++p[i]; //把012转化成123    }     p[n] = '\0';} 观察yxs序列的形成过程，其实我们很容易发现，yxs序列的构造还可以采用下面的方法：先令p[0] = '0';p[1] = '1'; 然后对下标i=[1，n/2]之间的所有元素，按规则为p[2*i]和p[2*i+1]赋值。这样得到的序列也是yxs序列。代码5如下： void unoverlap(int n, char *p){       p[0] = '0';    p[1] = '1';        for (int i=1; i<=n/2; i++)//先写入由0和1构成的yxs序列    {        if (p[i] == '0')        {            p[2*i] = '0';            p[2*i+1] = '1';        }        else        {            p[2*i] = '1';            p[2*i+1] = '0';        }    }        if ((n & 1) == 0)     {        p[n] = p[n/2];    }          for (int i=0; i<n; i++)//按照转换原理，由yxs序列得到实际需要的序列     {        if (p[i] == p[i+1])            p[i] = '0';        else            p[i] = (p[i] - '0')*2 + p[i+1];                    ++p[i]; //把012转化成123     }    p[n] = '\0';}很明显，代码5仍然是先实现yxs序列，但是弥补了代码4重复计算和需要补充空位的缺陷。 wangfangbob认为yxs序列貌似是几何分形，即以0 1开始每次取反码然后加在后面：0 10 1 1 00 1 1 0 1 0 0 10 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0根据wangfangbob的算法也很容易得到yxs序列。代码6如下： void unoverlap(int n, char *p){       p[0] = '0';    p[1] = '1';        int len = 2;    while (len < n)    {        for (int i=0; i<len; ++i)//对当前序列取反码然后加在后面        {            if (len+i > n)                break;            if (p[i] == '0')                p[len+i] = '1';            else                p[len+i] = '0';        }        len *= 2;    }       if ((n & 1) == 0)     {        p[n] = p[n/2];    }          for (int i=0; i<n; ++i)//按照转换原理，由yxs序列得到实际需要的序列     {        if (p[i] == p[i+1])            p[i] = '3';        else if (p[i] == '0')            p[i] = '1';        else            p[i] = '2';    }    p[n] = '\0';} 在理解yxs序列的过程中，我总感觉由yxs序列转化成题目要求的序列采用的规则太麻烦，心想能否采用更简单的规则呢？于是尝试着采用如下更简单的规则：首先直接用字符'1'和'2'代替原来的'0'和'1'；转换的规则是只改变原yxs序列中重复的两个相邻字符的后者。由于原yxs序列能够保证不会出现长度大于1的相同子串，所以由这个简单规则得到的序列也是一个无连续重复部分的字符串。 代码7如下： void unoverlap(int n, char *p){       p[0] = '1';    p[1] = '2';        for (int i=1; i<=n/2; i++)//先写入由1和2构成的yxs序列    {        if (p[i] == '1')//每隔i个数取相同的值，因为i是递增的，所以可以保证不会出现长度大于1的相同子串         {            p[2*i] = '1';            p[2*i+1] = '2';        }        else        {            p[2*i] = '2';            p[2*i+1] = '1';        }    }          for (int i=1; i<n; i++)//修正序列的值，把连续的两个相同值的后者改成第3个值就好了     {        if (p[i] == p[i-1])            p[i] = '3';    }    p[n] = '\0';} 注：虽然上述方法都能得到正确的字符串，但是字符串的内容却不相同。采用以下主函数生成字符串并判断字符串是否满足条件。（由小黑骑DK提供） #include <iostream>#include <time.h>using namespace std; void unoverlap(int n, char *p);int overlap(const char *p, int n);int test_str(const char *p, int n); int main(){ char a[20] = {0}; int n = 14;  unoverlap(n, a); puts(a); test_str(a, n);  getchar(); return 0;} //判断一个字符序列里是否有重复的部分 1为不满足条件int test_str(const char *p, int n){        int i = 2;     for (; i<n; i++)    {        if (overlap(p,i) == 1)        {            printf("\nWhich:%d\n", i);            return 1;        }    }     return 0;} //判断一个序列是否有连续重复的部分(以第n个字母结束的子串)int overlap(const char *p, int n){    int max = (n+1)/2;//如果有重复部分,则此长度是最大重复长度    int length = 1;    int end1, end2;//两个要比较的子串结尾     for (; length<=max; length++)    {        for (end1=n,end2=n-length; end1>n-length && p[end1]==p[end2]; end1--,end2--)            ;//比较两个子串        if (end1 == n-length)//两子串相同,表明有重复        {            printf("\nlength:%d\n",length);            return 1;        }    }     return 0;} 代码1 输出：12131231321231代码2 输出：21323121312321代码3 输出：13212313231213代码4 输出：21323121312321代码5 输出：21323121312321代码6 输出：13212313231213代码7 输出：12312132313212 测定速度；int main(){ time_t startTime; time_t endTime; time(&startTime);        for (int n=10000; n<20000; ++n){  char a[25000] = {0}; unoverlap(n, a);}  time(&endTime); cout << difftime(endTime, startTime) << endl;  getchar(); return 0;} 代码1 超时代码2 8秒 代码3 10秒 代码4 8秒 去掉重复计算可达到5秒 代码5 5秒代码6 5秒代码7 4秒 附上雨中飞燕的证明----- yxs0001的算法证明： 以n=20为例：源下标 0 1 2 3 4 5 6 7 8 91011121314151617181920对应串 1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1       \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\目标串  1 3 2 1 2 3 1 3 2 3 1 2 1 3 2 1 2 3 1 2 0 两个相邻对应串的字符决定一个目标串字符 1 2 -> 1 2 1 -> 211,22-> 3（对应的数可以随意） （下文?表示1个1或2）证明1：对应串不存在任意三个连续相同的数    对应串里的数两两分组，每组必然包含1和2；    因为任意三个连续的数必定包含一组，所以不存在 推论1：对应串不存在任意三个间距为1的相同的数（即1?1?1或者2?2?2）    或者，不存在任意三个间距为2^n-1的相同的数。    因为要出现1?1?1的必要条件是在它前面折半的位置出现三个连续相同的数    用数学归纳法，若间距是2^(n-1)-1不存在，可以得到间距是2^n-1也不存在（n>0） 证明2：对应串可能存在任意三个间距为2的相同的数，即形如1ab1AB1，但a!=A或者b!=B。    把它两两分组，假设是    1a b1 AB 1*    于是a=b=2，又因为A!=B，所以AB之中必有一个数与ab不相等    另一种分组法类似（成镜像），此处略，下同。 推论2：对应串可能存在任意三个间距为偶数的相同的数，形如1aaaa1bbbb1，但aaaa的内容与bbbb不全相同。    当间距是比2大的偶数的时候，假如是4，可表示为：    1abcd1ABCD1?    有类似分组为：    1a bc d1 AB CD 1?    所以，a=d=2，令A=D=2，得B=C=1，但因b!=c，矛盾；    当间距更大时，可以类似方法递推。所以满足这个条件的序列也不存在 推论3：对应串可能存在任意三个间距为非2^n-1形式的数的相同的数，但前半串与后半串不全相同。    这个证明简单，如果间距是奇数，如1?????1?????1，那么在前面折半的位置必然能找到    形如1??1??1这样的数，一直递降，最后必定出现证明2或者推论2的情况。 结论1：对应串中，任意三个间距为k的相同的数中：    k表达为2^n-1时，这样的序列不存在；    k不能表达为2^n-1时，中间所夹的两段子串不全相同。    或者可以表达为：对应串中不存在一对仅有一个公共元素且完全相同的子串。 结论2：由此对应串生成的目标串，不存在一对连续且相同的子串。 证毕。

评论