Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Реализация. Шаг 1. Генерируем элементы исходного массива заданной размерности с помощью датчика случайных чисел





Шаг 1. Генерируем элементы исходного массива заданной размерности с помощью датчика случайных чисел. Одновременно проверяем элементов на уникальность. Выводим последовательноссть на экран.

 

cout << "SourceMas: \n";

int SourceMas [ N ]; // исходный массив генерируемых чисел

srand (time (NULL));

for (k = 0; k < N; ++k) // k - индекс массива SourceMas

{

int flag=0;

while (flag==0)

{

SourceMas [ k ] = rand ()% 99999 + 100000 * (rand () % 9 + 1);

flag=1;

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

if (SourceMas [k]== SourceMas [j]) flag=0;

cout << SourceMas [ k ] << "\t"; // вывод на экран

 

 

Шаг 2. Начинаем работу с хеш-таблицей, занулив её.

 

for (ht = 0; ht < t; ++ht) // зануляем хеш-таблицу

HashTabl [ ht ] = 0;

 

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

 

for (ht = 0; ht < N; ++ht) // заполняем хеш-таблицу

{

adres = ((SourceMas [ht] + 18)/ 61) % t; // вычисляем непосредственно хеш функцию

int adres0 = adres;

if (HashTabl [adres] == 0) // если ячейка хеш таблицы пустая

{

HashTabl [adres] = SourceMas [ht]; // то записываем в неё значение из исхтаблицы непосредственно по адресу=ключу

kz++;

}

else // иначе

{

while (HashTabl [ adres ]!= NULL) // пока не найдётся пустая ячейка

{

adres = (adres0 + np*np) % t; // применяем метод квадратичной пробы, где np-№ пробы, adres0-нач значение ключа

++np;

}

chp++;

HashTabl [ adres ] = SourceMas [ ht ];

kz++;

}

}

 

 

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

 

cout << "\nHashTabl: \n";

for (ht = 0; ht < t; ++ ht)

printf("%i: %i\t",ht,HashTabl [ ht ]);

printf("Koeff.zapoln.tabl: %f \n",float(kz)/float(t));

printf("Srednee chislo prob:%f\n",float(chp)/float(kz));

 

Шаг 4. В результате работы программы получим следующий результат:

Вывод

 

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







Дата добавления: 2015-06-15; просмотров: 548. Нарушение авторских прав; Мы поможем в написании вашей работы!




Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


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


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

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

Тема: Кинематика поступательного и вращательного движения. 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью, проекция которой изменяется со временем 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью...

Условия приобретения статуса индивидуального предпринимателя. В соответствии с п. 1 ст. 23 ГК РФ гражданин вправе заниматься предпринимательской деятельностью без образования юридического лица с момента государственной регистрации в качестве индивидуального предпринимателя. Каковы же условия такой регистрации и...

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

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

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия