маленькая, но не менее умная задача
есть какое-то вещественное C
надо найти такие целые A в [A_min..A_max], B в [B_min..B_max] так
чтобы A / B было максимально близко к C ( скажем c = A/B, надо Min (c-C)^2 )
highly professional scums
the place where select game development veterans rant about life, universe, and everything
Balmer:
За O(log2(max((A_max-A_min), (B_max-B_min)))) решается строчек в 15 кода.
16 December 2009, 12:12 pmLoyso:
solve :: (Int,Int) -> (Int,Int) -> Float -> (Int, Int)
solve (a_min,a_max) (b_min,b_max) c =
let err a b c = ( fromIntegral a / fromIntegral b - c ) ^ 2
searchspace = [ (a, b, err a b c ) | a <- [a_min..a_max], b <- [b_min..b_max] ]
min (a,b,e) [] = (a,b,e)
min (a,b,e) ( (xa,xb,xe):xs ) | xe < e = min (xa,xb,xe) xs
| otherwise = min (a,b,e) xs
solve’ ((xa,xb,xe):xs) = (a,b) where (a,b,e) = min (xa,xb,xe) xs
in solve’ searchspace
Квадрат, куча памяти, зато интроспективно :)
16 December 2009, 2:24 pmА вообще оптимизационная задача лиейного программирования вроде (симплекс метод/градиентный спуск).
Loyso:
пс: мой пост игнорируйте, пожалуйста - просто упражнение на скорость.
16 December 2009, 3:08 pmLoyso:
> Balmer
16 December 2009, 3:40 pmПеребрать по брезенхему варианты на прямой - это будет O(max((A_max-A_min), (B_max-B_min)). Расскажи, плиз, откуда log2.
Balmer:
> Loyso
Да, что-то поторопился. Вчера вечером пробовал написать алгоритм с log2, не получилось.
17 December 2009, 11:02 amXunter:
ну за линейное время от max((A_max-A_min), (B_max-B_min))
17 December 2009, 7:06 pm- решение очевидно.
Xunter:
даже за O(min((A_max-A_min), (B_max-B_min)))
17 December 2009, 7:09 pmLoyso:
> решение очевидно.
18 December 2009, 4:28 amВообще-то (я так понял) провокационно предполагается, что есть аналитическое решение О(1).
Balmer:
Сегодня вечером написал решение за O(log2((A_max-A_min)*(B_max-B_min))), так как этот log2 от поиска в сортированном массиве, то можно и log1000 сделать при желании. Правда он в prebuild жрёт (A_max-A_min)*(B_max-B_min)*12 памяти.
18 December 2009, 10:32 amlook4awhile:
Ну, собственно, вот
http://en.wikipedia.org/wiki/Continued_fraction
конкретно нас интересует Best rational approximations, и, разумеется, truncation
и, конечно, всякое дополнительное теоретическое чтение
http://en.wikipedia.org/wiki/Farey_sequence
http://en.wikipedia.org/wiki/Stern-Brocot_tree
меня эта задача точно так-же поставила в тупик, как и остальных участников треда
совершенно замечательный мат-аппарат в своё время прошёл совсем мимо меня
ну да я сам себе злобный буратина. зато теперь я умею “много гитик” :)
желающим рекомендую почитать ещё и
21 December 2009, 11:37 amhttp://perl.plover.com/yak/cftalk/