3

私の友人が、彼が参加している C++ コースで自宅でのエクササイズを教えてくれました。私はすでにC++を知っていますが、Haskellを学び始めたばかりなので、「Haskell流」で演習を解こうとしました。

これらは運動の指示です（母国語から翻訳したので、指示が明確でない場合はコメントしてください）：

ユーザーからゼロ以外の係数 (A、B、C、D) を読み取り、それらを次の式に配置するプログラムを作成します。 A*x + B*y + C*z = D プログラムは、ユーザーからも読み取る必要があります。範囲を表す N。プログラムは、-N/2 から N/2 の範囲で方程式のすべての可能な積分解を見つける必要があります。

例えば：

Input: A = 2,B = -3,C = -1, D = 5, N = 4
Output: (-1,-2,-1), (0,-2, 1), (0,-1,-2), (1,-1, 0), (2,-1,2), (2,0, -1)

最も単純なアルゴリズムは、力ずくですべての可能性を試すことです。次の方法で Haskell に実装しました。

triSolve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve a b c d n =
  let equation x y z = (a * x + b * y + c * z) == d
      minN = div (-n) 2
      maxN = div n 2
  in [(x,y,z) | x <- [minN..maxN], y <- [minN..maxN], z <- [minN..maxN], equation x y z]

ここまでは順調ですが、演習の指示では、より効率的なアルゴリズムを実装できると書かれているので、どうすれば改善できるかを考えました。方程式は線形であるため、Z が常に最初にインクリメントされるという仮定に基づいているため、解が見つかったら、Z をインクリメントする意味はありません。代わりに、Y をインクリメントし、Z を範囲の最小値に設定し、立ち止まるな。このようにして、冗長な実行を保存できます。Haskell にはループがないので (少なくとも私の理解では)、そのようなアルゴリズムは再帰を使用して実装する必要があることに気付きました。次の方法でアルゴリズムを実装しました。

solutions :: (Integer -> Integer -> Integer -> Bool) -> Integer -> Integer -> Integer -> Integer -> Integer ->     [(Integer,Integer,Integer)]
solutions f maxN minN x y z
  | solved = (x,y,z):nextCall x (y + 1) minN
  | x >= maxN && y >= maxN && z >= maxN = []
  | z >= maxN && y >= maxN = nextCall (x + 1) minN minN
  | z >= maxN = nextCall x (y + 1) minN
  | otherwise = nextCall x y (z + 1)
  where solved = f x y z
        nextCall = solutions f maxN minN

triSolve' :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve' a b c d n =
  let equation x y z = (a * x + b * y + c * z) == d
      minN = div (-n) 2
      maxN = div n 2
  in solutions equation maxN minN minN minN minN

どちらも同じ結果になります。ただし、実行時間を測定しようとすると、次の結果が得られました。

*Main> length $ triSolve' 2 (-3) (-1) 5 100
3398
(2.81 secs, 971648320 bytes)
*Main> length $ triSolve 2 (-3) (-1) 5 100
3398
(1.73 secs, 621862528 bytes)

つまり、愚かなアルゴリズムは実際には、より洗練されたアルゴリズムよりも優れたパフォーマンスを発揮します。私のアルゴリズムが正しかったという仮定に基づいて (これが間違っているとは思いません :))、2 番目のアルゴリズムは再帰によって作成されたオーバーヘッドに苦しんでいると仮定します。リストの理解。Haskell でダムアルゴリズムよりも優れたアルゴリズムを実装する方法はありますか? (また、私のコーディング スタイルに関する一般的なフィードバックをいただければ幸いです)

4

2 に答える 2

3

もちろんあります。我々は持っています：

a*x + b*y + c*z = d

x と y の値を仮定するとすぐに、次のようになります。

a*x + b*y = n

ここで、n は既知の数値です。したがって

c*z = d - n
z = (d - n) / c

そして、整数の z のみを保持します。

于 2013-06-26T20:33:43.687 に答える