Решение задач на использование алгоритмов обработки данных

Цель лекции: изучить основные приемы разработки алгоритмов обработки данных, научиться применять их при решении задач и учитывать трудоемкость и эффективность используемых алгоритмов.

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

Приведем общую схему решения задач по программированию.

Алгоритмы сортировки данных

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

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

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

Пример 1. Задача "Поразрядная сортировка"

Поразрядная сортировка была изобретена в 1920-х годах как побочный результат использования сортирующих машин. Такая машина обрабатывала перфокарты, имевшие по 80 колонок. Каждая колонка представляла отдельный символ. В колонке было 12 позиций, и в них для представления того или иного символа пробивались отверстия. Цифру от 0 до 9 кодировали одним отверстием в соответствующей позиции (еще две позиции в колонке использовали для кодировки букв).

Запуская машину, оператор закладывал в ее приемное устройство стопку перфокарт и задавал номер колонки на перфокартах. Машина "просматривала" эту колонку на картах и по цифровому значению 0, 1, ..., 9 в ней распределяла ("сортировала") карты на 10 стопок.

Несколько колонок (разрядов) с закодированными цифрами представляли натуральное число, т.е. номер. Чтобы получить стопку карт, упорядоченных по номерам, оператор действовал так. Вначале он распределял карты на 10 стопок по значению младшем разряде. Эти стопки в порядке возрастания значений в младшем разряде он складывал в одну и повторял процесс, но со следующим разрядом, и т.д. Получив стопки карт, распределенных по значениям в старшем разряде, оператор складывал их по возрастанию этих значений и получал то, что нужно.

Значения в разрядах номеров заданы цифрами, поэтому поразрядную сортировку еще называют цифровой. Заметим, что цифры от 0 до 9 упорядочены по возрастанию, поэтому цифровая сортировка располагает числа в лексикографическом порядке.

Пример.

Описание решения.

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

733   877   323   231   777   721   123

Распределим данную последовательность по младшей цифре на стопки:

231   721
733   323   123
877   777

Далее сложим получившиеся стопки в одну в порядке возрастания последней цифры.

231   721  733   323   123  877   777

На следующем шаге номера, которые обрабатываются именно в этой последовательности, распределяются по второй цифре на следующие стопки.

721   323   123
231   733
877   777

Затем из них также образуется одна последовательность.

721   323   123   231   733   877   777

Обратим внимание, что перед последним шагом все номера с числом сотен 7, благодаря предыдущим шагам, расположены один относительно другого по возрастанию.

На последнем шаге номера распределяются по старшей цифре на стопки:

123
231
323
721   733   777
877

и образуется окончательная последовательность:

123   231   323   721   733   777   877.

Далее приведем код программы.

#include "stdafx.h"
#include <iostream>
using namespace std;
const int D = 3;
const int B = 10;

typedef int T[D];
typedef T *List;

void SortD(int k);
void Done();
void outDigs(int i);

List Data;
int PFirst[B], PLast[B], *PQNext;
int first, n, newL, tempL, i, nextI;

int _tmain(int argc, _TCHAR* argv[]){
  int k;
  cout << "Введите количество элементов массива n  ";
  cin >> n;
  Data = new T[n];
  PQNext = new int[n];
  for ( k = 0 ; k < n ; k++ ){
    PQNext[k] = k + 1;
    for ( int r = 0 ; r < D ; r++ )
      Data[k][r] = 0;
  }
  for ( k = 0 ; k < n ; k++ )
    for ( int r = 0 ; r < D ; r++ )
      Data[k][r] = rand()%B;
  first = 0;
  Done();
  cout << endl;
  for ( k = D - 1 ; k >= 0 ; k-- )
    SortD(k);
  Done();
  cout << endl;
  delete [] PQNext;
  delete [] Data;
  system("pause");
  return 0;
}

// описание функции поразрядной сортировки
void SortD(int k){
  for ( tempL = 0 ; tempL < B ; tempL++ ){
    PFirst[tempL] = n;
    PLast[tempL] = n;
  }
  i = first;
  while (i != n){
    tempL = Data[i][k];
    nextI = PQNext[i];
    PQNext[i] = n;
    if ( PFirst[tempL] == n )
      PFirst[tempL] = i;
    else PQNext[PLast[tempL]] = i;
    PLast[tempL] = i;
    i = nextI;
  }
  tempL = 0;
  while ( tempL < B  PFirst[tempL] == n )
    tempL++;
  first = PFirst[tempL];
  while ( tempL < B - 1 ){
    newL = tempL + 1;
    while ( newL < B  PFirst[newL] == n )
      newL++;
    if ( newL < B )
      PQNext[PLast[tempL]] = PFirst[newL];
    tempL = newL;
  }
}

/*описание функции вывода элементов в соответсвии со списком индесов в массиве PQNext*/
void Done(){
  int i = first;
  while ( i != n ){
    outDigs(i);
    i = PQNext[i];
  }
}

/*описание функции вывода элементов из массива Data, индекс которого задан ее аргументом*/
void outDigs(int i){
  int j = 0;
  while ( Data[i][j] == 0  j < D )
    j++;
  if ( j == D )
    cout << 0;
  else
    while ( j < D )
      cout << Data[i][j++];
  cout << "  ";
}

Алгоритмы на графах

Многие прикладные задачи и задачи повышенной сложности легко сформулировать в терминах такой структуры данных как граф. Для ряда подобных задач хорошо изучены эффективные (полиномиальные) алгоритмы их решения.

Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, с помощью которой легко проверить, существует ли в графе ребро, соединяющее вершину одну с вершиной с другой. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N2 значений, даже если ребер в графе существенно меньше, чем N2. Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.

Данного недостатка лишены такие способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.

Для реализации некоторых алгоритмов более удобным является описание графа путем перечисления его ребер. В этом случае хранить его можно в одномерном массиве длиной M, каждый элемент которого содержит запись о номерах начальной и конечной вершин ребра, а также его весе в случае взвешенного графа.

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

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

Графы широко используются в различных областях науки и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра – отношениям между объектами.

Пример 2. Задача "Тетраэдр"

Дано треугольное поле в виде равностороннего треугольника. Оно разбито на одинаковые равносторонние треугольники со сторонами в М раз меньшими, чем сторона большого треугольника (рис 46.1).

Маленькие треугольники пронумерованы подряд с верхнего ряда вниз по рядам, начиная с 0. Числами показаны номера треугольников. I -му треугольнику приписана пометка Pi.

Имеется также тетраэдр (правильная треугольная пирамида) с ребром, равным длине стороны маленького треугольника. Тетраэдр установлен на S -м треугольнике. Все грани тетраэдра пронумерованы следующим образом:

Например, при S=2 жирной линией выделено нижнее ребро третьей грани, а при S=3 жирной линией выделено нижнее ребро второй грани. J -я грань тетраэдра имеет пометку Rj.

Имеется возможность перекатывать тетраэдр через ребро, но при каждом перекатывании взимается штраф, равный квадрату разности между пометками совмещаемой грани тетраэдра и треугольника. Требуется перекатить тетраэдр с треугольника S на D с наименьшим суммарным штрафом $$(S\ne D)$$.

Входные данные находятся в текстовом файле INPUT.TXT. Первая строка содержит целые числа S, D и М (M<=90). Каждая из следующих M2 строк содержит пометку соответствующего треугольника. В последней строке записаны пометки граней тетраэдра. Пометки (как граней, так и треугольников) – целые неотрицательные числа, не превосходящие 300. Числа в одной строке разделены пробелами.

В выходной файл OUTPUT.TXT должно быть записано одно число – минимально возможный штраф.

Пример.

0 4 3
         4
         3
         8
       100
         7
         3
         2
        49
         9
7 50 100 8

9446

Описание решения.

Перейдем к графу следующим образом: вершина – маленький треугольник. Ребро – наличие возможности перекатить тетраэдр через ребро из одного треугольника в другой. Тогда, например, поле, изображенное на рис 46.2, превратится в граф на рис 46.3.

На этом графе требуется найти путь минимальной стоимости из одной вершины в другую. Поскольку веса ребер в этом графе зависят от того, какой именно гранью тетраэдр придет на соответствующий треугольник, то воспользуемся поиском в ширину. Но прежде проясним процесс перекатывания тетраэдра. В соответствии с условиями задачи начальное положение развертки тетраэдра показано на рис 46.4.

Обозначим его и рис 46.6 приведены соответствующие развертки:

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

Для удобства использования этой информации введем следующее кодирование:

Получаем двумерный массив Т (8 строк, 4 столбца), который описывает все возможные перекатывания тетраэдра.

Основная идея решения заключается в следующем:

При установке в очередь очередной элемент включает номер вершины на графе, тип прихода (1u...4d), текущий штраф после перехода в эту вершину. Элемент не нужно ставить в очередь, если текущий штраф больше ранее запомненного для этой вершины графа.

Далее приведем код программы.

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
void InputData();
void OutResult();
void InitGraph();
void Put(long long v, long long tv, long long cv);
void Get(long long *v, long long *tv, long long *cv);
void PutAll(long long v, long long tv, long long cv);
long long SQR(long long a);
int MaxM = 10;
int Table[8][4]  =  {
          8, 0, 6, 4,
          0, 7, 3, 5,
          6, 0, 8, 2,
          0, 5, 1, 7,
          4, 0, 2, 8,
          0, 3, 7, 1,
          2, 0, 4, 6,
          0, 1, 5, 3
          };
int MaxQ = MaxM * MaxM * MaxM;
int *p, *cp, *Pw, **g, **Q;
long long *R;
long long i, S, D, M, j, a, TS, QBegin, QEnd, V, TV, CV, Last;
//V – номер вершины
//TV – тип вершины
//CV – текущее значение штрафа
int _tmain(int argc, _TCHAR* argv[]){
  p = new int[MaxM * MaxM];
  cp = new int[MaxM * MaxM];
  Pw = new int[MaxM * MaxM];
  for (i = 0; i < MaxM * MaxM; i++)
    p[i] = cp[i] = Pw[i] = 0;
  g = new int*[MaxM * MaxM];
  for (i = 0; i < MaxM * MaxM; i++ ){
    g[i] = new int[4];
    g[i][0] = g[i][1] = g[i][2] = g[i][3] = 0;
  }
  Q = new int*[MaxQ + 1];
  for (i = 0; i < MaxQ  + 1; i++ ){
    Q[i] = new int[4];
    Q[i][0] = Q[i][1] = Q[i][2] = Q[i][3] = Q[i][4] = 0;
  }
  R = new long long[5];
  R[0] = R[1] = R[2] = R[3] = R[4] = 0;
  InputData();
  InitGraph();
  QEnd = 0;
  QBegin = 1;
  Put(S,TS,0);
  while (QBegin <= QEnd){
    Get(V,TV,CV);
    PutAll(V,TV,CV);
  }
  OutResult();
  system("pause");
  return 0;
}
//описание функции ввода исходных данных
void InputData(){
  FILE *f;
  f = fopen("input.txt","r");
  fscanf(f,"%d %d %d",S,D,M);
  for ( i = 0; i < M * M; i++ )
    fscanf(f,"%d",p + i);
  for ( i = 1; i < 5; i++ )
    fscanf(f,"%d",R + i);
  fclose(f);
}
//описание функции вывода результата
void OutResult(){
  FILE *f;
  f = fopen("output.txt","w");
  fprintf(f,"%d",cp[D]);
  fclose(f);
}
//описание функции создания графа по исходным данным
void InitGraph(){
  Pw[0] = 1;
  g[0][1] = 2;
  for ( i = 1; i < M; i++)
    for ( j = i * i; j < (i + 1) * (i + 1) - 1; j++){
      g[j][++Pw[j]] = j + 1;
      g[j + 1][++Pw[j + 1]] = j;
    }
  a = 4;
  TS = 1;
  for ( i = 1; i < M - 1; i++){
    for ( j = i * i; j < (i + 1) * (i + 1); j += 2){
      g[j][++Pw[j]] = j + a;
      g[j + a][++Pw[j + a]] = j;
      if ( S == j ) TS = 2;
    }
    a += 2;
  }
  for ( i = 0; i < M * M; i++)
    cp[i] = INT_MAX;
}
//описание функции постановки в очередь одной вершины графа
void Put(long long v, long long tv, long long cv){
  QEnd++;
  Q[QEnd][1] = v;
  Q[QEnd][2] = tv;
  Q[QEnd][3] = cv;
  cp[v] = cv;
}
//описание функции взятия из очереди очередной вершины графа
void Get(long long *v, long long *tv, long long *cv){
  *v = Q[QBegin][1];
  *tv = Q[QBegin][2];
  *cv = Q[QBegin][3];
  QBegin++;
}
/*описание функции постановки в очередь всех вершин, смежных с текущей*/
void PutAll(long long v, long long tv, long long cv){
  long nv, ntv, ncv, Dir, Base;
  for ( i = 1 ; i <= Pw[v]; i++ ){
    nv = g[v][i];
    if ( nv == v + 1 )
      Dir = 2;
    else if ( nv == v - 1 )
      Dir = 3;
    else if ( nv > v )
      Dir = 0;
    else Dir = 1;
    ntv = Table[tv-1][Dir];
    Base = (ntv + 1) / 2;
    if ( Base > 0 ) {
      ncv =  cv + SQR(p[nv] - R[Base]);
      if ( ncv < cp[nv] )
        Put(nv,ntv,ncv);
    }
  }
}
//описание функции возведения в квадрат
long long SQR(long long a){
  return a*a;
}

Алгоритмы сжатия данных

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

Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов данных и разных объемов. Однако в основе этих методов лежат три теоретических алгоритма:

Пример 3. Задача "Энтропийное кодирование"

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

Английский текст, закодированный с помощью ASCII, имеет высокую степень энтропии, потому что для кодирования всех символов используется одно и тоже количество битов – восемь. В то же время известный факт состоит в том, что буквы E, L, N, R, S и T встречаются со значительно более высокой частотой, чем другие буквы английского алфавита. Если найдется способ закодировать только эти буквы четырьмя битами, то закодированный текст станет существенно меньше и при этом будет содержать всю исходную информацию и иметь меньшую энтропию. Однако, как различить при декодировании, четырьмя или восемью битами закодирован очередной символ? Эта проблема решается с помощью префиксного кодирования.

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

Рассмотрим текст AAAAABCD. Кодирование, использующее ASCII, требует 64 бита. Если же символ А будет кодироваться битовой последовательностью 00, символ В – последовательностью 01, символ С – последовательностью 10, a D – последовательностью 11, то для кодирования потребуется всего 16 битов. Результирующий поток битов будет такой: 0000000000011011.

Но это все еще кодирование с фиксированной длиной, здесь просто использовались для каждого символа два бита вместо восьми.

Символ А встречается чаще, тогда будем его кодировать с помощью меньшего количества битов. Следовательно, закодируем символы такими последовательностями битов:

А – 0
В –10
С – 110
D – 111

Используя такое кодирование, получим только 13 битов в закодированном сообщении: 0000010110111. Коэффициент сжатия в этом случае равен 4,9 к 1. Это означает, что каждый бит в последнем закодированном сообщении содержит столько же информации, сколько и 4,9 бит в первом закодированном сообщении (с помощью ASCII).

Попробуйте читать сообщение 0000010110111 слева направо – и убедитесь, что "префиксное" кодирование обеспечивает простое декодирование текста, даже несмотря на то, что символы кодируются различным количеством битов.

В качестве другого примера рассмотрим текст THE CAT IN THE HAT.

В этом тексте символы Т и пробел встречаются чаще других. Поэтому их нужно кодировать меньшим количеством битов. А символы C, I и N встречаются только по одному разу, потому будут кодироваться самыми длинными кодами. Например, так:

пробел – 00
А – 100
С – 1110
Е – 1111
Н – 110
I – 1010
N – 1011
Т – 01

При таком кодировании исходного предложения потребуется только 51 бит против 144, которые необходимы, чтобы закодировать исходное сообщение с помощью 8-битного ASCII-кодирования. Коэффициент сжатия равен 2,8 к 1.

Входной файл будет содержать список текстовых сообщений, по одному в строке. Сообщения будут состоять только из больших английских букв, цифр и символов подчеркивания (вместо пробелов). Конец файла обозначается строкой END. Эту строку не нужно обрабатывать.

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

Пример.

AAAAABCD
THE_CAT_IN_THE_HAT
END

64 13 4.9
144 51 2.8

Описание решения.

В данной задаче проведем кодирование текста алгоритмом Хаффмана. Отличиями являются представление входных и выходных данных. Каждую входную строку нужно кодировать по отдельности. Строка "END" обозначает конец ввода, ее кодировать не нужно.

На выходе нужно указать три числа:

Приведем программную реализацию данной задачи.

#include "stdafx.h"
#include <iostream>
using namespace std;
void InputData(FILE *f);
long MinK();
void SumUp(FILE *f);
void BuildBits();
void OutputData(FILE *f);
void Create();
void Clear();
void Destroy();

int MaxK = 1000;
long *k, *a, *b;
char **bits;
char *sk;
bool *Free;
char **res;
long i, j, n, m, kj, kk1, kk2;
char str[256];
int _tmain(int argc, _TCHAR* argv[]){
  FILE *in, *out;
  in = fopen("input.txt","r");
  out = fopen("output.txt","w");
  while ( !feof(in) ) {
    Create();
    Clear();
    InputData(in);
    cout << str << endl;
    SumUp(out);
    if (kj != 1) BuildBits();
    if (kj != 1) OutputData(out);
    Destroy();
  }
  fclose(out);
  fclose(in);
  
  return 0;
}
//описание функции выделения памяти
void Create(){
  if ( (k = new long[MaxK + 1]) == NULL ){
    printf ("Memory for k no!\n");
    system("pause");
    exit(0);
  }
  if ( (a = new long[MaxK + 1]) == NULL ){
    printf ("Memory for a no!\n");
    system("pause");
    exit(0);
  }
  if ( (b = new long[MaxK + 1]) == NULL ){
    printf ("Memory for b no!\n");
    system("pause");
    exit(0);
  }
  if ( (bits = new char*[MaxK + 1]) == NULL ){
    printf ("Memory for bits no!\n");
    system("pause");
    exit(0);
  }
  for (i = 0; i < MaxK + 1 ; i++)
    if ( (bits[i] = new char[40]) == NULL ){
      printf ("Memory for bits[%d] no!\n",i);
      system("pause");
      exit(0);
    }
  if ( (sk = new char[MaxK + 1]) == NULL ){
    printf ("Memory for sk no!\n");
    system("pause");
    exit(0);
  }
  if ( (Free = new bool[MaxK + 1]) == NULL ){
    printf ("Memory for Free no!\n");
    system("pause");
    exit(0);
  }
  if ( (res = new char*[256]) == NULL ){
    printf ("Memory for res no!\n");
    system("pause");
    exit(0);
  }
  for (int i = 0; i < 256 ; i++)
    if ( (res[i] = new char[40]) == NULL ){
    printf ("Memory for res[%d] no!\n",i);
    system("pause");
    exit(0);
  }
}
//описание функции обнуления данных в массивах
void Clear(){
  for (i = 0; i < MaxK + 1; i++){
    k[i] = a[i] = b[i] = 0;
    sk[i] = 0;
    Free[i] = true;
    for (j = 0; j < 40; j++)
      bits[i][j] = 0;
  }
  for (i = 0; i < 256 ; i++)
    for (j = 0; j < 40; j++)
      res[i][j] = 0;
}
//описание функции освобождения памяти
void Destroy(){
  delete [] res;
  delete [] Free;
  delete [] sk;
  delete [] bits;
  delete [] b;
  delete [] a;
  delete [] k;
}
//описание функции ввода данных
void InputData(FILE *f){
  char c;
  long *s = new long[256];
  for ( i = 0; i < 256; i++)
    s[i] = 0;
  fscanf(f,"%s", str);
  if (strcmp(str,"END") == 0) {
    system("pause");
    exit(0);
  }
  for ( n = 0; n < strlen(str); n++ ){
    c = str[n];
    s[c]++;
  }
  j = 0;
  for ( i = 0; i < 256; i++)
    if ( s[i] != 0 ){
      j++;
      k[j] = s[i];
      sk[j] = i;
    }
  kj = j;
}
/*описание функции нахождения минимальной частоты символа в исходном тексте*/
long MinK(){
  long min;
  i = 1;
  while ( !Free[i]  i < MaxK) i++;
  min = k[i];
  m = i;
  for ( i = m + 1; i <= kk2; i++ )
    if ( Free[i]  k[i] < min ){
      min = k[i];
      m = i;
    }
  Free[m] = false;
  return min;
}
//описание функции посчета суммарной частоты символов
void SumUp(FILE *f){
  long s1, s2, m1, m2;
  if ( kj == 1 ){
    fprintf(f,"%d %d %.1f\n",8*strlen(str),strlen(str),8);
    return;
  }
  for ( i = 1; i <= kj; i++ ){
    Free[i] = true;
    a[i] = 0;
    b[i] = 0;
  }
  kk1 = kk2 = kj;
  while (kk1 > 2){
    s1 = MinK();
    m1 = m;
    s2 = MinK();
    m2 = m;
    kk2++;
    k[kk2] = s1 + s2;
    a[kk2] = m1;
    b[kk2] = m2;
    Free[kk2] = true;
    kk1--;
  }
}
//описание функции формирования префиксных кодов
void BuildBits(){
  bits[kk2] = "1";
  Free[kk2] = false;
  strcpy(bits[a[kk2]],bits[kk2]);
  strcat( bits[a[kk2]] , "0");
  strcpy(bits[b[kk2]],bits[kk2]);
  strcat( bits[b[kk2]] , "1");
  i = MinK();
  bits[m] = "0";
  Free[m] = true;
  strcpy(bits[a[m]],bits[m]);
  strcat( bits[a[m]] , "0");
  strcpy(bits[b[m]],bits[m]);
  strcat( bits[b[m]] , "1");
  for ( i = kk2 - 1; i > 0; i-- )
    if ( !Free[i] ) {
      strcpy(bits[a[i]],bits[i]);
      strcat( bits[a[i]] , "0");
      strcpy(bits[b[i]],bits[i]);
      strcat( bits[b[i]] , "1");
    }
}
//описание функции вывода данных
void OutputData(FILE *f){
  long b8, bh;
  for ( i = 1; i <= kj; i++ )
    res[sk[i]] = bits[i];
  b8 = 8 * strlen(str);
  bh = 0;
  for (i = 0; i < strlen(str); i++)
    bh += strlen(res[str[i]]);
  double k = b8 * 1.0 / bh;
  fprintf(f,"%d %d %.1f\n",b8,bh,k);
}

Ключевые термины

Цифровая (поразрядная) сортировка – это упорядочивание данных по ключу, которое выполняется отдельно с каждым разрядом с последующим объединением результатов.

Энтропийное кодирование – это метод кодирования данных, который обеспечивает компрессию данных за счет удаления избыточной информации.

Краткие итоги

Лабораторная работа 46. Решение задач на использование алгоритмов обработки данных

Цель работы: изучить основные приемы разработки алгоритмов обработки данных, научиться применять их при решении задач и учитывать трудоемкость и эффективность используемых алгоритмов.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 46.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

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

Пример входного файла:

10
1 5 10 3 6 5 
2 6 7 3 6 9 
5 7 3 2 1 9
1 3 3 5 8 10
6 6 2 2 4 4 
1 2 3 4 5 6
10 9 8 7 6 5 
6 1 2 3 4 7
1 2 3 3 2 1
3 2 1 1 2 3

Пример выходного файла:

8
1 bottom
2 back
3 right
4 left
6 top
8 front
9 front
10' top

Указания к выполнению работы.

Лабораторная работа носит одновременно практический и исследовательский характер, поэтому для ее выполнения сначала необходимо изучить материал лекции 33, обратив внимание на приведенные примеры и их описание. Каждое задание необходимо решить в соответствии с изученными в предыдущих лабораторных работах алгоритмами обработки данных в языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи. Результаты тестирования программ необходимо провести в соответствии приведенными примерами входных и выходных файлов к задачам (как дополнение допустимы и собственные примеры тестовых данных). В выводе к отчету необходимо сформулировать результаты проведения анализа трудоемкости алгоритмов, сделать выводы о принадлежности каждого алгоритма к определенному классу сложности с обоснованием результата.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы