Генерация всех перестановок множества
//Генерация всех перестановок множества
#include<iostream>
usingstd::cin;
usingstd::cout;
//Множество
int* A;
//Размер множества
intsize;
//Выводмножества
void Output()
{
for(inti=0;i<size;i++)
cout<<A[i]<<" ";
cout<<"\n";
}
//Поменять местами два элемента множества
voidSwap(intx,int y)
{
int temp = A[x];
A[x] = A[y];
A[y] = temp;
}
//Сгенерировать следующее разбиение
voidGenerate(int k)
{
//Генерация завершена, вывести множество
if (k==size)
{
Output();
}
else
{
//Продолжить генерацию
for(int j=k;j<size;j++)
{
Swap(k,j);
Generate(k+1);
Swap(k,j);
}
}
}
int main()
{
std::cout<<"Size: ";
std::cin>>size;
if(size<=0)
return 0;
//Заполнениемножества
A = new int[size];
for(inti = 0;i<size;i++)
A[i] = i+1;
Generate(0);
delete[] A;
return 0;
}
АлгоритмДейкстры
//АлгоритмДейкстры
#include <iostream>
#include <string>
usingstd::cin;
usingstd::cout;
usingstd::string;
//Количество вершин
int n;
//Матрица стоимостей
//Расстояние между вершинами - положительное число
//Отсутствие ребра между вершинами - 0
int **C;
//Число, превышающее максимальный элемент матрицы(аналог бесконечности)
int max;
//Вычисление max
voidSetMax()
{
max=0;
for (inti=0; i<n; i++)
for (int j=0; j<n; j++)
max=max+C[i][j];
|
|
|
max=max+1;
}
//Проверка на наличие числа num в массиве
boolin_arr(intnum, int *arr)
{
bool result=false;
for (inti=0; i<n-1; i++)
if (arr[i]==num)
result=true;
returnresult;
}
//Перевод числа в строку
stringinttostr(intnum)
{
charbuf[10];
itoa(num, buf, 10);
return string(buf);
}
int main()
{
cout<< "Number of vertexes:" << "\n";
cin>> n;
//Номер вершины-источника
int a;
cout<< "Main vertex: " << "\n";
cin>> a;
a--;
cout<< "Vertexes: " << "\n";
//Ввод матрицы стоимостей
C = new int*[n];
for(inti=0;i<n;i++)
C[i] = new int[n];
for(inti=0;i<n;i++)
for(int j=0;j<n;j++)
cin>> C[i][j];
cout<< "\n";
SetMax();
//Вершины, помеченные, как посещенные
int *S=newint[n-1];
//Кратчайшие расстояния к вершинам из вершины-источника
int *D=new int[n];
|
|
|
//Последние промежуточные вершины на маршруте
int *P=newint[n];
//Вспомогательные переменные
intw,min;
//Инициализация S(Ни одна вершина еще не посещена)
for (int k=0; k<n-1; k++)
{
S[k]=-1;
}
S[0]=a;
//Инициализация P и D
for (inti=0; i<n; i++)
{
if (C[a][i]==0)
D[i]=max;
else
D[i]=C[a][i];
P[i]=a;
}
//АлгоритмДейкстры
for (inti=1; i<n-1; i++)
{
min=max;
for (int k=0; k<n; k++)
{
//Если расстояние до k меньше текущего минимального и при этом
//k еще не посещена и не является вершиной-источником, то установить
//новыйминимум
|
|
|
if (D[k]<min && !in_arr(k,S) && k!=a)
{
w=k;
min=D[k];
}
}
if (min==max) break;
//Вершинаiпосещена
S[i]=w;
for (int j=0; j<n; j++)
{
//Если вершина j не посещена и путь от нее до текущей вершины w существует
//и расстояние от a до j >= сумме расстояний от a до w и от w до j,
//то установить новое расстояние от a до j
if (!in_arr(j,S) && C[w][j]!=0 && (D[w]+C[w][j])<=D[j])
{
P[j]=w;
D[j]=D[w]+C[w][j];
}
|
|
|
}
}
//Выводрезультатов
int t;
stringstr;
for (inti=0; i<n; i++)
{
if (i!=a && C[P[i]][i]!=0)
{
str=inttostr(i+1);
t=P[i];
do
{
if (str!=inttostr(i+1))
t=P[t];
str=str+">-"+inttostr(t+1);
}
while (t!=a);
str = string(str.rbegin(),str.rend());
cout<<str<< " = " <<inttostr(D[i]) <<"\n";
}
}
delete[] S;
delete[] P;
delete[] D;
for(inti=0;i<n;i++)
delete[] C[i];
delete[] C;
}
Генерация кода Фано
#include<iostream>
#include <string>
usingstd::cin;
usingstd::cout;
usingstd::string;
//Массивсимволов
char* A;
//Массив частот
double* F;
//Размермассивов
intsize;
//Функция для поиска кода для каждой буквы
//ch - '0' или '1', последний добавленный бит
//full - полный текущий код буквы(строка из нулей и единиц)
//start, end - интервал
void Next(char ch, string full, int start, int end)
{
//Половина суммы всех частот и сумма частот, не превышающая hS
doublehS,S;
//Счетчик
intm;
//Строка для записи кода числа
stringstr;
str=full+ch;
//Если размер интервала равен 1, то код сгенерирован, вывести его
if(start==end)
{
cout<< A[start] << " = " <<str<< " ";
return;
}
//Нахождение половины суммы всех частот
hS=0;
for(inti=start;i<=end;i++)
hS=hS+F[i];
hS=hS/2;
//Поиск позиции, примерно делящей алфавит на две части
S=0;
inti=start;
m=i;
while((S+F[i]<hS) && (i<end))
{
S=S+F[i];
i++;
m++;
}
//Генерация следующей части кода для первой части массива
Next('1', str, start, m);
//Генерация следующей части кода для второй части массива
Next('0', str, m+1, end);
}
//Сортировка массивов
//(алгоритм требует наличия невозрастающей последовательности частот)
void Sort()
{
for (inti=0; i<size; i++)
{
int k=i;
for (int j=i+1; j<size; j++)
if (F[j]>F[k])
k=j;
if (i!=k)
{
char t = A[i];
A[i]=A[k];
A[k]=t;
double temp = F[i];
F[i]=F[k];
F[k]=temp;
}
}
}
int main()
{
//Созданиемассивов
cout<< "Size: ";
cin>> size;
if(size<=0)
return 0;
A = new char[size];
F = new double[size];
//Вводбукв
cout<< "Input letters:";
for(inti=0;i<size;i++)
{
cin>>A[i];
}
//Вводчастот
for(inti=0;i<size;i++)
{
cout<< "Frequency for " << A[i] << ": ";
cin>> F[i];
}
//Сортировка
Sort();
//Начало генерации кода
Next(' ',"", 0, size-1);
return 0;
}
Дата добавления: 2018-04-05; просмотров: 170; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!