[Homework] Algorithms - Sorting and Searching - Problem 2 - Софтуерен университет

djc_bg2015 923 Точки

[Homework] Algorithms - Sorting and Searching - Problem 2

Здравейте,

стигнах до задача 2 от домашното: Implement Interpolation Search

Използвайки псевдо кодове които намерих из нета a и този който е в слайдовете, успявам да го докарам до работещ вариант, когато колекцията е от числа.

Но как да стане когато елемента който търсим е от тип Т и няма как да намеря Mid позицията по формулата:

int mid = low + ((needle - list[low]) * (high - low)) / (list[high] - list[low]);

тъй като няма как от нещо което незнам какво е да извадя число

Тагове:

06/10/2015 00:00:31 Структури от данни и алгоритми 06/10/2015 00:04:02

Виж всички отговори

ttitto 1153 Точки

Този проблем, че на генеричен клас не можем да зададем условие Т да имплементира някакъв оператор го разреших чрез делегати. На сортабъл колекцията подавам в нов конструктор два делегата Func<T, T, int> Multiply и Func<T,T,int> Subtract. В класа, който ползва колекцията (в случая компонентните тестове) се имплементират два метода, които връщат инт и се подават при инициализацията на сортабъл колекцията. Кодът може да се види тук ред 23 и 95 и употреба в тестовете

Другото, което си мислех е, дали не може да се използва getHashCode за приравняване на обект от тип T към int и на тази основа да се прави интерполацията. Но първият вариант ми се стори по-привлекателен и реших да се занимавам само с него.

11/10/2015 11:08:59

dim4o 288 Точки

Интересно е решението с делегатите. Единствено на 111-ти и 115-ти ред според мен изразите в условията трябва да са с различни знаци, за да работи правилно.

И аз мислех за GetHashCode(), но не съм го пробвал, защото ако o1.CompareTo(o2) > 0 то o1.GetHashCode() > o2.GetHashCode() изобщо не е задължително. Дори по някакъв GetHashCode() имплементацията да се обвърже с CompareTo() пак няма да стане в общия случай.

11/10/2015 15:17:14

ttitto 1153 Точки

Да, трябва да обърна знака на 115ти ред. Благодаря!

11/10/2015 15:30:35

dim4o 288 Точки

Относно тестовете: аз правя нещо от сорта Assert.AreEqual(element, collection[result]). Така независимо дали има повтарящи се елементи пак може да се тества за правилна работа. Иначе е вярно, че ако имаме {.....3, 4, 4, 4.....} и търсим 4 няма как да знаем на кой индекс ще ударим.

11/10/2015 15:38:05

Виж всички отговори