int kl InByte (letter) ; int k2 = InByte(letter); int size = 256 * kl + k2;

старший байт длины сообщения младший байт длины сообщения длина сообщения

вывести size байт в outfile for(int i = 0; i < size; i++)

outfile (char)InByte(letter);

Напоследок для примера можно привести фрагмент письма с внедрённым сообщением hello! , сгенерированного программой:

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

9.3.2. Стеганография в изображениях - более надёжный

способ передачи секретных сообщений

Текст, в котором неравномерность пробелов сразу бросается в глаза, - не лучший кандидат на роль подставного письма. Гораздо надежнее можно спрятать сообщение в файле с картинкой.

Возьмём любое достаточно большое 24-битное (true color) изображение. В нём выберем какой-либо сравнительно часто встречающийся цвет (назовём его базовым ). Для простоты можно просто взять пиксель из левого верхнего угла, при условии, что он не белый. Если угловой пиксель оказался белым, можно заменить его цвет на сероватый: для невооруженного глаза картинка от этого не изменится.

Обозначим RGB компоненты базового цвета как (R, Gj, В). Дополнительным цветом назовем цвет (В + 1, Gj + 1, В + 1).

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

В результате выполненных действий мы получим картинку, полностью свободную от пикселей дополнительного цвета. Это означает, что можно использовать дополнительный цвет в качестве источника информации. Например, пусть каждый пиксель базового цвета кодирует нуль, а пиксель дополнительного цвета - единицу. Осталось пройтись по картинке ещё раз и изменить где требуется базовый цвет на дополнительный в соответствии с содержимым секретного сообщения.

Думаю, теперь понятно, почему белый цвет, RGB компоненты которого равны (255,255, 255), не годится в качестве базового: дополнительный цвет для него подобрать нельзя.

Вашим заданием будет написание полноценной системы стеганографии, аналогичной программе из предыдущей задачи.

9.4. СПЕЦИАЛИЗИРОВАННЫЕ АЛГОРИТМЫ

9.4.1. Оптимальное вычисление Принцип динамического программирования

В процессе решения математических задач нередко приходится вычислять произведения матриц. В результате умножения матрицы А размерностью ш X к на матрицу В размерностью к х п (если количество столбцов первой матрицы не совпадает с количеством строк второй, умножение производить нельзя) получается матрица С размерностью m х п, значения элементов которой находятся по формуле:

CrAi*B>i + VB, + - + VB,

Вычисление произведения двух матриц - довольно дорогостоящая операция, требующая m х к х п операций умножения отдельных элементов (е прямолинейной реализации).

Поскольку А X (В X С) = (А X В) X С, произведение трёх и более матри! А, X Aj X ... X А можно вычислять в любом порядке. Последовательность выбора очередной пары матриц для перемножения не влияет на конечны результат, но влияет на скорость работы алгоритма.

Первый по.пученный бит записывается в старший бит result, но после восьми итераций (и, соответственно, семи сдвигов result вправо) оно оказывается уже на месте младшего бита, а последнее считанное значение - на месте старшего.

Функция Decode () совершенно прямоушнейна:

void Decode(char *enc file) {

ifstream letter(enc file); ofstream outfile( decoded.txt ) ;

Чтобы получить общее количество операций, необходимое для вычисления всего произведения, к величине Ops придётся прибавить операции, затрачиваемые при получении каждой из матриц-\!ножителей (поскольку эти матрицы, в свою очередь, тоже могут быть произведениями других матриц).

Таким образом, постепенно вырисовывается схема алгоритма: искомое количество операций для случая N матриц выражается через решения задач, включающих меньшее количество матриц.

Поскольку текст на С++ в данном случае выглядит ненамного сложнее псевдокода, я сразу буду приводить фрагменты окончательной программы.

Пусть в массивах

vector<int> Rows, Columns;

Хранятся размерности матриц исходного произведения (так, Rows[l], Columns [ 1 ] - размерность первой матрицы). Ради удобства нотации я не стал использовать нулевые элементы массивов.

Тогда количество операций, требуемое для вычисления цепочки А х ... х А, можно найти с помощью рекурсивной функции GetOps ():

int GetOps(int i, int j) {

if(i == j) одна матрица

return 0;

максимальное целое число

int minOps = numeric limits<int>() .max();

находим наименьшее количество операций, требуемое для вычисления выражения A[i]*...*А[к]*...*А[j] for(int к = i; к < j; к++) {

int ops = GetOps(i, k) + Rows[i]*Columns[k]*Columns[j] +

GetOps(k + 1, j); if(ops < minOps) minOps = ops;

return minOps;

Эта функция является ядром программы. При вызове GetOps (1, N) будет найдено решение исходной задачи.

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

Рассмотрим вычисление выражения Aj х Aj х A3, где размерность А, равна 5x10, размерность - 10x6, а размерность A3 - 6x2. Если сначала вычислить значение А, х А, это потребует 300 (5x10x6) операций умножения. Полученная матрица 5x6 умножается на A3, что потребует ещё 60 (5x6x2) умножений. В результате получаем 360 операций. Если же первым делом вычислить значение А2 х A3, а лишь затем умножить А на полученную матрицу, алгоритм потребует лишь 220 (120 + 100) умножений.

Задача заключается в определении оптимального порядка вычисления произведения N матриц А, X Aj X ... х А. На вход подаётся число N и размерность каждой участвующей в выражении матрицы. На выходе программа должна печатать цепочку перемножаемых матриц с расставленными скобками, соответствующими оптимальному вычислению произведения.

Решение

Решение в лоб очевидно: перебор всех возможных вариантов умножения с подсчётом количества выполняемых операций. К счастью, существует и более эффективный алгоритм, требующий порядка действий, где N - количество матриц в цепочке (полный перебор имеет экспоненциальную сложность).

Рассмотрим произведение N матриц А, х Aj х ... х Aj. В конечном счёте, в любой операции умножения участвует только два .элемента, только две матрицы. Вопрос лишь в том, как расставить скобки, чтобы разделить N матриц на две группы. Здесь возможно всего N - 1 вариантов:

А, X (Аз X ... X А), (А, X Aj) X (A3 X ... X А),(А, х ... х А ,) х А

Как уже сказано, умножение матрицы размерностью m х г на матрицу размерностью г X п требует m х г х п операций. Размерности обеих матриц в произведении мы знаем: у матрицы А. х ... х А. столько же строк, сколько у А, и столько же столбцов, сколько у А.. Обозначив через к индекс, на котором заканчивается первая матрица, можно записать произведение в общем виде:

(А, х...хА,)х( А,х...хА)

Количество операций, требуемое для умножения этих матриц, будет выражаться формулой:

Ops = Rows(Aj)*Columns(A)*Columns(A),

где Rows(A) - количество строк, а Columns(A) - количество столбцов в матрице А.

return minOps;

Для вывода на экран решения подзадачи Ai х ... х Aj потребуется вспомогательная функция RepresentSolution ():

string RepresentSolution(int i, int j) {

одна матрица

if(i == j)

вернуть строковое представление её порядкового номера ostringstream s; s i;

return s.str();

else {

найти разбиение задачи на две подзадачи int к = Subproblems[pair<int, int>(i, j)];

string si = RepresentSolution(i, k); решение первой подзадачи если оно состоит из более чем одной матрицы, заключить в скобки if(si.length О > 1)

si = -(- + si + -) ;

аналогично для второй подзадачи string s2 = RepresentSolution(к + 1, j); if(s2.length О > 1)

s2 = -(- + s2 + -)-;

return si + * + s2;

Осталось написать лишь нехитрую функцию main ():

int main(int argc, char* argv[]) {

int N; количество матриц

cout N = *; cin N;

Rows.push back(0); заполнить нулевые элементы массивов Columns.push back(0); (они нам не понадобятся)

считать значения Rows[i] и Columns[i]

for(int i = 1; i <= N; i++)

int h, w;

cout Rows( i *) = ; cin h;

Чтобы определить фактически выполняемую последовательность умножений, которой соответствует минимальное количество операций, достаточно сохранять для каждой передаваемой на вход функции GetOps () пары чисел (i, j ) найденный разделитель к.

Второе усовершенствование функции заключается в использовании дополнительного кэша . Обратите внимание, что GetOps () может многократно вызываться для одних и тех же значений (i, j ). Поэтому сохранять однажды найденные значения, чтобы избежать повторного вычисления, весьма полезно.

Функции кэша и хранилища разбиений задач па подзадачи выполняют ассоциативные массивы Cache и Subproblems:

map<pair<int, int>, int> Cache; паре (i, j) сопоставляется

значение ops

map<pair<int, int>, int> Subproblems; nape (i, j) сопоставля-

ется величина к

Итоговая версия функции GetOps () приведена ниже.

int GetOps(int i, int j) {

if(i == j)

return 0;

поиск пары (i, j) в кэше

map<pair<int, int>, int>::iterator p = Cache.find{pair<int, int>(i, j));

если пара найдена, возвращается значение, извлечённое из кэша if(р != Cache.end()) return p->second;

иначе находим наименьшее требуемое количество операций и

соответствующий ему индекс разбиения minK

int minOps = numeric limits<int>::max(), minK;

for(int к = i; к < j; k++)

int ops = GetOps(i, k) + Rows[i]*Columns[k]*Columns[j] +

GetOps(k + 1, j); if(ops < minOps)

{ minOps = ops; minK = k; )

занести значение minK в массив разбиений, а значение GetOps(1, j) в кэш Subproblems[pair<int, int>(i, j)] = minK; Cache[pair<int, int>(i, j)] = minOps;