pascal 0/1字符串问题

来源：百度知道 编辑：UC知道 时间：2024/06/05 01:18:56
输出仅有0和1组成的长度为n的字符串，并且其中不可含有三个连续的相同字符串。
输入：字符串长度
输出：所有满足条件的字符串的个数
样例输入
2
样例输出
4 用pascal实现

该问题其实就是“走台阶”问题。由第一组开始，每一组最多只有3步。由此可以得到DP方程：
a[n]=a[n-1]+a[n-2]+a[n-3].
基于这个分析得出的程序如下(其中的maxn,max可以自己根据情况修改)：
Program Str01;
const max=100;{n的最大值}
maxn=3;{间距的最大值}
var a:array[-maxn+2..max]of longint;
i,j,n:integer;
begin
readln(n);
for i:=-maxn+2 to -1 do a[i]:=0;
a[0]:=2;a[1]:=2;
for i:=2 to n do begin
a[i]:=a[i-maxn];
for j:=1 to maxn-1 do
a[i]:=a[i]+a[i-j];
end;
writeln(a[n]);
end.

Program str01;
var
a:string;
n,i,count:integer;
procedure jinwei(n:integer);
begin
if string[n]='0' then
string[n]:='1'
else
if n<>1 then begin
string[n]:='0';
jinwei(n-1)
end
end
function sum;
var
i,s:integer;
begin
s:=0;
f