маленькая, но не менее умная задача

есть какое-то вещественное C
надо найти такие целые A в [A_min..A_max], B в [B_min..B_max] так
чтобы A / B было максимально близко к C ( скажем c = A/B, надо Min (c-C)^2 )

  • Balmer

    За O(log2(max((A_max-A_min), (B_max-B_min)))) решается строчек в 15 кода.

  • http://www.creative-assembly.com.au/ Loyso

    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

    Квадрат, куча памяти, зато интроспективно :)
    А вообще оптимизационная задача лиейного программирования вроде (симплекс метод/градиентный спуск).

  • http://www.creative-assembly.com.au/ Loyso

    пс: мой пост игнорируйте, пожалуйста – просто упражнение на скорость.

  • http://www.creative-assembly.com.au/ Loyso

    > Balmer
    Перебрать по брезенхему варианты на прямой – это будет O(max((A_max-A_min), (B_max-B_min)). Расскажи, плиз, откуда log2.

  • Balmer

    > Loyso

    Да, что-то поторопился. Вчера вечером пробовал написать алгоритм с log2, не получилось.

  • Xunter

    ну за линейное время от max((A_max-A_min), (B_max-B_min))
    - решение очевидно.

  • Xunter

    даже за O(min((A_max-A_min), (B_max-B_min)))

  • http://www.creative-assembly.com.au/ Loyso

    > решение очевидно.
    Вообще-то (я так понял) провокационно предполагается, что есть аналитическое решение О(1).

  • Balmer

    Сегодня вечером написал решение за O(log2((A_max-A_min)*(B_max-B_min))), так как этот log2 от поиска в сортированном массиве, то можно и log1000 сделать при желании. Правда он в prebuild жрёт (A_max-A_min)*(B_max-B_min)*12 памяти.

  • look4awhile

    Ну, собственно, вот

    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

    меня эта задача точно так-же поставила в тупик, как и остальных участников треда
    совершенно замечательный мат-аппарат в своё время прошёл совсем мимо меня
    ну да я сам себе злобный буратина. зато теперь я умею “много гитик” :)

    желающим рекомендую почитать ещё и
    http://perl.plover.com/yak/cftalk/