0

Project Eulerの問題をやっていて、14日です。

IOArray既に計算した Collat​​z の長さを格納するミュータブルがあります。

import Data.Array.IO
import Control.Monad
import Data.Array

p14 :: IO [Int]
p14 = do
  array <- p14extra
  forM_ [1..1000000] $ \i -> do
    e <- readArray array i
    if e == 0
      then do
        let col  = collatz i
        forM_ col $ \(v,i) -> do
          writeArray array i v
      else return ()
  frozen <- freeze array
  return $ elems frozen

-- an `IOArray` from `1` to `1000000` full of `0`
p14extra :: IO (IOArray Int Int)
p14extra = newArray (1,1000000) 0

collatz :: Int -> [(Int, Int)]
collatz n
  | n == 1    = [(1,1)]
  | otherwise = (n, (snd $ head hack) + 1) : hack
  where
    hack = collatz $ if even n then (n `div` 2) else (3 * n + 1)

ここで、最初の要素は計算される数値で、2 番目の数値はコラッツ シーケンスの長さです。

問題は、p14私が行うことですwriteArray array i vが、常にゼロ (0) の配列が含まれています。何故ですか？

4

3 に答える 3

4

正確なコードを実行したところ、配列が変更されていることがわかりました。

末尾にはゼロがたくさんあるため、数字を見つけるには先頭までスクロールする必要があります。

実際に代入すると

  frozen <- freeze array
  return $ elems frozen

と

  sol <- getElems array
  return (length . takeWhile (/=0) $ sol)

正しい解である 525 が得られます...これについては最後に詳しく説明します。

ただし、いくつかの問題があります。

  1. 行forM_ col $ \(v,i) -> doでは、最初の値がインデックスであり、2 番目の値が値であることを理解していることから、collat​​z のように見える(v,i)はずです。(i,v)
  2. これを整理したので、 と を使用してコードを実行しようとするforM_ [1..10]とnewArray (1,10)、 が得られ*** Exception: Ix{Int}.index: Index (16) out of range ((1,10))ます。1000000これは、数値のコラッツを計算するために より大きい数値のコラッツを計算する必要がある場合があるため、値を再度 に設定すると発生します1000000。たとえば、collat​​z の計算には、わずか 4 ステップ837798の後の計算が含まれます。1885048そのインデックスに書き込もうとすると、問題が発生します。

2 番目のソリューションでは、次のことができます。

  • collat​​z シーケンスが境界を超えないことを期待して、絶対に巨大な可変配列を作成してみてください (お勧めしません)。
  • 事前に計算された値を利用しない単純なバージョンを作成してみてください (主にそれを機能させるために、そこから適切に最適化します)。
  • 各書き込みの前に、境界チェックが実行されるようにします
  • ...または、ゼロから再設計して、より洗練されたソリューションを思い付くことができるかどうかを確認してください ;)

動作する理由は、の代わりにlength . takeWhile (/=0) $ sol使用したため、 collat​​z シーケンスの長さ i を持つ最小の数値をインデックス iに書き込んでいたため、インデックス 525 で 837799 を取得し、それ以降はすべてゼロであったためです。 525 より大きい collat​​z シーケンス。(v,i)(i,v)

于 2013-11-04T08:56:31.990 に答える
1

これがあなたを混乱させるものである場合に備えて、ただの直感です。p14使用する配列を変更しますが、後でその配列は含まれp14extraません。これは、実行されるたびに常にゼロで埋められた新しい配列を作成する IO アクションです。

于 2013-11-05T02:32:32.613 に答える