Текущий архив: 2005.03.20;
Скачать: CL | DM;
Вниз
Четверговые задачки Найти похожие ветки
← →
MBo © (2005-03-03 10:11) [0]1. В тёмной комнате стоит стол, на котором лежат монеты - 5 решкой и 8 орлом.
Нужно разделить их на 2 кучки таким образом, чтобы в каждой оказалось одинаковое количество решек.
Монетки можно переворачивать. Монеты на ощупь одинаковые.
2. Есть бинарное дерево без повторяющихся элементов.
Известно, что есть 3 различных вида обхода вершин дерева (в глубину):
a)self-left-right
b)left-self-right
c)left-right-self
Если мы обойдем одним способом дерево с N вершинами и запишем номера вершин в порядке
обхода, то у нас будет массив чисел размера N.
Теперь собственно задача: имея два массива номеров вершин, полученных при обходе
способами a и b, требуется получить массив номеров вершин, соответствующий
третьему виду обхода.Пример для такого дерева1
2 3
4 5 6 7
а) 1 2 4 5 3 6 7
b) 4 2 5 1 6 3 7
нужно получить
c) 4 5 2 6 7 3 1
3. Дана бесконечная пирамида уравнений:
A * N = BC
AD * N = BBC
ADD * N = BBBC
ADDD * N = BBBBC
и т.д. ......
Найти N - натуральное число, A,B,C,D - различные цифры.
4. Для какого минимального натурального M число M^2003+1 делится на 2^N?
5. Как удалить узел из односвязного списка, имея только указатель на него?
На голову списка или пред. узел указателей нет. Известно, что узел не последний.
6. Как найти, не зациклен ли односвязный список, не используя много памяти?
7. Код Грея представляет собой целочисленную последовательность G(N), такую, что каждый
член отличается от предыдущего только одним битом. Первые 16 в бинарном виде:
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Написать функции преобразования N в G(N) и обратную ей.
← →
wal © (2005-03-03 10:18) [1]4. M=1; 1^2003+1=2; (2 mod (2^1))=0 :)
← →
Думкин © (2005-03-03 10:23) [2]> [1] wal © (03.03.05 10:18)
Видимо имелось в виду M(N)=?
← →
wal © (2005-03-03 10:40) [3]7. BinToGray:
G[0]:=B[0] xor B[1]
G[i]:=B[i] xor B[i+1]
Где операция [] обозначает номер бита.
Если короче, то G:=B xor (B shr 1);
GrayToBin пока красиво не придумал.
С уважением.
← →
Alx2 © (2005-03-03 10:47) [4]7. G(n) = n xor (n shr 1) это уже написал wal.
Обратно:
N := G;
while G>0 do
begin
G := G shr 1;
N := N xor G;
end;
← →
Vlad Oshin © (2005-03-03 10:53) [5]
> 1. В тёмной комнате стоит стол, на котором лежат монеты
> - 5 решкой и 8 орлом.
> Нужно разделить их на 2 кучки таким образом, чтобы в каждой
> оказалось одинаковое количество решек.
> Монетки можно переворачивать. Монеты на ощупь одинаковые.
-------
разделить их на 2 кучки таким образом,5 и 8
переворачивать все 5
← →
Cosinus © (2005-03-03 11:06) [6]
> Vlad Oshin © (03.03.05 10:53) [5]
ЧЁ-то я не догнал... А можно поподробнее?
← →
Vlad Oshin © (2005-03-03 11:16) [7]
> разделить их на 2 кучки таким образом, 5 и 8 монет
где 5 - все перевернуть
← →
Cosinus © (2005-03-03 11:30) [8]
> Vlad Oshin © (03.03.05 11:16) [7]
А-а-а... Понял.
← →
Alx2 © (2005-03-03 11:41) [9]3.
A=1 B=3 C=2 D=6
N =2
← →
Alx2 © (2005-03-03 11:42) [10]Пост Alx2 © (03.03.05 11:41) [9] не считается :)
Поторопился. Сорри.
← →
Vlad Oshin © (2005-03-03 11:45) [11]кто бы 6 решил
интересно посмотреть, как это сделать...
← →
Kaban (2005-03-03 11:49) [12]5. Сдвинуть все следующие элементы списка и удалить последний
← →
Диссидент © (2005-03-03 11:51) [13]Kaban (03.03.05 11:49) [12]
Явно неверный ответ.
← →
Диссидент © (2005-03-03 11:53) [14]6. Может добавить в список временно свой элемент. Пробежать по списку и, если встретим свой элемент, то список зациклен.
← →
Vlad Oshin © (2005-03-03 11:57) [15]
> Диссидент © (03.03.05 11:51) [13]
> Явно неверный ответ.
почему?
если, наверное, имелось ввиду сдвинуть информативную часть элементов, не трогая ссылки.
← →
Диссидент © (2005-03-03 11:58) [16]Vlad Oshin © (03.03.05 11:57) [15]
если, наверное, имелось ввиду сдвинуть информативную часть элементов, не трогая ссылки.
АА.. тогда примите извинения :)
← →
Kaban (2005-03-03 11:58) [17]6. По тупому:
количество_памяти / размер_узла = максимальное_количество_узлов
если удасться сдвинуться на максимальное_количество_узлов значит есть цикл
← →
Kaban (2005-03-03 11:59) [18]в 5, очевидно, речь шла про информационную часть
← →
Kaban (2005-03-03 12:01) [19]добавить свой элемент не получится, цикл может быть таким:
ваш. эл.
---V-----------------() <-цикл
← →
Vlad Oshin © (2005-03-03 12:02) [20]
> Диссидент © (03.03.05 11:58) [16]
а Вам - мои поздравления :) за
> [14]
← →
Vlad Oshin © (2005-03-03 12:04) [21]Kaban (03.03.05 12:01) [19]
добавить свой элемент не получится, цикл может быть таким:
ваш. эл.
---V-----------------() <-цикл
тогда nil известен, значит не зациклен
← →
Vlad Oshin © (2005-03-03 12:09) [22]
> Vlad Oshin © (03.03.05 12:04) [21]
не понял сам себя:)
проблема в крайних элементах?
тогда надо добавить после второго рассматриваемого, если он не конечный
← →
wal © (2005-03-03 12:17) [23]>Vlad Oshin © (03.03.05 11:45) [11]
>кто бы 6 решил
Я решил, но ответа пока не дам :Р
← →
wal © (2005-03-03 12:24) [24]>Vlad Oshin © (03.03.05 12:04) [21]
>тогда nil известен, значит не зациклен
Цикл не обязательно может быть на начало.
Например 0-1-2-3-4-5-6-3-... , и куда в таком случае "свой" элемент вставить?
← →
Vlad Oshin © (2005-03-03 12:38) [25]
> wal © (03.03.05 12:24) [24]
> Kaban (03.03.05 12:01) [19]
понял...
жаль..
← →
MBo © (2005-03-03 12:45) [26]1. Vlad Oshin © (03.03.05 10:53) [5]
>разделить их на 2 кучки таким образом,5 и 8
>переворачивать все 5
Верно
7. wal, Alx2 - верно
← →
MBo © (2005-03-03 12:48) [27]5. - мысли прозвучали, но четкого ответа пока нет.
2,3,4,5,6 - не решено пока
← →
GuAV © (2005-03-03 13:06) [28]MBo © (03.03.05 10:11)
5. Как удалить узел из односвязного списка, имея только указатель на него?
На голову списка или пред. узел указателей нет. Известно, что узел не последний.
Скопировать следующий за удаляемым узлом в удаляемый узел и удалить старый следующий узел
MBo © (03.03.05 10:11)
6. Как найти, не зациклен ли односвязный список, не используя много памяти?
Запомнить указатель на узел. Идти к последнему элементу, сравнивая указатель с запомненым. Нашли запомненый - зациклен. Нашли последний - не зациклен.
← →
Диссидент © (2005-03-03 13:09) [29]GuAV © (03.03.05 13:06) [28]
Запомнить указатель на узел.
Это сколько ж указателей придется хранить?
← →
Kaban (2005-03-03 13:10) [30]2 GuAV © (03.03.05 13:06) [28]
Если бы 6 решалась так легко, ее бы не задали :)
← →
Alx2 © (2005-03-03 13:11) [31]3.
Три решения:
1) N=8, a=8 b=6 c=4 d=3
2) N=12, a=8 b=9 c=6 d=3
3) N=25, a=3 b=7 c=5 d=1
← →
GuAV © (2005-03-03 13:18) [32]Ага, понял. Надо проходит список, заменяя указатели на следующий указателями на предыдущи Если в следующем уже указатель на предыдущий, то зациклен, если нашли последний то нет.
← →
MBo © (2005-03-03 13:20) [33]GuAV © (03.03.05 13:06) [28]
5. Скопировать следующий за удаляемым узлом в удаляемый узел и удалить старый следующий узел
Да, верно. Идея уже всплывала в [12], но неполноценно
6. неверно. цикл, как уже говорили, может начаться в любом месте
Alx2 © (03.03.05 13:11) [31]
3.Три решения:
Правильно
← →
Alx2 © (2005-03-03 13:30) [34]4.
M = 2^N-1
← →
Alx2 © (2005-03-03 13:36) [35]6.
Памяти мало, но времени - квадратично от длины списка.
Начиная с первого узла запомниаем его адрес, и бежим по списку пока не конец, или пока не встретится вновь этот адрес. Встретился - значит цикл.
Потом со второго узла и т.д. Но по времени - ужас :))
← →
wal © (2005-03-03 13:39) [36]>Alx2 © (03.03.05 13:36) [35]
>Встретился - значит цикл.
А если не встретился ни конец ни первый узел - крутимся до скончания времен.
← →
Alx2 © (2005-03-03 13:41) [37]wal © (03.03.05 13:39) [36]
Действительно. Тормознул я.
← →
MBo © (2005-03-03 13:41) [38]>Alx2 © (03.03.05 13:30) [34]
>4. M = 2^N-1
Верно
Возможное решение: M^2003 известным способом раскладывается на множители, первый из которых (M+1), а второй состоит из 2002 слагаемых-степеней M и единички, т.е. всегда нечетен.
>Alx2 © (03.03.05 13:36) [35]
Сам понимаешь - не наш это метод ;)
← →
GuAV © (2005-03-03 13:52) [39][32] + для восстановления списка идти от последнего к исходному (исходный запомнить), заменяя обратно.
← →
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. я не о том что мне надо объяснить, я понял, я вообще
← →
Alx2 © (2005-03-03 18:14) [67]>default © (03.03.05 17:56) [66]
Вообще-то идею объяснил в посте Alx2 © (03.03.05 15:42)
У MBo несколько другой: по списку идут два указателя с разной скоростью. Когда встретятся - есть цикл.
У меня же неявно ищется число, кратное периоду цикла (переменная M). В конечном итоге суть такая же, что и у MBo.
← →
default © (2005-03-03 19:36) [68]Alx2 © (03.03.05 18:14) [67]
мне в посте [61] "k:=k+M" не сразу ясно стало
а так красивый алгоритм:)
← →
Alx2 © (2005-03-04 07:26) [69]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;
← →
Alx2 © (2005-03-04 08:31) [70]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"
← →
MBo © (2005-03-04 08:50) [71]>Alx2 © (04.03.05 08:31) [70]
эээ... для полного двоичного дерева (у которого все уровни заполнены) действительно достаточно одного из массивов узлов. А вот если оно неполное, придется для восстановления третьего массива использовать два первых.
← →
wal © (2005-03-04 08:56) [72]>Alx2 © (04.03.05 07:26) [69]
>Tmp := Tmp^.Next^.Next;
Я бы не стал так делать, подозреваю, что в таком случае можно подобрать такую петлю, чтобы "быстрый" указатель всегда перепрыгивал через "медленный". Я бы сделал таким образом, чтобы "медленный" указатель шагал только по нечетным итерациям, в то время как "быстрый" шагает в каждой итерации.
С уважением.
← →
Alx2 © (2005-03-04 09:07) [73]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)
← →
Alx2 © (2005-03-04 09:19) [74]MBo © (04.03.05 8:50) [71]
Ага, действительно...
← →
Vlad Oshin © (2005-03-04 09:22) [75]красиво 6 решили
← →
Alx2 © (2005-03-04 09:53) [76]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 © (2005-03-04 10:08) [77]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;
← →
MBo © (2005-03-04 10:09) [78]>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);
Страницы: 1 2 вся ветка
Текущий архив: 2005.03.20;
Скачать: CL | DM;
Память: 0.68 MB
Время: 0.045 c