ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
(СПбГУТ)
Факультет инфокоммуникационных Сетей и систем (иксс)
кафедра программной инженерии и вычислительной техники (пиивт)
Лабораторная работа №7
«Поиск кратчайшего пути на графах»
Дисциплина: «Алгоритмы и Структуры Данных»
Выполнили: Студент группы ИКПИ-92 Козлов Никита
Тюришев Матвей
Принял: к.т.н., доцент кафедры ПИиВТ
Дагаев А.В.
Пример работы
Дана последовательность символов a[6] = {'v','o','l','v','o','\0'};
На каждом шаге (шаг – символ, кроме нулевого) производится вычисление: сложение по модулю 2 в степени битности хеша (в данном случае используется 32 бита) с входной последовательностью и умножение на простое число (16777619).
Вычисление основывается на обращении к предыдущим значениям, поэтому предусмотрен Х0 = 2166136261.
Таким образом, вычисляется всё по формулам:
Описание программы
Программа включает в себя несколько функций, как:
unsigned int FNV1Hash (char *buf)
char getRandomChar()
Функция 1 – сам алгоритм FNV, возвращающий хеш-сумму для аргумента в виде массива символов.
Функция 2 – получение случайного символа. Возвращает один из 52 символов – строчные и заглавные латинские буквы.
Использовались классы:
fstream – вывод полученных результатов в файл
iostream – работа функций ввода/вывода
conio.h – работа функции getch()
Код программы
#include <iostream>
#include <conio.h>
#include <chrono>
#include <fstream>
#define k1 5000
using namespace std;
const unsigned FNV_32_PRIME = 0x01000193;
char getRandomChar()//Функция случайного символа
{
const char str[] = {'A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H', 'h', 'I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o', 'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v', 'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z'};
return str[rand() % 52]; //любая из 52 букв
}
unsigned int FNV1Hash (char *buf)
{
unsigned int hval = 0x811c9dc5; // FNV0 hval = 0
int i=0;
while (*buf)
{
hval ^= (unsigned int)*buf++;
hval *= FNV_32_PRIME;
i++;
}
return hval;
}
int main()
{
setlocale(LC_ALL, "Russian");
cout << "ожидайте...\n";
int stepcount = 20;
int size = 100000;
unsigned int* hashsumm = new unsigned int [size];
int *collcount = new int [stepcount];
for (int i=1; i<=stepcount; i++)
{
int coll_count=0;
char **hashfunc = new char* [size];
for (int k = 0; k < size; k++)
{
hashfunc[k] = new char [4];
for (int j=0; j<4; j++)
hashfunc[k][j]=getRandomChar();
hashfunc[k][3]='\0';
hashsumm[k] = FNV1Hash(hashfunc[k]);
}
size -= k1;
for (int k=0;k<size;k++)
for (int j=k+1;j<size; j++)
if (hashsumm[k]==hashsumm[j])
coll_count++;
collcount[i-1]=coll_count;
cout << collcount[i-1] << " - количество коллизий\n";
for (int k = 0; k < size; k++)
delete [] hashfunc[k];
}
fstream fout ("rez.csv", ios::out);
for (int i=1; i<=stepcount; i++)
fout << collcount[i-1] << endl;
fout.close();
delete [] hashsumm;
delete [] collcount;
getch();
return 0;
}