Непятничная задачка

← →
palva © (2005-02-14 16:41) [0]

Непятничная задачка.

Требуется хранить в файле большой массив, состоящий из перестановок чисел 0..255. В несжатом виде перестановка - это некий массив из 256 байтов с неповторяющимися значениями. Ясно, что в таком массиве имеется информационная избыточность. Скажем, последний байт массива можно не хранить, он вычисляется по значениям остальных байтов. Пока я придумал способ хранения, который требует 224 байта (вместо 256). Теоретическое минимальное значение log_2 256! / 8 байтов, что приближенно равно 210.4995. Как видите резерв имеется, но чтоб использовать этот резерв придется, наверно, придумывать алгоритмы, требующие существенно большего количества ресурсов.

У кого какие соображения? Попробуйте догадаться хотя бы, как сделать 224 байта.

← →
MBo © (2005-02-14 16:45) [1]

А есть ли необходимость действительно хранить сами эти перестановки? Понятно, что быстрее прочитать готовый массивчик, но не устроит ли генерация перестановки по ее номеру?

← →
Sandman25 © (2005-02-14 16:47) [2]

palva © (14.02.05 16:41)

128*8+64*7+32*6...+2*2+1=224 байта с копейками (битами)

---
к

← →
palva © (2005-02-14 16:48) [3]

> генерация перестановки по ее номеру?

Это идеальный вариант. Номер из диапазона 1..256! Только не могу предположить, какой может быть алгоритм генерации.

← →
wal © (2005-02-14 16:49) [4]

Хранить номер перестановки
256!=8,5781777534284265411908227168123e+506
Log2(256!)~=1684(бит)~=211(байт).

С уважением.

← →
palva © (2005-02-14 16:51) [5]

Sandman25 © (14.02.05 16:47) [2]
> 224 байта с копейками (битами)

По моим расчетам 223.5 Может я и ошибся...

← →
wal © (2005-02-14 16:52) [6]

Есть не очень сложный алгоритм, который создает "отсортированные" перестановки (каждая последующая "больше" предыдущей).

С уважением.

← →
MBo © (2005-02-14 17:30) [7]

Пардон, я сначала неправильно (в е раз меньше ;)) оценил размер буфера для хранения номера перестановки. Действительно, те же 211 байт потребуются, так что выигрыш от хранения номера вместо самой перестановки несущественный.

← →
default © (2005-02-14 18:03) [8]

перестановок по 2 элемента всего 256*255=65280
двумя байтами можно закодировать 2^16=65536 состояний
первые 65280 из них кодируют нужную перестановку из двух элементов
остаётся 65536 - 65280 = 256
то есть как раз достаточно для кодирования следующего элемента! таким образом 2 байтами кодируем 3 элемента перестановки!256/3=85.33...то есть экономим 85 байт!
итого 256-85=171 байт для кодирования...
рулёз!

← →
Sha © (2005-02-14 18:13) [9]

> default © (14.02.05 18:03) [8]

Можно подробнее, как именно двумя байтами кодируются 3 элемента?

← →
default © (2005-02-14 18:23) [10]

Sha © (14.02.05 18:13) [9]
два байта дают 65536 состояний
первыми 65280 кодируются два элемента всей перестановки
(путём указания её номера, таких номеров 65280)
посредством оставшихся 256 состояний кодируем следующий элемент перестановки после указанных двух
то есть кодируем тройками
я думаю этим алгоритмом далеко не ограничивается всё пространство решений этой задачи...есть думаю и эффективнее...
даже в этом алгоритме есть избыточность
поскольку после наступления какой-то перестановки она уже встретиться не может, но число бит под номер перестановки постоянно

← →
Sha © (2005-02-14 18:35) [11]

> default © (14.02.05 18:23) [10]

Не понял. Нельзя ли привести пример кодирования/декодирования?

← →
default © (2005-02-14 18:37) [12]

Sha © (14.02.05 18:35) [11]
если брать перестановки по 4 элемента и ещё маленькие нюансы можно сжать аж до 64 байт...
тут надо уже искать компросисс эффективности сжатия и скорости шифрации/дешифрации

← →
raidan © (2005-02-14 18:40) [13]

А если брать по 16 элементов?

← →
Sha © (2005-02-14 18:43) [14]

> default © (14.02.05 18:37) [12]

Опять не понял. Нельзя ли, наконец, привести пример кодирования/декодирования?

← →
raidan © (2005-02-14 18:45) [15]

Берем массив.
Упаковываем его.
Переставляем местами элементы.
Упаковываем его еще раз.
Еще раз переставляем местами элементы.
Продолжается до тех пор, пока не получим требуемый коэффициент сжатия.
Обратная задача - из 1 байта развернуть исходный массив.

← →
raidan © (2005-02-14 18:46) [16]

>palva © (14.02.05 16:41)
Кстати, что по этому поводу говорит winrar?
На сколько сжимает?

← →
Юрий Зотов © (2005-02-14 18:48) [17]

Или я чего-то не так понял, или Set of byte требует 32 байтов.

← →
default © (2005-02-14 18:49) [18]

возьму на примере меньшего числа элементов
пусть элементами перестановки будут числа 1,2,3,4
число перестановок по два элемента будет 4*3=12
пусть они занумерованы так:
1 1,2
2 1,3
3 1,4
4 2,1
5 2,3
6 2,4
7 3,1
8 3,2
9 3,4
10 4,1
11 4,2
12 4,3
нужно нам закодировать перестановку 1,3,2,4
1,3 - это перестановка двух элементов имеет номер 2
следующий элемент перестановки это 2, нумерация же кодирования третьего элемента тройки обычная: 1..4 в этом случае
значит первая тройка кодируется как 22 и тд по тройкам
понятно что мы не кодировали бы перестановки из 4 элементов так, но я на этом примере хотел пояснить кодирование при 256 элементах
но ка я говорил можно и эффективней кодировать тут уже надо искать приемлемую скорость декодирования

← →
palva © (2005-02-14 18:49) [19]

wal © (14.02.05 16:52) [6]
> Есть не очень сложный алгоритм, который создает "отсортированные" перестановки (каждая последующая "больше" предыдущей).

Да, помнится в учебнике Куроша по общей алгебре такой алгоритм излагался. Каждая перестановка получалась из предыдущей обменом двух соседних чисел. Надо вечером дома посмотреть.

← →
Sha © (2005-02-14 18:50) [20]

> Юрий Зотов © (14.02.05 18:48) [17]

Set - неупорядоченное множество,
Перестановка - упорядоченное.

← →
default © (2005-02-14 18:50) [21]

Юрий Зотов © (14.02.05 18:48) [17]
там сочетания, а не перестановки

← →
Sha © (2005-02-14 18:54) [22]

> default © (14.02.05 18:49) [18]
> значит первая тройка кодируется как 22 и тд по тройкам

Нет не как 22, а как 022 - всего 3 байта.

← →
default © (2005-02-14 19:07) [23]

Sha © (14.02.05 18:54) [22]
там принцип пояснён...
при 256 элементах тройка кодируется 2 байтами
вообщем работают алгоритмы такого рода...

← →
default © (2005-02-14 19:26) [24]

Sha © (14.02.05 18:54) [22]
да действительно, я ступил
считал состояния независимыми...

← →
palva © (2005-02-14 22:01) [25]

Пока ехал домой, придумал практический алгоритм, который позволяет использовать меньше 240 байтов.

Берем перестановку и кодируем по два байта. Первые два байта остаются без изменения. Следующие два байта заменяем на их номер среди тех байтов, которые еще не были закодированы. И так далее кодируем по два байта. Для примера рассмотрим начало перестановки
1, 2, 3, 4, 200, 12, ... - это исходная перестановка 1, 2, 1, 2, 196, 8, ... - это ее код (промежуточный)
Сразу можно сказать что если 2*n байтов уже закодировано, то следующие два кода не будут превышать 256-2*n. Следовательно для их записи потребуется уже не 8 битов, а вообще говоря меньше. Мы уже исследовали этот способ записи и определили, что он требует 240 байтов. Будем считать, что очередные два кода - запись некоторого числа в позиционной системе по основанию 256-2*n. Это число вначале потребует для своей записи 16 битов, потом, начиная с некоторого места 15 битов и т. д. Вот эти биты и будем накапливать как результат кодирования. Такой метод вырабатывает 1753 бита или 220 байтов. С раскодированием проблем не будет, поскольку местА, где число битов уменьшается на единицу могут быть вычислены заранее и фиксированы для данного алгоритма. Можно пойти дальше и кодировать не по 2 байта а по 4. Вычисления при кодировании здесь будут уже существенные - много умножений, но результат улучшится - 1698 битов 213 байтов. Наверно, можно кодировать и по 8 байтов - я не смотрел, будет лучше в этом случае или нет.

Выкладываю программу, считающую число битов при кодировании по 4.
{$APPTYPE CONSOLE} var i: Cardinal; sumofbits, max_number: Cardinal; function log2(n: Cardinal): Cardinal; var i, r: Cardinal; begin r := 0; for i := 1 to 32 do begin if Odd(n) then r := i; n := n shr 1; end; Result := r; end; begin sumofbits := 0; max_number := 256; for i := 0 to 63 do begin sumofbits := sumofbits + log2(max_number * max_number * max_number * max_number); max_number := max_number - 4; end; WriteLn(sumofbits, " ", (sumofbits + 7) div 8) // 1698 213 end.

← →
default © (2005-02-14 22:48) [26]

palva © (14.02.05 22:01) [25]
метод 224 байт допускает удобную практическую реализацию
всё зависит от интерпретации
выгодная интерпретация это понимать этот метод как постановку элемента 1 на одно из 256, далее 2 на одно из 255 мест и тд
ливидирую избыточность получим затраты [2]

← →
palva © (2005-02-14 23:05) [27]

default © (14.02.05 22:48) [26]
Да, вы совершенно правы, 224 легко достижимо. В своем последнем посте я ошибся и вместо 224 писал везде 240, т.е.

> ...который позволяет использовать меньше 240 байтов

> Мы уже исследовали этот способ записи и определили, что он требует 240 байтов.

Везде надо читать 224. Но сути это не меняет.

Первоначально задача и ставилась так, чтобы предложить практический способ сделать размер меньше чем 224. В моем последнем посте и предлагается алгоритм, дающий 220 и 213 байтов.

← →
default © (2005-02-14 23:08) [28]

объясните как вы получили 196, 8 из 200, 12(

← →
default © (2005-02-14 23:22) [29]

уже не надо

← →
default © (2005-02-15 01:06) [30]

palva © (14.02.05 22:01) [25]
"Следовательно для их записи потребуется уже не 8 битов, а вообще говоря меньше."
вы тут неверно сказали, надо было сказать - начиная с некоторого n
"Наверно, можно кодировать и по 8 байтов - я не смотрел, будет лучше в этом случае или нет."
странно что вы говорите НАВЕРНО если вы понимаете суть алгоритма вами же придуманного, конечно, будет!

математически можно суть пояснить так(это не для вас, а тем кто захочет понять откуда берётся избыточность и как это работает:)):
есть две двоичные записи чисел a и b прилегающие друг к другу, одна пусть кодируется na битами, другая - nb
причём оба числа не максимальны и вдобавок имеют ещё границу m - свою на каждом шаге алгоритма - она на каждом шаге в данном случае будет уменьшаться на 2
то есть: a<=m-1<2^na-1 и b<=m-1<2^nb-1
(m-1 используется поскольку считаем с 0)
(по сути своей это и есть условие избыточности!
не было бы его не было бы и алгоритма palva!тут возникает своеобразная битовая разрозненность, мы уплотнением и достигнем сжимаемости!)
число m определяется шагом алгоритма как уже говорилось - это число max_number в алгоритме
ясно что на оба числа расходуется na + nb бит в этом случае
но исходя из условия избыточности битами na и nb реальнобудут задаваться только m^2 чисел, а не 2^na*2^nb=2^(na+nb) если бы на a и b не были бы наложены условия избыточности
для m^2 чисел требуется лишь Log2(m^2) бит, а для
2^(na+nb) - na+nb
ясно отсюда что поскольку при каждом шаге алгоритма m уменьшается(при постоянстве na и nb) значит будет и уменьшаться Log2(m^2)
это приведёт к тому что начиная с некоторого шага алгоритма
m настолько уменьшится что мы будем иметь возможность получить экономию бит

← →
Alex Konshin © (2005-02-15 01:13) [31]

Любую комбинацию 256 чисел можно представить в виде перестановок. Такое ощущение, что должно быть достаточно 32 байт.

← →
default © (2005-02-15 01:16) [32]

palva © (14.02.05 23:05) [27]
поздавляю с находкой отличного алгоритма:)точнее целого класса:)

← →
default © (2005-02-15 01:21) [33]

Alex Konshin © (15.02.05 01:13) [31]
см [17] потом [20]

← →
palva1 (2005-02-15 10:09) [34]

default © (15.02.05 01:06) [30]
Я написал наверно по следующей причине. Из кодируемой группы байтов только первый действительно может достигать верхней границы, а второй и следующие - нет. Здесь возникает некоторая избыточность, поскольку интерпретация этой группы, как записи числа в позиционной системе позволяет кодировать некоторые недопустимые наборы байтов. Эта избыточность тем больше, чем больше байтов в группе, причем растет довольно быстро (навскидку - по экспоненте). Поэтому я так осторожничаю с числом 8. Но на самом деле это недолго проверить - изменить в выложенной программе несколько строк и запустить. Может быть я сегодня днем попробую это сделать и выложить результат. Сейчас - недосуг.

← →
Sha © (2005-02-15 10:46) [35]

> palva1 (15.02.05 10:09) [34]
> Поэтому я так осторожничаю с числом 8.

Можно смело разбивать на группы с любым количеством элементов, если немного подправить веса разрядов.
Например, для четверок можно использовать такие веса:

i*(i+1)*(i+2)*a[i+3]+i*(i+1)*a[i+2]+i*a[i+1]+a[i]

Здесь для удобства элементы нумеруются в обратном порядке,
так, что 1<=a[i]<=i, (первый элемент имеет номер 256).

← →
Sha © (2005-02-15 10:53) [36]

Поправка:
Здесь для удобства элементы нумеруются в обратном порядке,
так, что 0<=a[i]<i, (первый элемент имеет номер 255).

← →
default © (2005-02-15 12:10) [37]

palva1 (15.02.05 10:09) [34]
увеличение качества сжимаемости при увеличении численности группы кодировки почти очевидно
в пределе когда группа равна 256 мы как раз и получим теорграницу в 211 байт при остальных же группах затраты будут стремиться к этой границе при увеличении численности группы
почему очевидно?
да очень просто(можно это и математически доказать)
возьмём кодирование 6 элементов перестановки по 2 и по 3 элемента в группе
1 2|3 4|5 6 кодирование по 2
мы уплотнили код элементов 1,2; 3,4; 5,6
уплотнения же между элементами 2,3 и 4,5 НЕТ!
1 2 3|4 5 6 кодирование по 3
мы уплотнили элементы 1,2,3 и 4,5,6
но уплотнения элементов 3,4 НЕТ!
но тут нет одного уплотнения, а в предыдущем случае двух - отсюда и стремление к теоргранице при возрастании численности групп

← →
SergP. (2005-02-15 12:28) [38]

ИМХО максимум что можно выжать:

кол. байт = (log_2(256!))/8

Сколько это будет - х/з, не считал...

← →
Sha © (2005-02-15 12:35) [39]

> palva © (14.02.05 22:01) [25]

В программе имеется неточность: аргумент при первом вызове Log2 равен 256^4=0. После исправления

sumofbits := sumofbits + log2(max_number * (max_number-1) * max_number * max_number);

получаем результат 1724/216.

Предложенное в [34] усовершенствование позволяет сэкономить
еще одит байт (1713/215).

← →
Sha © (2005-02-15 12:45) [40]

> default © (15.02.05 12:10) [37]
> отсюда и стремление к теоргранице при возрастании численности групп

Все не так просто. Общая тенденция, конечно, имеется. Но не факт, что всегда для больших групп результат будет лучше, чем для меньших.

← →
default © (2005-02-15 12:48) [41]

Sha © (15.02.05 12:45) [40]
надо
max_number * (max_number-1) *
(max_number-2) * (max_number-3)
при групировках общее число сэконемленных бит равно но поскольку разрозненность сплотнения этих бит разная то и сжимаемость разная
и факт что будет всегда рост

← →
default © (2005-02-15 12:55) [42]

Sha © (15.02.05 12:45) [40]
"при групировках общее число сэконемленных бит равно но поскольку разрозненность сплотнения этих бит разная то и сжимаемость разная"
расплывчатая фраза но я думаю вы поняли о чём я
при перестановках по 2 и по 3 имеем затраты бит
Log2[m(m-1)]+Log2[(m-2)(m-3)]+Log2[(m-4)(m-5)]=
Log2[m(m-1)(m-2)]+Log2[(m-3)(m-4)(m-5)]
как вижно нужное число бит одинаково - оптимум, НО за счёт разрозенности сплотнения имеем ситуацию [37]

← →
Sha © (2005-02-15 13:09) [43]

> default © (15.02.05 12:48) [41]
> надо
> max_number * (max_number-1) * (max_number-2) * (max_number-3)

Ну так это другое кодирование: не [34], а [35] :)

а твой пост default © (15.02.05 12:10) [37] относился
к palva1 (15.02.05 10:09) [34]

Sha © (15.02.05 13:09) [43]
так я так и думал давно:)хотя писал m^2 вместо m(m-1) в посте [30]
это была просто невнимательность
сути дела о чём там говорится это не меняет
так вы ещё сомневаетесь в том что рост очевиден?
логарифмов не хватило?:) понятно что если мы одном месте будем копить состояния лишние, то быстрее экономию бит получить нежели эти состоянии будут копиться не в одном месте
вот так на словах смысл таков
или математически через логарифмы - чем больше округлений тем больше нужно бит а округлений тем больше чем на меньшие грцппы мы разбиваем исходную перестановку

> default © (15.02.05 13:17) [44]
> так вы ещё сомневаетесь в том что рост очевиден?

Вовсе нет, см. [40].

Я хочу только, чтобы ты понял, что примерами в математике можно доказать существование, а не всеобщность :)

Sha © (15.02.05 13:23) [45]
считаете что возможны выражения вида?
Round(Log2[m(m-1)])+Round(Log2[(m-2)(m-3)])+Round(Log2[(m-4)(m-5)]) <=
Round(Log2[m(m-1)(m-2)])+Round(Log2[(m-3)(m-4)(m-5)])
?
Round тут округление в ближайшему большему целому

> default © (15.02.05 13:37) [46]
> считаете что возможны выражения вида?
> Round(Log2[m(m-1)])+Round(Log2[(m-2)(m-3)])+Round(Log2[(m-4)(m-5)]) <=
> Round(Log2[m(m-1)(m-2)])+Round(Log2[(m-3)(m-4)(m-5)])
> Round тут округление в ближайшему большему целому

Возможность записи не отрицаю.
Истинность надо доказывать.
Но нам не эти выражения нужны.
Твое утверждение было не относительно этих, может быть истинных для любого m, выражений.
Оно касалось нашей конкретной задачи. А для нее даже пользуясь хорошими формулами из-за краевых условий (например 256 на 9 не делится, а на 8 делится) мы можем получить неоптимальный результат.

> Sha © (15.02.05 13:53) [47]
Есть более тонкие причины.
В общем, для доказательства или опровержения гипотезы в нашем случае проще написать программу.

Я попробовал с группами по 8. Получилось 1786 224 - такие пироги.

Вот программа, походил по ней отладчиком. Надеюсь, не ошибся, как в прошлый раз.
{$APPTYPE CONSOLE} var i: Cardinal; sumofbits, max_number: Integer; function log2(n: int64): Integer; var i, r: Integer; begin r := 0; for i := 1 to 64 do begin if Odd(n) then r := i; n := n shr 1; end; Result := r; end; var i64: Int64; begin sumofbits := 0; max_number := 256; for i := 0 to 32 do begin i64 := max_number * max_number; i64 := i64*i64; i64 := i64*i64 - 1; if i64 <= 0 then sumofbits := sumofbits + 64 else sumofbits := sumofbits + log2(i64); max_number := max_number - 8; end; WriteLn(sumofbits, " ", (sumofbits + 7) div 8) // 1698 213 end.
Сразу можно высказать соображение, что избыточность зависит не только от размера группы, но и от основания системы счисления. Поэтому выгодно в начале алгоритма работать группами меньшего размера, а дальше увеличивать размер группы. Размер группы тоже не обязательно должен быть степенью двойки. Возможно, существует какая то оптимальная последовательность: сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д.

В третьей строчке Cardinal нелогично. Нужно заменить на Integer. Да и комментарий в предпоследней строчке устарел...

> palva © (15.02.05 14:13) [49]
> Я попробовал с группами по 8. Получилось 1786 224 - такие пироги.

Я тоже попробовал по варианту [35]: 1699/213

program CodePerm3; {$APPTYPE CONSOLE} function ilog2(c: int64): cardinal; begin; Result:=0; while c<>0 do begin; c:=c shr 1; inc(Result); end; end; var i, maxi: integer; bits, c, t: int64; begin; maxi:=4; //2:1743/218 4:1713/215 8:1699/213 bits:=0; c:=256; while c>0 do begin; t:=1; for i:=1 to maxi do begin; if c=0 then break; t:=t*c; c:=c-1; end; bits:=bits + ilog2(t-1); end; writeln(bits, " ", (bits + 7) div 8); readln; end.

palva © (15.02.05 14:38) [50]
теперь я понял ваше наверно
вы зачем-то рассматриваете комбинации к примеру m^4 когда возможно только m(m-1)(m-2)(m-3) комбинаций
сами внося этим ненужную избыточность...
Sha © (15.02.05 14:05) [48]
вообщем согласен с [40]

palva © (15.02.05 14:13) [49]
" Возможно, существует какая то оптимальная последовательность: сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д."
ясно что чем больше групп с большим число элементов тем лучше - как минимум общая тенденция таково - что так всегда - всё-таки нужно доказать

> palva © (15.02.05 14:13) [49]
> Возможно, существует какая то оптимальная последовательность:
> сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д."

> default © (15.02.05 14:55) [53]

Есть интересная модификация [35]: "набивание под завязку".
В этом варианте мы четырьмя байтами кодируем столько, сколько сможем. При этом получаем высокую степень упаковки (1710/214) и высокую скорость.

program CodePerm2; {$APPTYPE CONSOLE} uses SysUtils; function ilog2(c: int64): cardinal; begin; Result:=0; while c<>0 do begin; c:=c shr 1; inc(Result); end; end; var max, bits, c, t: int64; begin; max:=$FFFFFFFF; bits:=0; c:=256; while c>0 do begin; t:=1; while max div t >= c do begin; if c=0 then break; t:=t*c; c:=c-1; end; bits:=bits + ilog2(t-1); end; writeln(bits, " ", (bits + 7) div 8); readln; end.

default © (15.02.05 14:51) [52]
> вы зачем-то рассматриваете комбинации к примеру m^4 когда возможно только m(m-1)(m-2)(m-3) комбинаций

Настало просветление. Я просто не видел хорошего алгоритма для устранения этой избыточности. Например, кодирую 3-й и 4-й байты 120, 23. Первый из них не больше чем 254, второй не больше чем 253. Я кодирую их как 254*120+23. Теперь, когда я стал отвечать, я увидел правильный алгоритм. Это надо кодировать как 253*120+23. Тогда, конечно, чем длиннее группа, тем выгоднее.

Мне мешала усвоенная очень давно идея позиционной системы счисления.

> default ©

Это интересно:

1. При кодировании с набиванием под завязку по 63 бита (max:=$7FFFFFFFFFFFFFFF;) мы получаем результат 1696/212, очень близкий к теоретическому минимуму (210).

2. Кодирование с набиванием под завязку по 60 битов (max:=$0FFFFFFFFFFFFFFF;) дает лучшее сжатие (1698/213),
чем по 61 биту (max:=$1FFFFFFFFFFFFFFF;) (1699/213), что противоречит твоим ожиданиям.

3. Еще более поразительно то, что результат для 54-битного кодирования (max:=$003FFFFFFFFFFFFF;) (1697/213) лучше, чем для
62-битного (max:=$3FFFFFFFFFFFFFFF;) (1698/213).

Да, интересно.

Sha © (15.02.05 16:02) [56]
хех:)это мне урок на счёт очевидности:)
я вот щас подумываю над доказательство и как паз не вижу безоговорочности роста сжатия при увеличении размеры группы
теперь интересно определить условия при которых "меньшее" кодировании имеет верх над "большим"

default © (15.02.05 16:48) [59]

Причина кроется в "более полном" использовании битов в целом по всем группам.

Количество неполнот может быть большим, но если их величина мала, то суммарная неполнота может оказаться небольшой.

Так устроен мир :)

Sha © (15.02.05 16:56) [60]
это понятно, я хотел какие-нибудь формулы найти для этого...да думаю и смысла-то в этом нет, проще вышеприведёнными алгоритмами проверить

Непятничная задачка Найти похожие ветки