2

まあ、私は Haskell の要点 (ほとんど) が、単純な関数からより複雑な関数を構築するために再帰性を使用する利点であることを理解しています。次に、特定のタプルを使用して、2 つの数値が実行できるすべての可能な操作 (*、+、-、/) を出力する operations という別の関数を用意します。

-- Find all possible 2-combinations of the elements of xs.
pairs :: [Int] -> [(Int, Int)]
pairs xs = [(x, y) | (x:ys) <- tails xs, y <- ys]

operations :: (Int, Int) -> [(Int, Int, Char, Int)]
operations (x, y) =
    [ (x, y, '+', x + y) ] ++
    [ (x, y, '*', x * y) ] ++
    [ (x, y, '-', x - y) | x > y, (x/=4 && y/=2) ] ++
    [ (x, y, '/', x `div` y) | x >= y, x `mod` y == 0]

int の文字列と目的の数値を指定する関数を実装しようとしています (最終的な目的は、int の文字列でその数値を取得することです)。タプルとその結果の可能なすべての組み合わせを出力します。

solve ( 100 , [1,4,5] , [] )

[ ( 100 , [5,5] , [(1,4,'+',5)] ),take first tuple 1,4 add and subs into "new tuple"5,5
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),
( 100 , [4,4] , [(5,1,'-',4)] ),
( 100 , [9,1] , [(4,5,'+',9)] ),
( 100 , [1,1] , [(5,4,'-',1)] ),
( 100 , [20,1] , [(4,5,'*',20)] ) ]

これにアプローチする方法について混乱しています。タプルで可能なすべての操作を出力する関数と、すべてのタプルを生成する関数が既にあることを知っているので、それらを組み合わせる方法がわかりません。助けていただければ幸いです、ありがとう.

私はあなたの解決策を見て理にかなっていますが、ゼロから始めるには遅すぎます。

私はこれをしました：

solve(n,ns) = [ e | ns' <- pairs ns
                      , e   <- operations ns']

( 100 , [3,5] , [(4,1,'-',3)] )、私が欲しいものです

なるほど、少し違うように見えるので、自分のやり方を試してみたいと思います.2回目以降は混乱します.Haskellはまだ少しひどいです. だから、これは私の関数が行うことです： etc] operations はタプルを取り、そのタプルで可能なすべての操作を返します (正の整数の結果でなければなりません)。

solve(n,ns) = [ e | ns' <- pairs ns
                      , e   <- operations ns']

n は目的の数値、ns は 6 +int の文字列であり、これまでのところ、[(3,'+',4,7),(3,´*´,4 などのタプルのすべての組み合わせが出力された文字列を返します。 、12)...など] ただし、各段階で印刷したい:

[n,(result of tuple operation,string number)(tuple operation)]
eg ( 100 , [5,5] , [(1,4,'+',5)] ),take first tuple 1,4 add and subs into "new tuple"5,5
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),
4

2 に答える 2

2

この問題を解決する方法はたくさんあります。以下は、比較的単純な Haskell 風のソリューションの概要です。は代数データ型を使用することに注意してください。

注: これはやや複雑な問題です。私のソリューション (比較的クリーン) は 55 行です。

最初のステップは、問題に適したデータ型を定義することです。以下を選択します。

data Expr = Lit Int
   | Plus Expr Expr
   | Times Expr Expr
   | Minus Expr Expr
   | Divide Expr Expr
  deriving Show

型の値はExpr、4 つの二項演算で構成され、葉に整数を持つ式ツリーです。この定義を使用して、次の関数を定義する必要があります。

eval :: Expr -> Int       -- "evaluate" a expression

exprs :: [Int] -> [Expr]  -- derive all expression trees whose literals come from
                          -- a list of integers

次に、特定の数値に評価される式を見つけることは次のとおりです。

findexprs :: [Int] -> Int -> [Expr]
findexprs xs y = filter (\e -> eval e == y) $ exprs xs

書き込みeval

eval関数は単純なケース分析になります。

eval (Lit x) = x
eval (Plus a b) = (eval a) + (eval b)
eval (Minus a b) = (eval a) - (eval b)
...

ヒント: 割り算については、quot関数を調べてください。

書き込みexprs

の最初の 2 つのケースexprsは非常に簡単です。

exprs :: [Int] -> [Expr]
exprs []  = []
exprs [x] = [ Lit x ]
exprs xs  = ...

リストに数字が 1 つしかない場合、作成できる唯一の式は withLitです。

の最後のケースは次のexprsようになります。

  1. xs2 つのサブリストに分割:leftおよびright
  2. リストを使用して式ツリーを定式化するleft
  3. リストを使用して式ツリーを定式化するright
  4. 2 つの式ツリーを二項演算子で結合する

ステップ 2 と 3 はexprs関数の再帰呼び出しです。ステップ 4 は、考えられるすべての二項演算子を繰り返すだけです。これにはリスト内包表記を使用できます。

ステップ 1 では、リストを 2 つのサブリストに分割するすべての方法を見つける必要があります。つまり、関数を定義する必要があります。

parts :: [Int] -> [ ([Int], [Int]) ]

たとえば、parts [1,2] = [ ([1,2],[]), ([1],[2]), ([2],[1]), ([], [1,2]) ].

もちろん、parts再帰的に定義することができ、トリックはパターンを見つけることです:

parts [] = [ ([],[]) ]
parts (x:xs) = ...???...

parts (x:xs)ここでのヒントは、からどのように形成するかを自問することですparts xs。

注意事項

いくつかの実装の詳細を省略しました。まず第一に、除算を本当に正しく実装したい場合は、おそらく次の型シグネチャを再検討する必要がありますeval。

eval :: Expr -> Int

最初に物事を機能させるために、除算演算子を省略したい場合があります。Maybe次に、データ型について読みたいと思うかもしれません。

の定義の詳細も省略しましたexprs。私が概説した手順には、無限ループの落とし穴 (簡単に回避できます) が潜んでいます。

幸運を！

コメント

(SO はコメント内の実行時間の長いスレッドを好まないため、ここで OP の質問に対処します。)

前に述べたように、この問題を解決するには多くの方法があります。たとえば 、演算子とオペランドの順列のアルゴリズムを参照してください。

このアプローチはより複雑ですが、Haskell で広く使用されている便利な分解パターンです。また、次の懸念事項を分離するように注意します。

  1. 可能性のあるツリーを生成する (exprs関数)
  2. 式ツリーの評価 (eval関数)
  3. 興味のある木を見つける ( filter ...)

あなたのアプローチは、最初の 2 つの懸念事項を組み合わせたものです。この問題を解決するだけなら問題ないかもしれませんが、法的な表現の基準を変更するとします。たとえば、リスト内の数字を複数回再利用できるとしたらどうしますか (現在、数字は 1 回しか使用できません)。または、すべての数字を使用する必要がない場合はどうしますか? これらのバリエーションは、exprs機能を変更するだけで済みます。

于 2013-05-06T07:23:35.897 に答える