Период псевдослучайной последовательности

[Serge_Bliznykov]

Ser@Fim, +100
я согласен с Вашим замечанием!!!
а ещё надо в основной цикл добавить проверку для вот таких "хитрых" последовательностей:
'3123123'
тут хитрость в том, что не надо продолжать искать, если больше половины строки прошли... тогда у подстрок получаются пересекающиеся части..

 while (pos(copy(s,1,i),copy(s,i,length(s)-i))<>0)
           and (i<(length(s)-i) ) do
   inc(i);

[Stilet]

Тут хитростей много навертеть можно, но это уже должен сделать сам автор, ато как то некрасиво получается, такие простейшие вещи за него другие делают.

Кстати думаю скорость чуть-чуть увеличтся если поменять местами условия:

 while (i<(length(s) div 2) ) and (pos(copy(s,1,i),copy(s,i,length(s)-i))<>0)
           do
   inc(i);

Ибо если не выполнится (i<(length(s) div 2) ) второе проверяться не будет по закону оптимизации, а второе условие тяжелее первого - так что незачем напрягать лишний раз кору дуба

[Serge_Bliznykov]

блин.. нашёл ещё "дырку" в алгоритме:
попробуйте для последовательности 123412341234
найди последовательность.

[Zhamie]

Спасибо за ваши старания...

Я кое-как исправила свою начальную программку и вот что получилось:

var i,j,k:integer;
     q,t:integer;
     n:integer;
     e:array[1..100] of integer;

 begin
   n:=Memo1.Lines.Count;
   for i:=1 to n do
   begin
     e[i]:= StrToInt(Memo1.Lines.Strings[i-1]);
   end;
   begin
     k:=1;
     for i:=1 to n do
     begin
       for j:=2 to n do
       if  e[i] = e[j]
       then
       for q:=i+1 to j-1 do
       begin
         t:=j+1;
         if (e[q] = e[t]) then
         k:=k+1;
         inc(t);
       end
        else Continue;

   end;

   Memo2.Lines.Add('Период псевдослучайной последовательности: ');

   for i:=1 to k do
    Memo2.Lines.Add(IntToStr(e[i]));

   Memo2.Lines.Add('Длина периода: '+IntToStr(k));

    end;
    end.

...зацените )

oops... снова ошибки в коде.

[Ser@Fim]

Покритикую немножко себя: ошибся, для последовательности 121125 моя проверка была бы ошибочной
По делу - действительно, для последовательностей повторяющихся несколько раз (123123123123) алгоритм не работает.
Вот переделал код Zhamie:

procedure TForm1.Button1Click(Sender: TObject);
var i,j,k:integer;
     q,t:integer;
     n:integer;
     s:string;
     b:boolean;
begin
   s:=Edit1.Text;
   n:=length(s);
   k:=1;
   for i:=1 to n do
    begin
     for j:=2 to n do
      if  s[i] = s[j]
       then
        begin
         b:=True;
         for q:=i+1 to j-1 do
          begin
           t:=j+q-1;
           if (s[q] = s[t]) then
            k:=k+1
           else
            begin
             b:=False;
             break;
            end;
           inc(t);
          end;
         if (b=True) then
          for q:=2*k+1 to n do
           begin
            t:=q mod k;
            if (t=0) then t:=k;
            if (s[q]<>s[t]) then
             b:=false;
           end;
         if (b=True) then
          break
         else
          k:=1;
        end
       else Continue;
    end;
    Memo2.Lines.Add('Период псевдослучайной последовательности: ');
    Memo2.Lines.Add(copy(s,1,k));
    Memo2.Lines.Add('Длина периода: '+IntToStr(k));
end;

Действовал "в лоб", так что за оптимизаторские ошибки приношу извинения. Например 1212512125 сначала ищем ближайшее повторение (12), затем проверяем, чтобы оставшаяся часть так же повторялась (что не выполняется, тк дальше идет 5) и заново

[Somebody]

Не уверен, правильно ли, но пока ошибок не вижу:

procedure TForm1.Button1Click(Sender: TObject);
var
  s: String;
  i, j, l: Integer;
begin
  s := Edit1.Text;
  l := 1;
  i := 1;
  j := 2;
  while j <= length(s) do
    if s[i] = s[j] then
    begin
      inc(i);
      inc(j);
    end
    else
    begin
      i := 1;
      inc(l);
      j := l + 1;
    end;
  Caption := 'Äëèíà ' + IntToStr(l) + ', ïåðèîä ' + Copy(s, 1, l);
end;

[Serge_Bliznykov]

Somebody, отлично!
Проверил.
мне тоже не удалось найти "плохих" последовательностей..

[puporev]

Caption := 'Äëèíà ' + IntToStr(l) + ', ïåðèîä ' + Copy(s, 1, l);

Перед тем как копировать текст, содержащий русские буквы, проследите чтоб была русская раскладка клавиатуры, русские символы будут отображаться нормально.

[Serge_Bliznykov]

Caption := 'Длина ' + IntToStr(l) + ', Период ' + Copy(s, 1, l);

[Zhamie]

Программа действительно без ошибок.

ОГРОМЕННОЕ СПАСИБО ВАМ ВСЕМ!!!