Haskell: Как запомнить этот алгоритм? - PullRequest
Новая
       61

Haskell: Как запомнить этот алгоритм?

0 голосов
/ 13 мая 2018

Я написал это решение проблемы замены монет на HackerRank : 

makeChange :: Int -> [Int] -> Int
makeChange n ys = go n (sort ys)
    where go _ [] = 0
          go n (x:xs)
            | x == n = 1
            | x > n = 0
            | otherwise = (makeChange n xs) + (makeChange (n - x) (x:xs))

Однако время ожидания некоторых из более крупных тестовых случаев истекло. Я видел эту статью о реализации мемоизации с использованием let связываний, но в основном это происходило у меня над головой, и я не уверен, как бы я реализовал это здесь. Любая помощь?

Я переписал его и получил значительное улучшение производительности, но все еще не могу выполнить упражнение по рангу хакера: 

makeChange' :: Int -> [Int] -> Int
makeChange' =
    let go _ [] = 0
        go n (x:xs)
          | x == n = 1
          | x > n = 0
          | otherwise = (makeChange' n xs) + (makeChange' (n - x) (x:xs))
    in go

f (x:y:xs) = makeChange' x ys
    where ys = sort xs
main = interact $ show . f . map read . words

Я переместил предварительную сортировку в промежуточную функцию f, которую я также использую для обработки ввода от Hacker Rank. Они дают вам строку с целью изменения, длиной массива изменений и массивом единиц изменения. Я использую f для удаления длины из ввода.

Ответы [ 3 ]

0 голосов
/ 13 мая 2018

Эта проблема не требует запоминания. Если a - это список бесконечной длины , где a !! n - это общее количество способов сделать общую сумму n с некоторым набором монет, и вы получите новую отдельную монету достоинством x, вы можете обновить список a до нового списка b, используя факты:

  • Первые x элементы не изменятся; потому что вы не можете использовать новую монету на сумму менее x. итак, take x a.

  • Для остальных элементов: 

    b(n) = a(n) + b(n - x)

    , где первое слагаемое означает, что новая монета вообще не используется, а 2-е слагаемое использует ее хотя бы один раз.

Это может быть просто реализовано с использованием правой складки с начальным значением [1, 0, 0, ...], потому что без монет единственная сумма, которую вы можете сделать, равна нулю. Хаскель лень здесь тоже очень полезна: 

solve :: Int -> [Int] -> Int
solve n xs = (foldr go (1:repeat 0) xs) !! n
  where go x a = let b = (take x a) ++ zipWith (+) b (drop x a) in b

, то: 

\> solve 4 [1, 2, 3]
4
\> solve 10 [2, 5, 3, 6]
5

как в примерах в вопросе.

0 голосов
/ 14 мая 2018

Я попытаюсь продемонстрировать, как работает код behzad.nouri, чтобы понять его сам:

Учитывая лень Хаскелла, мы наблюдаем, что !! n означает, что наш окончательный список будет оцененк этому (n+1) й элемент.Наш основной блок для каждой монеты: 

let b = (take x a) ++ zipWith (+) b (drop x a) in b

Здесь есть небольшая хитрость, которая работает, потому что b - это список.Обратите внимание, что подобный тип ссылки на себя не сработал бы, если бы b было целым числом.Допустим, наша единственная монета была 2: 

 > let b = (take 2 [1,0,0,0,0]) ++ zipWith (+) b (drop 2 [1,0,0,0,0]) in b
=> [1,0,1,0,1]

(что означает один способ сделать ноль, один способ сделать два и один способ сделать четыре.) Что происходит, то b создается рекурсивно какна него ссылаются до тех пор, пока не будет совпадения длины для оценки почтового индекса: 

 > zipWith (+) [] (drop 2 [1,0,0,0,0])
=> []
-- But we prepended [1,0] so the next `b` is [1,0]
 > zipWith (+) [1,0] (drop 2 [1,0,0,0,0])
=> [1,0]
-- But we prepended [1,0] so the next `b` is [1,0,1,0]
 > zipWith (+) [1,0,1,0] (drop 2 [1,0,0,0,0])
=> [1,0,1]
-- But we prepended [1,0] so the result matching the length is [1,0,1,0,1]

Теперь давайте воспользуемся этими знаниями, чтобы выполнить solve 4 [1,2,3]: 

let b = (take 3 [1,0,0,0,0]) ++ zipWith (+) b (drop 3 [1,0,0,0,0]) in b

take 3 [1,0,0,0,0] -- n+1 elements are evaluated from the infinite list
=> [1,0,0]

++       [0,0] -- drop 3 from [1,0,0,0,0]
     (+) []
     =>  []
     -- prepend [1,0,0]
     =>  [1,0,0]

++       [0,0]
     (+) [1,0,0]
     =>  [1,0]
     -- prepend [1,0,0]
     =>  [1,0,0,1,0]

Это один из способов сделатьноль и один способ сделать три.Далее: 

let b = (take 2 [1,0,0,1,0]) ++ zipWith (+) b (drop 2 [1,0,0,1,0]) in b

take 2 [1,0,0,1,0]
=> [1,0]

++     [0,1,0]
   (+) []
   =>  []
   -- prepend [1,0]
   =>  [1,0]

++     [0,1,0]
   (+) [1,0]
   =>  [1,1,0]
   -- prepend [1,0]
   =>  [1,0,1,1,0]

++     [0,1,0]
   (+) [1,0,1,1,0]
   =>  [1,1,1]
   -- prepend [1,0]
   =>  [1,0,1,1,1]

Это один способ сделать 0, один способ сделать 2, один способ сделать 3 и один способ сделать 4. Далее: 

let b = (take 1 [1,0,1,1,1]) ++ zipWith (+) b (drop 1 [1,0,1,1,1]) in b

Этотот, на котором больше всего итераций, начиная с b, построен только из одного элемента 

take 1 [1,0,1,1,1]
=> [1]

++   [0,1,1,1]
 (+) []
 =>  []
 -- prepend [1]
 =>  [1]

++   [0,1,1,1]
 (+) [1]
 =>  [1]
 -- prepend [1]
 =>  [1,1]

++   [0,1,1,1]
 (+) [1,1]
 =>  [1,2]
 -- prepend [1]
 =>  [1,1,2]

++   [0,1,1,1]
 (+) [1,1,2]
 =>  [1,2,3]
 -- prepend [1]
 =>  [1,1,2,3]

++   [0,1,1,1]
 (+) [1,1,2,3]
 =>  [1,2,3,4]
 -- prepend [1]
 =>  [1,1,2,3,4]

Это 1 способ сделать 0, 1 способ сделать 1, 2 способа сделать 2, 3 способа сделать 3,и 4 способа сделать 4.

0 голосов
/ 13 мая 2018

Я думаю, что это лучше всего решить с помощью явного 2D-массива.По сути, мы даем результат каждого вызова функции в этом массиве.Это позволяет нам оценивать функцию не более одного раза.Нам нужно добавить еще несколько шаблонов, потому что нам нужно проверить, будем ли мы индексировать вне массива 

makeChange :: Int -> [Int] -> Int
makeChange n ys = arr ! (n,1)
    where 
      len = length xs
      xs = sort ys
      arr = array ((1,1),(n,len)) [((i,j), go i j x)| i <- [1..n], (j,x) <- zip [1..] xs]
      go n ix x | x == n = 1
                | x > n = 0
                | otherwise = (if ix + 1 <= len then (arr ! (n, ix+1)) else 0) + 
                              (if (n-x) > 0 then (arr ! ((n-x), ix)) else 0)
...