1. Кодовое дерево

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

3. Исходный код программ

1. Программа для нахождения среднего времени и скорости передачи

//////// СРЕДНЯЯ СКОРОСТЬ И ВРЕМЯ ПЕРЕДАЧИ /////////

int main()

{

freopen("input.txt", "rt", stdin);

freopen("output.txt", "wt", stdout);

int tests;

int n;

cin >> tests;

for (int i = 0; i < tests; i++)

{

cin >> n;

double sum = 0;

for (int j = 0; j < n; j++)

{

double time;

double probability;

cin >> time;

cin >> probability;

sum += time * probability;

}

cout << "aveTime = " << sum << endl; // среднее время

cout << "speed = " << (log(n)/log(2))/sum << endl; // средняя скорость передачи

cout << "###################################" << endl << endl;

}

return 0;

}

2. Программа для нахождения различный характеристик для алфавитов

int main()

{

freopen("input.txt", "rt", stdin);

freopen("output.txt", "wt", stdout);

int tests;

int n;

cin >> tests;

for (int i = 0; i < tests; i++)

{

cin >> n;

double sum = 0;

double entrophy = 0;

double probability = 1.0 / n;

for (int j = 0; j < n; j++)

{

double tmp;

cin >> tmp;

sum += tmp;

entrophy += (tmp * log(tmp)/log(2));

}

entrophy *= -1;

double compression = entrophy / (log(n)/log(2));

double superfluity = 1 - compression;

double underLoading = 1 - sum;

cout << "sum = " << sum << endl;

cout << "underLoading = " << underLoading << endl;

cout << "entrophy = " << entrophy << endl;

cout << "compression = " << compression << endl;

cout << "superfluity = " << superfluity << endl;

cout << "###################################" << endl << endl;

}

return 0;

}

Программа, реализующая метод Шеннона-Фано

#pragma comment(linker, "/STACK: 2000000"

#include <stdio.h>

#include <iostream>

#include <vector>

#include <cmath>

#include <stack>

#include <algorithm>

using namespace std;

////////////// ПОДЗАДАЧА 1.4 //////////////

vector<int> st; // стек

vector<pair<double, int> > len; // массив длин

// предикат для сортировки массива

bool pred(pair<int,double> a, pair<int,double> b)

{

return a.second > b.second;

}

void func(vector<pair<int,double> > arr)

{

if (arr.size() == 1) // достигли листа дерева

{

cout << "Leaf: (len=" << st.size() << ") ";

// сохраняем результат

pair<double, int> tmp;

tmp.first = arr[0].second;

tmp.second = st.size();

len.push_back(tmp);

for (vector<int>::iterator it = st.begin(); it < st.end(); it++)

{

cout << *it; //<< " ";

}

cout << endl;

cout << arr[0].first << " " << arr[0].second << endl;

cout << "-------------------------------------------------" << endl;

return;

}

// продолжаем разделение

vector<pair<int,double> > a,b;

sort(arr.begin(), arr.end(), pred);

int start = 0;

int end = arr.size() - 1;

double sumA = 0;

double sumB = 0;

while (start <= end)

{

if (sumB < sumA)

{

sumB += arr[end].second;

b.push_back(arr[end]);

end--;

}

else

{

sumA += arr[start].second;

a.push_back(arr[start]);

start++;

}

}

st.push_back(0);

func(a);

st.pop_back();

st.push_back(1);

func(b);

st.pop_back();

}

int main()

{

freopen("input.txt", "rt", stdin);

freopen("output.txt", "wt", stdout);

int steps; // количество циклов обработки

int n;

cin >> steps;

cin >> n; // размерность началльного массива

vector<pair<int,double> > old;

for (int i = 0; i < steps; i++)

{

vector<pair<int,double> > arr(n);

if (i > 0) // формирование нового массива (блочное кодирование)

{

int old_n = (int)sqrt(n);

for (int j = 0; j < n; j++)

{

arr[j].second = old[j/old_n].second * old[j%old_n].second;

arr[j].first = j;

}

}

if (i == 0) // считывание данных

{

int j = 0;

for (vector<pair<int,double> >::iterator it = arr.begin(); it < arr.end(); it++)

{

cin >> (*it).second;

(*it).first = j;

j++;

}

}

len.clear();

// запуск алгоритма Шеннона-Фано

func(arr);

double aveLen = 0;

double entrophy = 0;

// подсчет искомых значений

for (vector<pair<double, int> >::iterator it = len.begin(); it < len.end(); it++)

{

aveLen += (((*it).first * (*it).second));

entrophy += (*it).first * log((*it).first)/log(2);

}

entrophy *= -1;

cout << "aveLen = " << aveLen << endl; // средняя длина

cout << "entrophy = " << entrophy << endl; // энтропия

cout << "Criteria = " << (aveLen - entrophy)/entrophy << endl; // близость средней длины к энтропии

cout << "############################################" << endl;

cout << "############################################" << endl;

cout << "############################################" << endl << endl;

old = arr; // сохраняем старый массив

n = n*n; // увеличение размерности

}

return 0;

}