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

← →
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. Как найти, не зациклен ли односвязный список, не используя много памяти?
Запомнить указатель на узел. Идти к последнему элементу, сравнивая указатель с запомненым. Нашли запомненый - зациклен. Нашли последний - не зациклен.

← →
Kaban (2005-03-03 13:10) [30]

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 © (03.03.05 13:06) [28]
5. Скопировать следующий за удаляемым узлом в удаляемый узел и удалить старый следующий узел

Да, верно. Идея уже всплывала в [12], но неполноценно
6. неверно. цикл, как уже говорили, может начаться в любом месте

Alx2 © (03.03.05 13:11) [31]
3.Три решения:

Правильно

4.

M = 2^N-1

6.
Памяти мало, но времени - квадратично от длины списка.

Начиная с первого узла запомниаем его адрес, и бежим по списку пока не конец, или пока не встретится вновь этот адрес. Встретился - значит цикл.
Потом со второго узла и т.д. Но по времени - ужас :))

>Alx2 © (03.03.05 13:36) [35]
>Встретился - значит цикл.
А если не встретился ни конец ни первый узел - крутимся до скончания времен.

>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]
Сам понимаешь - не наш это метод ;)

[32] + для восстановления списка идти от последнего к исходному (исходный запомнить), заменяя обратно.

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