Разное - Уникумы колец чисел постоянной длины

[burany]

Здравствуйте, форум



Задача: вызвать в Pascal входной файл simv.txt таблицы строк одинаковой длины, "закольцевать" строки и оставить единичных представителей колец чисел, они же строки постоянных длин.

Объясняю: Если нанизать на кольцо нумерованные шары (ожерелье), невозможно будет

сказать, какой из них первый. Разве что договориться. В производимой программой

вывода последовательностей постоянной длины строк массе текста среди прочих строк будут попадаться, к примеру, такие:

...

1 3 1 1 5 5 1

...

3 1 1 5 5 1 1

...

1 1 5 5 1 1 3

...

1 5 5 1 1 3 1

...

5 5 1 1 3 1 1

...

5 1 1 3 1 1 5

...

1 1 3 1 1 5 5

...

Но ведь это кольцо. А у кольца начала нет, и... Задача: где найти

программу с опцией: напечатать одного представителя кольца, а всех

остальных удалить. В первой строке самый первый символ

переставляется в конец строки, вся строка сдвигается влево и

сравнивается со всеми строками всей таблицы. При выявлении в

толще таблицы двойника, найденный второй дубликат убивается.

Программа возвращается к первой строке, теперь уже второй

символ переносится в конец строки, сдвиг и все по новой. И так по

очереди с третьим, четвертым и т. д. символами. Повторить столько

раз сколько имеется столбцов минус единица. Можно начать и с конца

строки. Сама таблица тоже сократится во столько раз, сколько имеется

столбцов. И будет программа вывода последовательностей с

представлением единичных представителей колец чисел. Так приблизительно

представляется. Здесь непонятно, как перейти к следующей строке? А строк тысячи. Не могли бы Вы расписать шаги для обработки нижеследующего поимера:



1 1 1 1 1 1 1 1 3

1 1 1 1 1 1 1 2 2

1 1 1 1 1 1 1 3 1

1 1 1 1 1 1 2 1 2

1 1 1 1 1 1 2 2 1

1 1 1 1 1 1 3 1 1

1 1 1 1 1 2 1 1 2

1 1 1 1 1 2 1 2 1

1 1 1 1 1 2 2 1 1

1 1 1 1 1 3 1 1 1

1 1 1 1 2 1 1 1 2

1 1 1 1 2 1 1 2 1

1 1 1 1 2 1 2 1 1

1 1 1 1 2 2 1 1 1

1 1 1 1 3 1 1 1 1

1 1 1 2 1 1 1 1 2

1 1 1 2 1 1 1 2 1

1 1 1 2 1 1 2 1 1

1 1 1 2 1 2 1 1 1

1 1 1 2 2 1 1 1 1

1 1 1 3 1 1 1 1 1

1 1 2 1 1 1 1 1 2

1 1 2 1 1 1 1 2 1

1 1 2 1 1 1 2 1 1

1 1 2 1 1 2 1 1 1

1 1 2 1 2 1 1 1 1

1 1 2 2 1 1 1 1 1

1 1 3 1 1 1 1 1 1

1 2 1 1 1 1 1 1 2

1 2 1 1 1 1 1 2 1

1 2 1 1 1 1 2 1 1

1 2 1 1 1 2 1 1 1

1 2 1 1 2 1 1 1 1

1 2 1 2 1 1 1 1 1

1 2 2 1 1 1 1 1 1

1 3 1 1 1 1 1 1 1

2 1 1 1 1 1 1 1 2

2 1 1 1 1 1 1 2 1

2 1 1 1 1 1 2 1 1

2 1 1 1 1 2 1 1 1

2 1 1 1 2 1 1 1 1

2 1 1 2 1 1 1 1 1

2 1 2 1 1 1 1 1 1

2 2 1 1 1 1 1 1 1

3 1 1 1 1 1 1 1 1



?

Спасибо

[Busla]

такое ощущение, что читаю машинный перевод - какое-то бессвязное нагромождение слов

[pva]

картинка красивая из циферок получилась

burany, а мона твои намётки на решение, а то вооще не понятно, о чём речь

[pva]

pva, наметок почти и нет:





var f : text;

s : char;

begin

assign(f, 'C:\c20c.txt');

reset(f);

while not Eof(f) do

begin

read(f, s);

write(s);

end;

close(f);

end.





а также:





{function AnsiCompareStr(s2, s0 :string) : integer;}

var

s : string[18];

s1 : string[2];

begin

s := ' 1 12 23 24 25 36';

s1:= copy(s,17,2);

delete(s,17,2);

insert(s1,s,1);

writeln(s);

{AnsiCompareStr:=(s2, s0);}

end.





Как все это связать? Задача, ведь, подробно расписана.

[pva]

burany, до меня трудно доходит. Нужно найти период повторения строки при циклическом сдвиге влево?

Всё, дошло. В общем я так понимаю, что это задача распознавания образов. Придётся делать перебор (сравнение всех между собой). Вариант 1:



Код:

Код: Выделить всё

function cyclic_equal(string a; string b): boolean;
var i: integer;
begin
  i:=1;
  result := false;
  while (not result) and (1<=length(a)) do begin
    result := b = copy(a, i, n-i) + copy(a, 1, i);
    inc(i);
  end
end;
...
var input_strings : array of string;
...
for i:=low(input_strings) to high(input_strings) do begin
  for j:=i+1 to high(input_strings) do begin
    if cyclic_equal(input_strings[i], input_strings[j]) then writeln('удалить вариант ', input_strings[i]);
  end
end

Второй вариант (извращенский), когда ооочень много строчек, а их длина есть степень двойки.

1. для каждой строчки делаем быстрое преобразование фурье, либо быстрое преобразование косинусов (требует длину - степень двойки, при циклическом сдвиге меняется только фаза фурье)

2. составляем строчки из амплитуд частот

3. сортируем список по полученным строчкам амплитуд (посимвольно) быстрой сортировкой

4. сравниваем между собой только внутри подмассивов с посимвольно одинаковыми амплитудами (на случай когда 2 разных сигнала имеют одинаковый частотно-амплитудный состав)

[burany]

По поводу непонятки, последнее слово строки ставится в

начало строки, вся строка сдвигается к хвосту, пробелы сохраняются

(важно!). Получаются две одинаковые строки, или более:



3 1 1 1 1 1 1 1 1

3 1 1 1 1 1 1 1 1

- - -



Надо оставить одну.





Pva, ты прогонял свои функции на циферках из красивой

картинки? А то что-то у меня не сразу.



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

список, а конкретно, в кольцо?

[pva]

Цитата burany:



Pva, ты прогонял свои функции на циферках

Разное - Уникумы колец чисел постоянной длины

Нет конечно, я только идею передал. Стопудово в коде есть простые глюки, но ты их выловишь


Цитата burany:



строку в динамический

список

Разное - Уникумы колец чисел постоянной длины

да, вместо `string` пиши `array of TЧтонибудь` и переделай функцию cyclic_equal

[burany]

Всем большое спасибо