主题：第53次编程比赛
小黑骑DK [专家分：610] 发布于 2007-05-16 15:41:00
晚上有事，先放出来吧。
就第二题了，
产生指定长度的无连续重复部分的字符串(所有元素都由'1','2','3'这三个字母构成)
输入: 指定的长度n
输出: 无
函数接口:
void unoverlap(int n, char *p)//p是已经分配好了的,不用担心溢出.
例如:
输入5
输出 p中的内容应为12312(或满足条件的其它串)
(不能输出12323,因为23和23是连在一起的并且相同)
当然只要输出一个满足条件字符串的就可以了。
回复列表 （共19个回复）
11 楼
hucheng [专家分：890] 发布于 2007-05-19 10:28:00
#include "stdio.h"
#define MAX 100
void main()
{
int n;
char p[MAX];
void unoverlap(int n, char *p);
puts("Please input the number:");
scanf("%d",&n);
unoverlap(n,p);
}
void unoverlap(int n, char *p)
{
int i=0;
int isok(char *,int);
for(i=0;i<=n;i++) p[i]='0';
i=1;
while(1)
{
p[i]=(p[i]-'0')%3+1+'0';
if (p[i]==p[i-1])
{
if (i<3) { puts("no sollution!"); break;}
i--;continue;
}
if (isok(p,i))
{
if (i==n) {p[i+1]=0;puts(p+1); return;}
i++;
p[i]=p[i-1];
}
}
}
int isok(char *p,int n)
{
int i,j,k;
for(i=1,k=n/2+1;i<k;i++)
{
for(j=0;j<i&&n-i-j>0;j++) if (p[n-j]!=p[n-i-j]) break;
if (j==i) return 0;
}
return 1;
}
[em1]
12 楼
merry05 [专家分：8920] 发布于 2007-05-19 19:38:00
/*实在没什么自信，算法有点不成熟，但是重在参与，如果发现错误偶会再来改*/
#include <string.h>
#define SUCC 1
#define FAIL 0
#define LEFT 0
#define RIGHT 1
#define MAX 1000
void reverse(char *str,char *p)
{
int strlenth,i;
strlenth= strlen(str);
for(i=0;i<strlenth;i++) p[strlenth-1-i]=str[i];
p[strlenth]='\0';
return;
}
int testString(char *str)
{
char newChar;
char revstr[MAX];
int pos,flag;
char *pos_newChar,*pos_boChar;
int chposRe;
flag=1;
reverse(str,revstr);
newChar=*revstr;
pos_newChar=strchr(revstr,newChar);
pos_boChar=strchr(revstr+1,newChar);
chposRe=(int)(pos_boChar-pos_newChar);
while(pos_boChar!=0)
{
if(strlen(revstr+chposRe)<chposRe) break;
flag=1;
for(pos=0;pos<chposRe;pos++)
{
if(revstr[pos]==revstr[pos+chposRe]) continue;
else {flag=0; break;}
}
if(flag==1) return FAIL;
pos_boChar=strchr(revstr+chposRe+1,newChar);
chposRe=(int)(pos_boChar-pos_newChar);
}
return SUCC;
}
void unoverlapmode(int n,char *p,int position,int charNum)
{
p[n]='\0';
if(n==1)
{
*p='1';
return;
}
unoverlapmode(n-1,p,LEFT,charNum);
if(position==LEFT)
{
switch (p[n-2])
{
case '1':
p[n-1]='3';
break;
case '2':
p[n-1]='1';
break;
case '3':
p[n-1]='2';
break;
}
}
else if(position==RIGHT)
{
switch (p[n-2])
{
case '1':
p[n-1]='2';
break;
case '2':
p[n-1]='3';
break;
case '3':
p[n-1]='1';
break;
}
}
if(testString(p)==SUCC) return;
unoverlapmode(n-1,p,RIGHT,charNum);
if(position==LEFT)
{
switch (p[n-2])
{
case '1':
p[n-1]='3';
break;
case '2':
p[n-1]='1';
break;
case '3':
p[n-1]='2';
break;
}
}
else if(position==RIGHT)
{
switch (p[n-2])
{
case '1':
p[n-1]='2';
break;
case '2':
p[n-1]='3';
break;
case '3':
p[n-1]='1';
break;
}
}
if(testString(p)==SUCC) return;
}
void unoverlap(int n,char *p)
{
unoverlapmode(n,p,LEFT,n);
if(testString(p)!=SUCC) unoverlapmode(n,p,RIGHT,n);
}
字符上60后生成速度非常慢，你电脑算爆掉了千万别来找偶啊！
13 楼
redbullivws [专家分：40] 发布于 2007-05-20 01:01:00
#include <stdio.h>
#define MAX_S 10000
#define PUSH(iDeep, elem) \
stack[s] = iDeep; stack[s + 1] = elem;s += 2;
#define POP \
s -= 2;iDeep = stack[s]; p[iDeep] = stack[s + 1];
static int check(char *pch, int iDeep, char elem); //判断元素elem是否可以放到位置iDeep 是反回1否则反回0
void unoverlap(int n, char *p)
{
int stack[MAX_S];
char chi;
int iDeep=0;
int s = 0; //栈顶"指针"
PUSH(iDeep, '1');
for (; iDeep<n; )
{
POP;
iDeep++;
for (chi='1'; chi<='3'; chi++)
if (check(p, iDeep, chi))
{
PUSH(iDeep, chi);
}
}
}
static int check(char *pch, int iDeep, char elem)
{
int equalPosition = iDeep - 1; //与elem相等的位置
int i;
if (elem == pch[iDeep - 1])
return 0;
do{
for (; pch[equalPosition]!=elem ; equalPosition--)
if (equalPosition == 0)
return 1;
for (i=iDeep - 1;
(i > equalPosition && pch[i] == pch[equalPosition - iDeep + i]); i--)
NULL;
if (i == equalPosition) //有重复
return 0;
}while (--equalPosition * 2 >= iDeep);
return 1;
}
//第一次参加，请大家多多指教。
14 楼
redbullivws [专家分：40] 发布于 2007-05-20 01:07:00
//已经发过了见笑了？[em3]
//修改过的效率还是提高不了多少，空间倒少了不少。
#include <stdio.h>
#define MAX_STACK 100000
int check(char *p, char *q);
void unoverlap(int n, char *p)
{
char *q = p;
*q = '0';
while (q - p < n)
{
if (++*q > '3')
{
q--;
continue;
}
if (!check(p, q))
{
*++q = '0';
}
}
*q = '\0';
}
int check(char *p, char *q)
{
char *a = q, *b = q;
char *ta, *tb;
while (1)
{
b--;
if (b - p + 1 < a - b)
{
return 0;
}
ta = a;
tb = b;
while ((*tb == *ta) && (tb-- >= p) && (ta-- > b))
NULL;
if (ta <= b)
{
return 1;
}
}
}
15 楼
panyonglin [专家分：240] 发布于 2007-05-20 02:13:00
hao
16 楼
panyonglin [专家分：240] 发布于 2007-05-20 02:14:00
好啊
17 楼
yxs0001 [专家分：9560] 发布于 2007-05-20 12:09:00
#include <iostream>
using namespace std;
void unoverlap(int n, char *p)
{
int i,j;
p[0] = '0';
p[1] = '1';
for(i=2;i<=n/2;i*=2){
for(j=i-1;j>=0;j--){
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){
p[n] = p[n/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++){
if(p[i] == p[i+1])
p[i] = '0';
else
p[i] = (p[i] - '0')*2 + p[i+1];
}
p[n] = '\0';
}
int main()
{
char t[2000] = "";
char *p = t;
int n = 2;
for(int n=2;n<=20;n++){
unoverlap(n, p);
cout<<n<<" "<<p<<endl;
}
}
18 楼
yuelei85 [专家分：0] 发布于 2007-05-20 19:03:00
11
19 楼
caulin [专家分：20] 发布于 2007-05-20 19:27:00
vs
我来回复
您所在位置：