Проблема BestApproximationDiv2 в Haskell


Задача-написать функцию findFraction maxDen количество найти короткое, но хорошее рациональное приближение к десятичной записи числа — проблема заявление на Топкодере:

Учитывая долю Ф = А/B, где 0 <= А < Б, его качество аппроксимации в число рассчитывается следующим образом:

  • Пусть s-десятичной дроби (конечным или бесконечным) представительство Ф.
  • Пусть N-количество цифр после запятой в количестве. Если число имеет незначащие нули, все они считаются значимыми и учитываются Н.
  • Если S Infinite или количество цифр после десятичной точки в S больше N, рассматривать только первые N знаков после десятичной точки в с. усечь остальные цифры без выполнения какой-либо округления.
  • Если количество цифр после десятичной точки в S меньше N, дописывать незначащие нули справа, пока существует ровно N цифр после десятичной точки.
  • Качества аппроксимации является количество цифр в длинный общий префикс и номер. Самый длинный общий префикс двух чисел является самой длинной строки, которая является префиксом десятичные представления чисел с нулями. Например, "3.14" - это самый длинный общий префикс 3.1428 и 3.1415.

[...] Вы только разрешено использовать дроби, где знаменатель меньше или равен maxDen. Найти приближенное значение Ф = А/B от числа такие, что 1 <= Б <= maxDen, 0 <= А < B и качества аппроксимации максимальна. Возвращает строку в формате "А/Б х точных цифр" (без кавычек), где A/B-это приближение вы нашли и X является его качество. Если есть несколько таких приближений, выбрать один с наименьшим знаменателем среди всех из них. Если есть еще галстук, выбирать среди них те, с наименьшим числителем.

import Data.Char
import Data.List
import Data.Maybe

showResult :: (Int, Int, Int) -> String
showResult (a, b, x) = show a ++ "/" ++ show b ++ " has "
                    ++ show x ++ " exact digits"

compareDigits :: [Int] -> [Int] -> Ordering
compareDigits xs [] = EQ
compareDigits (x:xs) (y:ys) = case compare x y of
                                  EQ -> compareDigits xs ys
                                  order -> order

toDigit :: Char -> Int
toDigit c = ord c - ord '0'

preciseDivision :: Int -> Int -> [Int]
preciseDivision a b = div a' b : preciseDivision (mod a' b) b
           where a' = 10 * a

estimate :: [Int] -> Double
estimate = sum . zipWith (flip (/)) (iterate (*10) 10) .
           map fromIntegral

bestNumerator :: [Int] -> Double -> Int -> Maybe Int
bestNumerator ds p b =
    case find atLeast . map (pair ds b) $ [pivot .. ] of
        Just (a, EQ) -> Just a
        otherwise -> Nothing
    where pivot = truncate $ p * fromIntegral b
          pair ds b a = (a, compareDigits (preciseDivision a b) ds)
          atLeast (a, order) = order /= LT

bestResult :: Int -> [Int] -> Maybe (Int, Int, Int)
bestResult n ds = fromMaybe Nothing . find isJust .
                  map (toResult ds $ estimate ds) $ [1..n]
    where toResult ds p b = case bestNumerator ds p b of
                                Just a -> Just (a, b, 1 + length ds)
                                Nothing -> Nothing

findFraction' :: Int -> [Int] -> (Int, Int, Int)
findFraction' n = fromJust . last . takeWhile isJust .
                  map (bestResult n) . inits

findFraction :: Int -> String -> String
findFraction n = showResult . findFraction' n .
                 map toDigit . tail . tail

Я очень волнуюсь по bestNumerator и bestResult здесь. Я использую найдите фразеологизм, который я сам придумал, и интересно, чище, более Haskelly альтернатив.



Комментарии
2 ответа

Хммм, не так много идей, только синтаксис:

showResult :: (Int, Int, Int) -> String
showResult (a, b, x) = concat [show a, "/", show b, " has ", show x, " exact digits"]

preciseDivision :: Int -> Int -> [Int]
preciseDivision a b = let (d,r) = divMod (10*a) b in d : preciseDivision r b

...where toResult ds p b = fmap (\a -> (a, b, 1 + length ds)) $ bestNumerator ds p b

5
ответ дан 11 октября 2011 в 07:10 Источник Поделиться

Заказ является экземпляром моноидом.

import Data.Monoid

compareDigits :: [Int] -> [Int] -> Ordering
compareDigits _ [] = EQ
compareDigits (x:xs) (y:ys) = compare x y `mappend` compareDigits xs ys

toDigit точно не надо; сведения.Голец имеет digitToInt, который делает примерно то же самое. Разница в том, что он поддерживает шестнадцатеричных чисел и будет выполнена, если символ не является допустимым шестнадцатеричное число, в то время как ваша функция принимает десятичную цифру, является более эффективным, но будет молча давать неверные результаты для некурящих цифр.

Ли вы заменить его или нет, хотя, toDigit обратно, поскольку функция принимает цифру и дает числовое значение.

В bestNumeratorс парой, вы тени в ДС и Б параметров. Что смущает меня. В bestResult, toResult также имеет тенизации ДС.

В общем, я думаю, что многие Ваши имена параметров являются слишком короткими. Я понимаю, что это распространено в Haskell, но я все еще нахожу это отвратительным за то, что не абстрактно. Например, Н вместо maxDenominator (или maxDen, как в постановке проблемы, а "Ден" - это непонятная аббревиатура).

1
ответ дан 3 февраля 2014 в 07:02 Источник Поделиться