首页 > 代码库 > 回溯法第6题—0/1字符串问题
回溯法第6题—0/1字符串问题
[问题描述]输入仅由0/1组成的长度为n的字符串,并且其中不可含有三个连续的相同子串。
输入:字符串的长度n(n<=40)。
输出:所有满足条件的字符串的个数
[样例输入]
2
4
设0/1序列的长度为L,x,y,z分别为第三、第二、第一个子串的首指针;
初始:x=L;y=L-1;z=L-2;
若三个数字不同,dec(x,1);dec(y,2);dec(z,3);
直到 (a[z]...a[y-1]=a[y]...a[x-1]=a[x]...a[l]) or (z<=0)
再开三个指针判断子串是否相等;
==============================分割线==============================
优化:利用对称性,比如n=6时,011001中不含3个连续的相同子串;那么100110也必然不含3个连续的相同子串;
因此只需查找第1位为0的序列,将得到的方案数乘以2即为所求。
字符串的生成方法:回溯法。
初始时a[1]=0,然后try(a[2]),顺序为先填0再填1,填0后满足条件则填下一位,否则改为1,若还是不满足条件,回溯至前一位,若满足条件,填下一位。
生成一个字符串时,方案数+2;
var a:array[1..40]of byte;//0/1序列 tot:longint; L:integer;//位指针 n:integer;function judge(L:integer):boolean;var x,y,z:integer;r,q,p:integer;begin x:=L;y:=L-1;z:=L-2;//指针初始化 while z>0 do begin p:=x;q:=y;r:=z; while (r<y)and(a[p]=a[q])and(a[q]=a[r]) do begin inc(p);inc(q);inc(r);end;//遍历子串 if r=y then exit(false);//如果三个子串完全一样就返回false dec(x,1);dec(y,2);dec(z,3); end; exit(true);end;procedure search(L:integer);begin if L>n then begin inc(tot,2); exit; end; a[L]:=0; if judge(L) then search(L+1); a[L]:=1; if judge(L) then search(L+1); end;begin readln(n); a[1]:=0; L:=1; tot:=0; search(2); writeln(tot);end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。