题目:
产生指定长度的无连续重复部分的字符串(所有元素都由'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 1
0 1 1 0
0 1 1 0 1 0 0 1
0 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 -> 2
11,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：由此对应串生成的目标串，不存在一对连续且相同的子串。
证毕。
评论