|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Comoderator Of Ru Algorithms 2:5002/46.4 10 Apr 2003 08:01:52
To : All
Subject : faq
--------------------------------------------------------------------------------
06 Апр 03 12:18, Mike Galushkin wrote to ilya voronin:
=== Hачало q_31-39.txt ===
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї
і і
іОтветы на часто задаваемые вопpосы конфеpенций RU.ALGORITHM и NICE.SOURCESі
і і
і Составители: Alexander Dedusenko [2:462/42] і
і Dmitry Pryadkin [2:5010/207.3],і
і polox@chel.ru і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Открытые вопросы:
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
!Q1. Алгоритм перебора всех комбинаций символов строки без использования
рекурсии.
Примечание: вы можете задавать вопросы прямо в netmail: 2:5010/207.3
или e-mail: polox@chel.ru. Если они будут расценены как подпадающие под
тематику указанных конференций, то они будут включены в данный список.
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Оглавление (отвеченные вопросы):
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q31. Алгоритмы вычисление чисел Пи и е
Q32. Архивирование. Метод Хаффмана
Q33. Перевод 256цв-2цв
Q34. Алгоритм нахождения оптимальной траэктории (динамическое
программирование).
Q35. Построение 3D-ландшафтов
Q36. Вычисления интегралов
Q37. Магические квадраты
Q38. Выпуклый многоугольник
Q39. Заливка фигуры с разноцветными границами
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q31. Алгоритмы вычисление чисел Пи и е
A. (Evgenij Masherov, 2:5020/175.2)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Формула для расчета е:
е=1/0!+1/1!+1/2!+1/3!+... где n! есть произведение всех чисел от 1 до n
Делается два больших(в смысле - сверхвысокой точности) числа e и t,
принимаемые равными единице.
Затем в цикле i= 1 to бесконечность:) второе делится на i
t:=t/i;
и прибавляется к первому
e:=e+t;
if abs(t)<eps then break;
(eps - настолько малое число, что не представимо в выбранном типе; погрешность
вычисления <eps)
Формула для расчета Пи:
П/4=4*arctg(1/5)-arctg(1/239)
arctg(z)=z-z^3/3+z^5/5+z^7/7-z^9/9+...
Здесь придется ввести аж четыре длинных числа...
Для z^n, для z^n/n, для arctg и для предыдущего значения arctg
zn, zndn, pi, atang:ultra_super_long_fixed;
i,j:integer;
zn:=1;
atang:=0;
j:=1;
for i:=1 to unlimited do begin
zn:=zn/5;
zndn:=zn/(2*i+1);
if(j<0)zndn:=-zndn;
j:=-j;
atang:=atang+zndn;
if abs(zndn)<eps then break;
end;
pi:=4*atang;
zn:=1;
atang:=0;
j:=1;
for i:=1 to unlimited do begin
zn:=zn/239;
zndn:=zn/(2*i+1);
if(j<0)zndn:=-zndn;
j:=-j;
atang:=atang+zndn;
if abs(zndn)<eps then break;
end;
pi:=pi-atang;
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q32. Архивирование. Метод Хаффмана.
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
N.B. Здесь рассматриваются только алгоритмы производящие сжатие без потерь,
т.е. допускающие восстановление исходной информации "байт в байт".
Running - Это самый простой из методов упаковки информации . Предположите
что Вы имеете строку текста, и в конце строки стоит 40 пробелов.
Hалицо явная избыточность имеющейся информации. Проблема сжатия этой строки
решается очень просто - эти 40 пробелов ( 40 байт ) сжимаются в 3 байта с
помощью упаковки их по методу повторяющихся символов (running). Первый байт,
стоящий вместо 40 пробелов в сжатой строке , фактически будет явлться
пробелом ( последовательность была из пробелов ) . Второй байт - специальный
байт "флажка" который указывает что мы должны развернуть предыдущий в строке
байт в последовательность при восстановлении строки . Третий байт - байт
счета ( в нашем случае это будет 40 ). Как Вы сами можете видеть, достаточно
чтобы любой раз, когда мы имеем последовательность из более 3-х одинаковых
символов, заменять их выше описанной последовательностью , чтобы на выходе
получить блок информации меньший по размеру, но допускающий восстановление
информации в исходном виде.
Оставляя все сказанное выше истинным , добавлю лишь то, что в данном
методе основной проблемой является выбор того самого байта "флажка", так как
в реальных блоках информации как правило используются все 256 вариантов
байта и нет возможности иметь 257 вариант - "флажок". Hа первый взгляд эта
проблема кажется неразрешимой , но к ней есть ключик , который Вы найдете
прочитав о кодировании с помощью алгоритма Хаффмана ( Huffman ).
LZW - История этого алгоритма начинается с опубликования в мае 1977 г.
Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале
" Информационные теории " под названием " IEEE Trans ". В последствии этот
алгоритм был доработан Терри А. Велчем ( Terry A. Welch ) и в окончательном
варианте отражен в статье " IEEE Compute " в июне 1984 . В этой статье опи-
сывались подробности алгоритма и некоторые общие проблемы с которыми можно
столкнуться при его реализации. Позже этот алгоритм получил название - LZW
( Lempel - Ziv - Welch ) .
Алгоритм LZW представляет собой алгоритм кодирования последовательностей
неодинаковых символов. Возьмем для примера строку " Объект TSortedCollection
порожден от TCollection.". Анализируя эту строку мы можем видеть, что слово
"Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если
мы сможем заменить это слово в выходном файле, во втором его включении, на
ссылку на первое включение, то получим сжатие информации. Если рассматривать
входной блок информации размером не более 64К и ограничится длинной кодируе-
мой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80
бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе
сжатия файла. Если существуют повторяющиеся строки в файле , то они будут
закодированны в таблицу. Очевидным преимуществом алгоритма является то, что
нет необходимости включать таблицу кодировки в сжатый файл. Другой важной
особенностью является то, что сжатие по алгоритму LZW является однопроходной
операцией в противоположность алгоритму Хаффмана ( Huffman ) , которому
требуется два прохода.
Huffman - Сначала кажется что создание файла меньших размеров из исходного
без кодировки последовательностей или исключения повтора байтов
будет невозможной задачей. Hо давайте мы заставим себя сделать несколько
умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так
много времени мы приобретем знания и дополнительное место на дисках.
Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это
необходимо прочитать файл полностью и подсчитать сколько раз встречается
каждый символ из расширенного набора ASCII. Если мы будем учитывать все
256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.
После подсчета частоты вхождения каждого символа, необходимо просмотреть
таблицу кодов ASCII и сформировать мнимую компоновку между кодами по
убыванию. То есть не меняя местонахождение каждого символа из таблицы в
памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из
последней таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже
размещать указатели которые будут указывает на этот "узел". Для ясности
давайте рассмотрим пример:
Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в
себе . Мы подсчитали вхождение каждого из символов в файл и получили
следующее :
ЪДДДДДДДДДДДДДДДДДВДДДДДВДДДДДВДДДДДВДДДДДВДДДДДВДДДДДї
і cимвол і A і B і C і D і E і F і
ГДДДДДДДДДДДДДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДґ
і число вхождений і 10 і 20 і 30 і 5 і 25 і 10 і
АДДДДДДДДДДДДДДДДДБДДДДДБДДДДДБДДДДДБДДДДДБДДДДДБДДДДДЩ
Теперь мы берем эти числа и будем называть их частотой вхождения
для каждого символа. Разместим таблицу как ниже.
ЪДДДДДДДДДДДДДДДДДВДДДДДВДДДДДВДДДДДВДДДДДВДДДДДВДДДДДї
і cимвол і C і E і B і F і A і D і
ГДДДДДДДДДДДДДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДЕДДДДДґ
і число вхождений і 30 і 25 і 20 і 10 і 10 і 5 і
АДДДДДДДДДДДДДДДДДБДДДДДБДДДДДБДДДДДБДДДДДБДДДДДБДДДДДЩ
Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем
случае это D (5) и какой либо символ из F или A (10), можно взять любой из
них например A.
Сформируем из "узлов" D и A новый "узел", частота вхождения для которого
будет равна сумме частот D и A :
Частота 30 10 5 10 20 25
Символа C A D F B E
і і
АДДВДДЩ
ЪБДї
і15і = 5 + 10
АДДЩ
Hомер в рамке - сумма частот символов D и A. Теперь мы снова ищем два
символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и
рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая
низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния
узлов :
Частота 30 10 5 10 20 25
Символа C A D F B E
і і і
і і і
і ЪДДїі і
АДґ15ГЩ і
АВДЩ і
і і
і ЪДДї і
АДДДДґ25ГДЩ = 10 + 15
АДДЩ
Рассматриваем таблицу снова для следующих двух символов ( B и E ).
Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все
не сведется к одному узлу.
Частота 30 10 5 10 20 25
Символа C A D F B E
і і і і і і
і і і і і і
і і ЪДДїі і і і
і АДґ15ГЩ і і і
і АВДЩ і і і
і і і і і
і і ЪДДї і і ЪДДї і
і АДДДДґ25ГДЩ АДґ45ГДЩ
і АВДЩ АВДЩ
і ЪДДї і і
АДДДДґ55ГДДДДДДЩ і
АДВЩ і
і ЪДДДДДДДДДДДДї і
АДДДґ Root (100) ГДДДДЩ
АДДДДДДДДДДДДЩ
Теперь когда наше дерево создано, мы можем кодировать файл . Мы должны
всенда начнинать из корня ( Root ) . Кодируя первый символ (лист дерева С)
Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый
поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота.
Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0)
к самому символу . Код Хаффмана для нашего символа C - 00. Для следующего
символа ( А ) у нас получается - лево,право,лево,лево , что выливается в
последовательность 0100. Выполнив выше сказанное для всех символов получим
C = 00 ( 2 бита )
A = 0100 ( 4 бита )
D = 0101 ( 4 бита )
F = 011 ( 3 бита )
B = 10 ( 2 бита )
E = 11 ( 2 бита )
Каждый символ изначально представлялся 8-ю битами ( один байт ), и так
как мы уменьшили число битов необходимых для представления каждого символа,
мы следовательно уменьшили размер выходного файла . Сжатие складывется
следующим образом :
ЪДДДДДДДДДДВДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДДДДДДДВДДДДДДДДДДДДДДї
і Частота і первоначально і уплотненные биты і уменьшено на і
ГДДДДДДДДДДЕДДДДДДДДДДДДДДДДЕДДДДДДДДДДДДДДДДДДДЕДДДДДДДДДДДДДДґ
і C 30 і 30 x 8 = 240 і 30 x 2 = 60 і 180 і
і A 10 і 10 x 8 = 80 і 10 x 3 = 30 і 50 і
і D 5 і 5 x 8 = 40 і 5 x 4 = 20 і 20 і
і F 10 і 10 x 8 = 80 і 10 x 4 = 40 і 40 і
і B 20 і 20 x 8 = 160 і 20 x 2 = 40 і 120 і
і E 25 і 25 x 8 = 200 і 25 x 2 = 50 і 150 і
АДДДДДДДДДДБДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДЩ
Первоначальный размер файла : 100 байт - 800 бит;
Размер сжатого файла : 30 байт - 240 бит;
240 - 30% из 800 , так что мы сжали этот файл на 70%.
Все это довольно хорошо, но неприятность находится в том факте, что для
восстановления первоначального файла, мы должны иметь декодирующее дерево,
так как деревья будут различны для разных файлов . Следовательно мы должны
сохранять дерево вместе с файлом . Это превращается в итоге в увеличение
размеров выходного файла .
В нашей методике сжатия и каждом узле находятся 4 байта указателя,
по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.
Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся
наши символы ) , всего 11 . 4 байта 11 раз - 44 . Если мы добавим после
небольшое количество байтов для сохранения места узла и некоторую другую
статистику - наша таблица будет приблизительно 50 байтов длинны.
Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что
общая длинна архивного файла вырастет до 80 байт . Учитывая , что
первоначальная длинна файла в рассматриваемом примере была 100 байт - мы
получили 20% сжатие информации.
Hе плохо . То что мы действительно выполнили - трансляция символьного
ASCII набора в наш новый набор требующий меньшее количество знаков по
сравнению с стандартным.
Что мы можем получить на этом пути ?
Рассмотрим максимум которй мы можем получить для различных разрядных
комбинацй в оптимальном дереве, которое является несимметричным.
Мы получим что можно иметь только :
4 - 2 разрядных кода;
8 - 3 разрядных кодов;
16 - 4 разрядных кодов;
32 - 5 разрядных кодов;
64 - 6 разрядных кодов;
128 - 7 разрядных кодов;
Hеобходимо еще два 8 разрядных кода.
4 - 2 разрядных кода;
8 - 3 разрядных кодов;
16 - 4 разрядных кодов;
32 - 5 разрядных кодов;
64 - 6 разрядных кодов;
128 - 7 разрядных кодов;
--------
254
Итак мы имеем итог из 256 различных комбинаций которыми можно
кодировать байт . Из этих комбинаций лишь 2 по длинне равны 8 битам.
Если мы сложим число битов которые это представляет, то в итоге получим
1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%,
таким образом максимально идеализированный Huffman может достигать сжатия
в 33% когда используется на уровне байта .
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
faq |
Mike Galushkin |
06 Apr 2003 13:18:22 |
 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:08:30 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:57:54 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:59:52 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 07:59:52 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:00:48 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:00:48 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:18 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:18 |
|
faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
|
2 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
 3 faq |
Comoderator Of Ru Algorithms |
10 Apr 2003 08:01:52 |
 3 faq |
Stanislav Shwartsman |
10 Apr 2003 08:11:45 |
|
3 faq |
Andrey Dashkovsky |
11 Apr 2003 23:00:43 |
|
3 faq |
Stanislav Shwartsman |
12 Apr 2003 10:39:21 |
 3 faq |
Andrey Dashkovsky |
13 Apr 2003 11:31:29 |
 3 faq |
Stanislav Shwartsman |
14 Apr 2003 08:20:45 |
 3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:21:35 |
|
3 faq |
Ruslan Tebuev |
14 Apr 2003 11:51:21 |
|
3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:38:11 |
|
3 faq |
Ruslan Tebuev |
15 Apr 2003 16:46:02 |
|
3 faq |
Moderator |
14 Apr 2003 23:26:48 |
|
3 faq |
Zahar Kiselev |
13 Apr 2003 19:07:12 |
|
3 faq |
Moderator |
14 Apr 2003 23:30:46 |
|
3 faq |
Stanislav Shwartsman |
15 Apr 2003 08:10:17 |
|
3 faq |
Andrey Dashkovsky |
14 Apr 2003 22:19:31 |
|
Re: 3 faq - аппроксимация |
Yuri Burger |
15 Apr 2003 14:49:50 |
|
|
