Help us understand the problem. What is going on with this article?

単価が異なるお菓子をどういう組み合わせで買えば目標の合計値になるか問題

先日、息子がとある算数の問題に挫折しているので覗いてみたら、確かにちょっと難しそうだった。「4種類の価格がまちまちのお菓子を任意個ずつ買ってキリがよい合計にする」という問題なんだけど、お菓子の単価と目標の合計値のみしか提示されていない 1 。当然、まるっきり当てずっぽうで正解が得られる感じではない。たぶん、答えが当ってるかどうかより、どういうアプローチで回答しようとしたかを見ることが問題の主旨であるような気がする。

で、これはまあ一種の切符問題なので、父さんならHaskellで解くなと思うだけ思ってそれきり忘れてたんですが、新千歳空港でお土産を買ってるときに思い出したので、成田までの機内で書きなぐってみました。抽象度が低くて残念な感じですが、当機はすでに着陸体制に入っています。(と思ったら成田が混雑してるので旋回しはじめた)

module Main where

import System.Environment

main :: IO ()
main = do
  -- 第一引数:目標の合計金額
  -- 残り:お菓子たちの単価
  x:xs <- fmap (map $ read) getArgs
  putStrLn $ show $ seek x (length xs) $ comb $ matrix xs

matrix :: [Int] -> [[(Int,Int)]]
matrix xs = map (\i -> map (\j -> (j,i)) [1..10]) xs

comb :: [[(Int, Int)]] -> [[(Int, Int)]]
comb [] = []
comb ([]:rest) = comb rest
comb ((x:xs):[]) = [[x]] ++ comb [xs]
comb ((x:xs):rest) = [(x:ys) | ys <- comb rest] ++ comb (xs:rest)

seek :: Int -> Int -> [[(Int, Int)]] -> [[(Int, Int)]]
seek target n = filter (totalIs target)
  where d (i,j) = i*j
        totalIs t xs = length xs == n && t == (sum $ map d xs)

問題の数字は覚えてないので、適当な合計金額と単価で実行例。

λ> :main "3000" "146" "172" "400" "500"
[[(4,146),(3,172),(1,400),(3,500)]]
λ> 

146円のお菓子が4個、172円のが3個、400円のが1個、500円のが3個で3000円になるらしいです。


  1. 厳密には、それぞれの上限を10個とするとか、お菓子はなるべく高いものを多く買うとか、もうちょっと制限があった。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした