真面目なブログはこっち 👉 blog.s64.jp

蟻本第2版34ページの問題をHaskellで書く

蟻本第2版23ページの問題 (POJ 1852) をHaskellで書く - 🍥shuma_yoshiokaに引き続き、プログラミング学び直し日記。「プログラミングコンテストチャレンジブック 第2版」の34ページより、「部分和問題」。類似問題はこちら。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

f0 :: [Int] -> Int -> Bool
f0 (a:as) k = a == k || f0 as k || f1 a as k
f0 [] _ = False

f1 :: Int -> [Int] -> Int -> Bool
f1 x (y:ys) k = x + y == k || f1 (x+y) ys k
f1 _ [] _ = False

main :: IO ()
main = do
    _ <- readLn :: IO Int -- n
    as <- (map read . words) <$> getLine :: IO [Int]
    k <- readLn :: IO Int

    putStrLn $ if (f0 as k) then "Yes" else "No"

コレで合ってるか大変不安である。しかし参考ナシで例を一発正当できたので嬉しい。