- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
--Поиск минимальной выпуклой оболочки
import Data.List; import Data.Ord
--общие функции и типы
data Point = P{x::Float,y::Float}
deriving (Show,Eq)
getRotate a b c = baX * cbY - baY * cbX
where baX = x b - x a; baY = y b - y a;
cbX = x c - x b; cbY = y c - y b;
sortFunc a b c
|k < 0 = LT
|k == 0 = compare (long a c) (long a b)
|k > 0 = GT
where k = getRotate a b c
long a b = (x b - x a)*(x b - x a) + (y b - y a)*(y b - y a)
getLeftPoint = minimumBy (comparing x)
--Джарвис
getMBOJarvis l = mboJ fp l fp
where fp = getLeftPoint l
mboJ current list fp
|getRotate current next fp > 0 = []
|True = current : mboJ next listWOC fp
where listWOC = filter ((/=)current) list;
next = minimumBy (sortFunc current) listWOC;
--Грехем
getMBOGragam = tail.throwGraham.sortGraham
sortGraham list = fp:sortBy (sortFunc fp) list
where fp = getLeftPoint list
throwGraham (f:s:t) = mboG (s:f:[]) t
mboG <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="dfb9ac9f">[email protected]</a>(f:s:st) <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="80f3eec0">[email protected]</a>(h:t)
|sortFunc s f h == GT = mboG (s:st) sn
|True = mboG(h:fs) t
mboG <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="d0b6a390">[email protected]</a>(f:st) <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="76051836">[email protected]</a>(h:t) = mboG(h:fs) t
mboG l [] = l
--тесты
testList1 = [P 0 (-1), P (-1) 0, P 0 1,P 1 0,P (-0.5) (-0.5),P 0.5 (-0.5),P (-0.5) 0.5,P 0.5 0.5,P 0 0]
testList2 = [P 0 0, P 1 0, P 0 1,P 2 0,P 1 1,P 0 2,P 2 1,P 1 2,P 2 2]
testJ1 = mapM_ print $ getMBOJarvis testList1
testG1 = mapM_ print $ getMBOGragam testList1
testJ2 = mapM_ print $ getMBOJarvis testList2
testG2 = mapM_ print $ getMBOGragam testList2
Да и у меня основная цель - не атрофировать фунцианальщину.
Вообще на окамле довольно просто лабы писать, там ведь от эффектов никто не ограждает, пиши себе в матрицы сколько влезет, и производительность предсказуемая.
С хацкелем хардкорнее - там половину нормальных алгоритмов (классические линейные строковые вроде КМП, обходы графов, преобразования матриц, деревья фенвика, тыщи их) без монады ST не изобразишь, а ленивость добавляет веселья при оптимизации.
OK, Jarvis
2) Используй otherwise
3) Почему s : f : [] вместо [s, f] ?
4) Почему ((/=) current) вместо (current /=) ?
3 и 4 - хз, на автомате писал
кофейном?
> кофейном?
на детерминированном или недетерминированном кофейном автомате?
Это была лаба по вычислительной геометрии?
Удалось потроллить? 🙂
Есть такое
С хацкелом тоже самое. Пришёл выебщик сдавать лабу на экзотическом языке, и сходу получил десяток колких вопросов.
http://code.jsoftware.com/wiki/Studio/IdiosyncraticIntroduction
А вообще, мне нравится loopless code, но синтаксис J — ет писдес
Во чьо компилил? В ДЖэй ?
Я плюшевый тюлень.
И телом нежным впитываю тень.
В шабата день.
Отвень.
Ваш этот J интерпретатор.
На нём Кегдану не дано.
Слепить брейнфака конпелятор.
вызывает из коробки глагол по индексу.
ЗЫ. 9: и тп — это глагол, кот-й возвращает константу
А в тацитной эта хня не нужна, векторный же язык, можно с помощью рангов ибашить поэлементно или построчно.
ЗЫ. ещё есть ^: для возведения глагола в степень. Можно въебать бесконечную степень, и глагол будет ибашить пока результат не перестанет меняться.