Четверговые задачки

← →
MBo © (2005-03-03 13:54) [40]

GuAV © (03.03.05 13:52) [32,39]
Не, не то... Не нужно ничего менять...

← →
GuAV © (2005-03-03 14:04) [41]

IMHO [32]+[39] работоспособно..

Хорошо, тогда запомнить текущий и идти пытаясь найти повторение через N элементов. Если не получится и не дошли до конца списка, то увеличить N (например N := N shl 1) и повторить.

← →
GuAV © (2005-03-03 14:05) [42]

GuAV © (03.03.05 14:04) [41]
увеличить N (например N := N shl 1) и повторить.
, снова запомнив текущий.

← →
КаПиБаРа © (2005-03-03 14:19) [43]

6.
Один конвеер на N элементов. Для коротких петлей длиной до N элементов.
Один динамический массив в который заносится каждый N элемент для длинных петлей, длтна которых больше N.

На каждом шаге проверять наличие в обоих структурах.

← →
Alx2 © (2005-03-03 14:19) [44]

6.
Еще один дикий вариант с минимумом затрат на память:

Посчитать количество всей доступной оперативной памяти. посчитать размер одного элемента списка.
Помчаться по списку. Дошли до конца- хорошо. Не дошли - смотрим количество пройденных элементов. Как только поняли, что оно "зашкалило", т.е. не может разместиться с нашими объемами ОЗУ - значит, цикл.

← →
Kaban (2005-03-03 14:35) [45]

Alx2 © (03.03.05 14:19) [44]
Я предлагал подобное в [17]

Видимо это тоже не наш метод

← →
КаПиБаРа © (2005-03-03 14:38) [46]

КаПиБаРа © (03.03.05 14:19) [43]
Максимум используемой памяти (N+K/N)*SizeOfPointer,
где K - количество элементов списка.

← →
Alx2 © (2005-03-03 14:38) [47]

Kaban (03.03.05 14:35) [45]

Не заметил. Сорри.

← →
MBo © (2005-03-03 14:46) [48]

>КаПиБаРа
достаточно O(1) памяти

← →
КаПиБаРа © (2005-03-03 14:51) [49]

MBo © (03.03.05 14:46) [48]
Это был способ без порчи данных.

Нужно менять направленность списка. Тогда если есть петля мы вернемся к элементу с которого начали.

← →
GuAV © (2005-03-03 14:53) [50]

> достаточно O(1) памяти

[41] [42] ?

← →
MBo © (2005-03-03 14:57) [51]

>GuAV © (03.03.05 14:53) [50]
>[41] [42] ?
это алгоритм сложности O(N^2)- многовато будет...

← →
default © (2005-03-03 15:00) [52]

MBo, [44], [17] точно не верны?
GuAV © (03.03.05 14:53) [50]
это хуже чем [44] и [17]
представь послед-ть навроде такой
0 1 2 3 ... 10^1000000 (10^1000000) + 1 10^1000000

← →
КаПиБаРа © (2005-03-03 15:13) [53]

КаПиБаРа © (03.03.05 14:51) [49]
Поясню ответ.

PStart := PNode;
PredNode := PNode;
NextNode := PNode^.Next;

1:
PNode := NextNode;
if PNode^.Next = PStart then Есть цикл, Exit;
if PNode^.Next = nil then Нет цикла, Exit;
NextNode := PNode^.Next;
PNode^.Next := PredNode;
goto 1

← →
default © (2005-03-03 15:17) [54]

ну если взять к примеру списко
1 2 3 4 5 6 7 8 5
то пробегая по списку мы держим указатели постоянно на два соседних элемента
в случае зацикливания - указатели станут равны
то есть сначала храним пару
2 3
потом 3 4, 4 5, 5 6, 7 8, 5 5 - и тут мы понимает что это цикл

← →
КаПиБаРа © (2005-03-03 15:21) [55]

default © (03.03.05 15:17) [54]
потом 3 4, 4 5, 5 6, 7 8, 5 5 - и тут мы понимает что это цикл
не так
3 4, 4 5, 5 6, 6 7, 7 8, 8 5, 5 6 и т.д

← →
default © (2005-03-03 15:23) [56]

КаПиБаРа © (03.03.05 15:21) [55]
.... 1 2 3 4 5 6 7 8 5 ...
для первого элемента имеем указатели
2 3
для второго
3 4
для восьмого
5 5

← →
default © (2005-03-03 15:25) [57]

КаПиБаРа © (03.03.05 15:21) [55]
блин туплю сори

← →
КаПиБаРа © (2005-03-03 15:27) [58]

default © (03.03.05 15:23) [56]
1 2 3 4 5 6 7 8 5
Построим список так

N N_Next
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 5

И где тут 5 5 встречается?

← →
КаПиБаРа © (2005-03-03 15:28) [59]

default © (03.03.05 15:25) [57]
Ага

← →
КаПиБаРа © (2005-03-03 15:30) [60]

КаПиБаРа © (03.03.05 15:13) [53]
поправочка
PStart := PNode; NextNode := PNode^.Next; 1: PredNode := PNode; PNode := NextNode; if PNode^.Next = PStart then Есть цикл, Exit; if PNode^.Next = nil then Нет цикла, Exit; NextNode := PNode^.Next; PNode^.Next := PredNode; goto 1

← →
Alx2 © (2005-03-03 15:42) [61]

6.
Пусть N - длина зацикленного участка.
P(k) - значение ссылки в k-м встреченном элементе.
Для ссылок внутри цикла справедливо P(k+N) = P(k) или P(N*m+k)=P(k) где m - натуральное.

Отсюда вырисовывается алгоритм:

Запоминаем ссылку на текущий k-й элемент. Сравниваем с ссылкой через M элементов. Если равны - цикл. Если нет, то k:=k+M, а M := M+1. В итоге M будет расти до тех пор, пока не станет равной N*m.
В результате будем иметь либо конец списка, либо равенство P(k)=P(k+M), в случае цикла.

← →
MBo © (2005-03-03 15:48) [62]

>Alx2 © (03.03.05 15:42) [61]
Если от глыбы отсечь лишнее, получится изящная скульптура ;)

← →
Alx2 © (2005-03-03 16:02) [63]

MBo © (03.03.05 15:48) [62]
Реализация (непроверенная)

Type PList = ^TList; TList = Record Info: Pointer; Next: PList; End; Function isLooped(List: PList): Boolean; Var M, Current: Integer; Tmp: PList; Begin Result := False; M := 1; Tmp := List; Current := 0; While List <> Nil Do Begin List := List^.Next; inc(Current); If (Current = M) Then If Tmp = List Then Begin Result := true; exit; End Else Begin Tmp := List; Current := 0; inc(M); End; End; End;

← →
Alx2 © (2005-03-03 16:17) [64]

Проверил. Работает как часы :)

← →
MBo © (2005-03-03 16:21) [65]

>Alx2 © (03.03.05 16:02) [63]
резюмируем: пускаем по списку два указателя. Один идет по 2 шага, другой по одному. Встретились - есть цикл.

← →
default © (2005-03-03 17:56) [66]

Alx2 © (03.03.05 15:42) [61]
изящный алгоритм
правда вы его не объяснили:)
P.S. я не о том что мне надо объяснить, я понял, я вообще

>default © (03.03.05 17:56) [66]

Вообще-то идею объяснил в посте Alx2 © (03.03.05 15:42)

У MBo несколько другой: по списку идут два указателя с разной скоростью. Когда встретятся - есть цикл.

У меня же неявно ищется число, кратное периоду цикла (переменная M). В конечном итоге суть такая же, что и у MBo.

default © (03.03.05 19:36) [68]
Да, но с подводными камнями: если список огромен, и велика петля, то возможно переполнение (так как считается кратное), да и количество прогонов по петле велико. А в условии вовсе не требуется искать период петли.

Алгоритм, реализованный по идее MBo более красив и работает быстрее при вышеописанных условиях:

Function isLooped2(List: PList): Boolean; Var Tmp: PList; Begin Result := False; If List <> Nil Then Begin Tmp := List^.Next; While (Tmp <> Nil) And (Tmp <> List) And (Tmp^.Next <> Nil) Do Begin List := List^.Next; Tmp := Tmp^.Next^.Next; End; Result := List = Tmp; End; End;

2.
Function LSRtoLRS(Const LSR: String): String; Var idx: Integer; Begin If LSR = "" Then Result := "" Else Begin idx := (Length(LSR) + 1) Div 2; Result := LSRtoLRS(copy(LSR, 1, idx - 1)) + LSRtoLRS(copy(LSR, idx + 1, Length(LSR))) + LSR[idx]; End; End; Function SLRtoLRS(Const SLR: String): String; Var len: Integer; Begin If SLR = "" Then Result := "" Else Begin len := (Length(SLR) - 1) Div 2; Result := SLRtoLRS(copy(SLR, 2, Len)) + SLRtoLRS(copy(SLR, Len + 2, Length(SLR))) + SLR[1]; End; End;

Проверка:

SLRtoLRS("1245367") = "4526731"
LSRtoLRS("4251637") = "4526731"

>Alx2 © (04.03.05 08:31) [70]
эээ... для полного двоичного дерева (у которого все уровни заполнены) действительно достаточно одного из массивов узлов. А вот если оно неполное, придется для восстановления третьего массива использовать два первых.

>Alx2 © (04.03.05 07:26) [69]
>Tmp := Tmp^.Next^.Next;
Я бы не стал так делать, подозреваю, что в таком случае можно подобрать такую петлю, чтобы "быстрый" указатель всегда перепрыгивал через "медленный". Я бы сделал таким образом, чтобы "медленный" указатель шагал только по нечетным итерациям, в то время как "быстрый" шагает в каждой итерации.

С уважением.

wal © (04.03.05 8:56) [72]

Тоже было такое подозрение. Но оно пустое: в петле указатели всегда встретятся.

достаточно проверить систему
cos(t-alpha)=cos(2*t)
sin(t-alpha)=sin(2*t)

Решение:
t = -alpha+2*Pi*k где k - целое.

здесь alpha = 2*Pi*m/n задает начальное смещение двух указателей в петле относительно друг друга. Петля состоит из n звеньев. Значение alpha задает смещение "медленного" указателя на m звеньев относительно "быстрого" указателя в тот момент, когда они оба в петле.

Из решения следует, что указатели будут встречаться каждый оборот "медленного" указателя в звене с номером (n-m) (следует из t=2*Pi*(k-m/n)

красиво 6 решили

2.
Function SLR_LSR_to_LRS(Const SLR, LSR: String): String; Function toLRS(Var k: integer; Const SLR, LSR: String): String; Var idx: Integer; Begin If (k > Length(SLR)) Or (LSR = "") Then Result := "" Else Begin idx := pos(SLR[k], LSR); inc(k); Result := toLRS(k, SLR, Copy(LSR, 1, idx - 1)); Result := Result + toLRS(k, SLR, Copy(LSR, idx + 1, Length(LSR))) + LSR[idx]; End; End; Var k: Integer; Begin k := 1; Result := toLRS(k, SLR, LSR); End;

проверка:

SLR_LSR_to_LRS("1245367", "4251637")="4526731"

Alx2 © (04.03.05 9:53) [76]

2. Немножко повыкидывав мусор:

Function SLR_LSR_to_LRS(Const SLR, LSR: String): String; Var k, LenSLR: Integer; Function toLRS(Const LSR: String): String; Var idx: Integer; Begin If (k > LenSLR) Or (LSR = "") Then Result := "" Else Begin idx := pos(SLR[k], LSR); inc(k); Result := toLRS(Copy(LSR, 1, idx - 1)); Result := Result + toLRS(Copy(LSR, idx + 1, Length(LSR))) + LSR[idx]; End; End; Begin k := 1; LenSLR := Length(SLR); Result := toLRS(LSR); End;

>Alx2 © (04.03.05 09:53) [76]
Работает ;)

мой вариант (a,b: массивы SLR и LSR):

procedure Recurse(BStart, BEnd, APos: Integer); var Mid: Integer; begin if BStart > BEnd then Exit; if BStart = BEnd then begin Writeln( b[BStart] ); Exit; end; Mid := BStart; while a[APos] <> b[Mid] do Inc(Mid); Recurse(BStart, Mid - 1, APos + 1); Recurse(Mid + 1, BEnd, APos + Mid + 1); Writeln( b[Mid] ); end; вызов Recurse(0,n-1,0);

Четверговые задачки Найти похожие ветки