haskell-jp / mokumoku-online #55

b

1) の3種類のコインを使った最小枚数での払い方。計算量 O(log(b))。

import Data.List (unfoldr)

-- a/b の連分数展開と近似分数
cf a b = unfoldr f (a,b,0,1,1,0) where
  f (_,0,_,_,_,_) = Nothing
  f (a,b,p1,q1,p2,q2) = Just((b,c,p2,q2), (b,a',p2,q2,p,q)) where
    (c, a') = a `divMod` b
    (p, q) = (p1 + c * p2, q1 + c * q2)

chunk [] = []
chunk [(r1,_,p1,q1)] = [(r1,p1,q1, 0,undefined,undefined, undefined)]
chunk ((r1,_,p1,q1):(r2,c2,p2,q2):ds)
  | c' < c2 = [pair]
  | otherwise = pair: chunk ds
  where
    (c, l) = (r1 - p1 + q1) `divMod` (r2 + p2 - q2)
    c' = if c == c2 && l == 0 then c-1 else c
    pair = (r1,p1,q1, r2,p2,q2, c')

-- n円を a円 b円 1円 (a > b > 1) の3種類のコインで払う。計算量 O(log(b))
cmp a b n = (y'+x'+z',(y',x',z')) where
  (y, x) = n `divMod` a
  (y',x',z') = cmp' (chunk $ cf a b) (y,x,0)
  cmp' [] yxz = yxz
  cmp' ((r1,p1,q1, r2,p2,q2, c): ds) (y,x,z)
    | i1 < i = yxz1
    | r2 == 0 = yxz1
    | x1 < r2 = cmp' ds yxz1
    | j2 <= c && y2 >= 0 = cmp' ds yxz2 
    | otherwise = yxz1
    where
      i = x `div` r1
      i1 = if y < i * q1 then y `div` q1 else i
      yxz1@(y1,x1,z1) = (y - i1 * q1, x - i1 * r1, z + i1 * p1)
      (j,x2) = (x1 - r1) `divMod` r2
      j2 = -j
      yxz2@(y2,_,_) = (y1 - j2 * q2 - q1, x2, z1 + j2 * p2 + p1)

import Test.QuickCheck

-- 計算量 O(log(u2)) の実装（ただし未証明）
cmp u1 u2 n = 前回書いたコード

-- ナイーブな実装
cmp_naive u1 u2 n = let (y, x) = n `divMod` u1
  in minimum $ [(i+j+k, (i,k,j)) | i <- [(max 0 (y-u2))..y], let (j,k) = (n - i*u1) `divMod` u2]

abn :: Gen (Int,Int,Int)
abn = do
  d1 <- chooseInt (1, 10000)
  d2 <- chooseInt (1, 100000)
  n <- chooseInt (0, 1000000)
  let (u1, u2) = (u2 + d2, 1 + d1)
  return (u1, u2, n)

-- 1000万回テスト
main = do
  quickCheckWith stdArgs { maxSuccess = 10000000 } $ forAll abn $ \(u1,u2,n) -> fst (cmp u1 u2 n) == fst (cmp_naive u1 u2 n)