Краен срок за предаване: 2016.03.17 23:59:59
Точки: 5
Напишете функция long hash(char *word), която пресмята хеш стойността на дадена дума. Хеширане на данни представлява преобразуването на входни данни с произволна дължина към изходни с фиксирана. За хеширане могат да се използват различни алгоритми. Програмата трябва да чете от стандартния вход дума с големина до 200 символа и да изведе хеша на стандартния изход.
Във вашата функция използвайте следният алгоритъм:
- Дефинирайте начална стойност: 42
- За всеки символ от думата (може да ползвате strlen за да вземете големината на думата):
- Вземете ASCII кода
- Умножете го по позицията на символа в думата (започва от 1, не от 0)
- Сумирайте всички получени стойности - това е хешът
Функцията трябва да връща пресметнатото число.
Примерен вход:
tovaeprimerenvhod
Изход:
16512
Ограничения:
- Думата може да има най-много 200 символа
Точки: 7
Дефинирайте структура struct occurance_t съдържаща хешът на дума и броят пъти, които се среща.
Четете от стандартния вход думи докато не срещнете думата "vsmisal". Изведете на стандартния изход колко пъти се среща най-често срещаната дума и нейният хеш. Използвайте хеширащата функция описана в задача 1.
Ограничения:
- Думата може да има най-много 200 символа
- Няма да бъдат въведени повече от 2000 думи преди "vsmisal".
- Ще бъде въведена поне една дума преди "vsmisal".
Пояснение:
- Ако има повече от една думи с равен брой срещания, и този брой е най-голям, се очаква да се изведе първата.и
- Пример: ако всички думи се срещат по веднъж се очаква да се изведе хешът на първата
- Пример: ако няколко думи се срещат по два пъти се очаква да се изведе хешът на двойката, която се среща първа
- Ако две думи имат еднакъв хеш, то двете думи ги считаме за еднакви
- Думите "vsmisal" и "Vsmisal" се считат за ралични думи
- Всмисъл техните хешове са различни
Примерен вход:
do you even yaml bro rofl vsmisal
Изход:
2 1116
Точки: 7
Нашият алгоритъм за смятане на хеш има един проблем. Всмисъл появяват се т.нар колизии или две различни думи с един и същи хеш. Напишете програма, която чете думи докато не намери точно 4 думи с еднакъв хеш. За целта добавете поле към структурата occurance_t което да бъде масив от стрингове на думите, както и поле за брой на срещанията. Да се изведат колизиращите думи (без повторения) в нарастващ ред по хеш. Редът на думите с еднакъв хеш трябва да бъде същият както реда на прочитане от стандартния вход.
Формат на изхода:
хешът дума1 дума2
хешът дума1 дума2 дума3 дума4
хешът дума1 дума2 дума3
В изходa не трябва да фигурират [].
Ограничения:
- Думата може да има най-много 200 символа
- Няма да бъдат въведени повече от 3000 думи преди срещането на четирите колизиращи думи.