Источник генерирует знак x1 и x2 с вероятностями р(x1)=0, 33 и р(x2)=0, 67. построить коды шеннона – фано и хаффмана для для последовательности из трех знаков. каково среднее число символов на знак? сравнить с энтропией.

Строить коды для алфавита из двух символов немного странно - и так понятно, что получатся 0 и 1, и все эти кодирования бессмысленны.

Код Шеннона - Фано: делим знаки на две части, чтобы суммарные вероятности появления символов частей были максимально близки (тут в каждой части всего один символ - иначе никак). Одной приписываем 0, другой 1. На этом всё кончилось.

Код Хаффмана: выбираем два символа с наименьшими вероятностями, у одного постфикс 0, у другого 1. Объединяем в одну вершину, и она осталась одна. Конец.

В среднем 1 символ - 1 бит.
Энтропия -∑ p ㏒₂ p = -0.33 log 0.33 - 0.67 log 0.67 = 0.915 бит на символ.

Учитывая, что энтропия всегда не превосходит среднюю длину кода, тут сошлось.

//Pascal ABC.NET v3.0 сборка 1111

var
 i,a,b:integer;
 ar:array[1..10] of integer;

 procedure oddDec(var a,b:integer);  //подпрограмме переданы аргументы a и b
//процедура для вычитания в нечётном элементе
begin;
a:=a-b;
end;

procedure NotoddInc(var a,b:integer); //подпрограмме переданы аргументы a и b
//процедура для сложения в чётном элементе
begin;
a:=a+b;
end;

begin
randomize;
readln(a); //ввод a
readln(b); //ввод b
writeln('Array:');
for i:=1 to 10 do //весь массив
 begin;
  ar[i]:=random(-20,80); //случайные числа от -20 до 80 включительно
  write(ar[i]:4); //вывод
  if odd(i) then oddDec(ar[i],b) else NotoddInc(ar[i],a);
  {если нечётное, то первая процедура, иначе вторая. Обращаю внимания на то, что элементы меняются сразу после вывода}
 end;
writeln;
writeln('Final array:'); //вывод получившегося массива
for i:=1 to 10 do
write(ar[i]:4);
end.

Пример ввода:
20
10
Пример вывода:
Array:
  10  16   0  60  23   4  22 -20   4  55
Final array:
   0  36 -10  80  13  24  12   0  -6  75  

#include "math.h"#include "iostream"
using namespace std;
int main(){int a, n, max, min;int max_i, max_k, min_i, min_k;//ввод размера массиваcin>>a;cin>>n;
//объявление массиваint** a = new int* [a]; for(int i = 0; i < n; i++) { a[i] = new int [a]; }
//ввод первого массива for(int i = 0; i < a; i++) { for(int k = 0; k < n; k++) { cin>>a[i][k]; } } //Инициализация max, min; max=a[0][0]; min=a[0][0]; //поиск максимума for(int i = 0; i < a; i++) { for(int k = 0; k < n; k++) { if(max<a[i][k]) { max=a[i][k]; max_i=i; max_k=k; } } } //поиск минимума for(int i = 0; i < a; i++) { for(int k = 0; k < n; k++) { if(min>a[i][k]) { min=a[i][k]; min_i=i; min_k=k; } } }
//Max and Min меняются местамиswap(a[max_i][max_k],a[min_i][min_k]);getch();return 0;}