7

“假设你想用一排 4×1 和 6×1 的乐高积木拼成一个实心面板。为了结构强度，积木之间的空间绝不能在相邻的行中排列。例如，所示的 18×3 面板下面是不可接受的，因为前两行块之间的空间对齐。

构建 10×1 面板有 2 种方式，构建 10×2 面板有 2 种方式，构建 18×3 面板有 8 种方式，构建 36×5 面板有 7958 种方式。

构建 64×10 面板有多少种不同的方法？答案将适合 64 位有符号整数。编写程序计算答案。你的程序应该运行得非常快——当然，它不应该超过一分钟，即使在旧机器上也是如此。让我们知道您的程序计算的值，您的程序计算该值所用的时间，以及您在哪种机器上运行它。包括程序的源代码作为附件。"

我最近收到了一个编程难题，并且一直在绞尽脑汁试图解决它。我使用 c++ 编写了一些代码，我知道这个数字很大......我的程序运行了几个小时，然后我决定停止它，因为即使在慢速计算机上也需要 1 分钟的运行时间。有没有人见过类似的谜题？已经有几个星期了，我不能再提交了，但这真的让我很烦恼，我无法正确解决它。关于使用算法的任何建议？或者也许可能的解决方法是“开箱即用”。我采用的是制作一个程序，该程序构建每个可能的 4x1 和 6x1 块“层”以制作 64x1 层。结果证明有大约 3300 个不同的层。然后我让我的程序运行并将它们堆叠到所有可能的 10 层高墙上，这些墙没有排列的裂缝……正如你所看到的，这个解决方案需要很长时间。所以很明显，蛮力似乎并不能在时间限制内有效地解决这个问题。任何建议/见解将不胜感激。

4

3 回答 3

5

主要见解是：在确定第 3 行中的内容时，您不关心第 1 行中的内容，而只关心第 2 行中的内容。

因此，让我们将如何构建 64x1 层称为“行场景”。您说大约有 3300 行场景。那还不错。

让我们计算一个函数：

f(s, r) = 将行场景编号“s”放入“r”行并合法填充“r”以上所有行的方式数。

（我数的是顶部的“1”行，底部的“10”行）

如果您想避免剧透，请立即停止阅读。

现在很清楚（将我们的行从 1 编号到 10）：

f(s, 1) = 1

对于“s”的所有值。

此外，这就是洞察力的来源，（使用Mathematica -ish 表示法）

f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]

其中“fits”是一个函数，它接受两个场景编号，如果您可以合法地将这两行堆叠在一起，则返回“1”，如果不能，则返回“0”。这使用了洞察力，因为放置场景的合法方式的数量仅取决于根据“适合”在其上方放置场景的方式的数量。

现在，可以预先计算拟合并将其存储在 3328 x 3328 字节数组中。这只是大约 10 兆的内存。（如果您喜欢并将其存储为位数组，则更少）

那么答案显然只是

Sum[ f(i, 10) , {i, 1, 3328} ]
于 2009-05-27T02:22:02.057 回答
4

这是我的答案。它是 Haskell，除其他外，您可以免费获得 bignums。

编辑：它现在实际上在合理的时间内解决了问题。

更多编辑：使用稀疏矩阵在我的计算机上需要半秒钟。

您计算平铺一行的每种可能方式。假设有 N 种方法来平铺一行。制作一个 NxN 矩阵。如果第 i 行可以出现在第 j 行旁边，则元素 i,j 为 1，否则为 0。从包含 N 个 1 的向量开始。将矩阵乘以向量的次数等于墙的高度减去 1，然后对结果向量求和。

module Main where
import Data.Array.Unboxed
import Data.List
import System.Environment
import Text.Printf
import qualified Data.Foldable as F
import Data.Word
import Data.Bits

-- This records the index of the holes in a bit field
type Row = Word64

-- This generates the possible rows for given block sizes and row length
genRows :: [Int] -> Int -> [Row]
genRows xs n = map (permToRow 0 1) $ concatMap comboPerms $ combos xs n
  where
    combos [] 0 = return []
    combos [] _ = [] -- failure
    combos (x:xs) n =
      do c <- [0..(n `div` x)]
         rest <- combos xs (n - x*c)
         return (if c > 0 then (x, c):rest else rest)
    comboPerms [] = return []
    comboPerms bs =
      do (b, brest) <- choose bs
         rest <- comboPerms brest
         return (b:rest)
    choose bs = map (\(x, _) -> (x, remove x bs)) bs
    remove x (bc@(y, c):bs) =
      if x == y
         then if c > 1
                 then (x, c - 1):bs
                 else bs
         else bc:(remove x bs)
    remove _ [] = error "no item to remove"
    permToRow a _ [] = a
    permToRow a _ [_] = a
    permToRow a n (c:cs) =
      permToRow (a .|. m) m cs where m = n `shiftL` c

-- Test if two rows of blocks are compatible
-- i.e. they do not have a hole in common
rowCompat :: Row -> Row -> Bool
rowCompat x y = x .&. y == 0

-- It's a sparse matrix with boolean entries
type Matrix = Array Int [Int]
type Vector = UArray Int Word64

-- Creates a matrix of row compatibilities
compatMatrix :: [Row] -> Matrix
compatMatrix rows = listArray (1, n) $ map elts [1..n] where
  elts :: Int -> [Int]
  elts i = [j | j <- [1..n], rowCompat (arows ! i) (arows ! j)]
  arows = listArray (1, n) rows :: UArray Int Row
  n = length rows

-- Multiply matrix by vector, O(N^2)
mulMatVec :: Matrix -> Vector -> Vector
mulMatVec m v = array (bounds v)
    [(i, sum [v ! j | j <- m ! i]) | i <- [1..n]]
  where n = snd $ bounds v

initVec :: Int -> Vector
initVec n = array (1, n) $ zip [1..n] (repeat 1)

main = do
  args <- getArgs
  if length args < 3
    then putStrLn "usage: blocks WIDTH HEIGHT [BLOCKSIZE...]"
    else do
      let (width:height:sizes) = map read args :: [Int]
      printf "Width: %i\nHeight %i\nBlock lengths: %s\n" width height
             $ intercalate ", " $ map show sizes
      let rows = genRows sizes width
      let rowc = length rows
      printf "Row tilings: %i\n" rowc
      if null rows
        then return ()
        else do
          let m = compatMatrix rows
          printf "Matrix density: %i/%i\n"
                 (sum (map length (elems m))) (rowc^2)
          printf "Wall tilings: %i\n" $ sum $ elems
                  $ iterate (mulMatVec m) (initVec (length rows))
                            !! (height - 1)

而结果...

$ time ./a.out 64 10 4 6
Width: 64
Height 10
Block lengths: 4, 6
Row tilings: 3329
Matrix density: 37120/11082241
Wall tilings: 806844323190414

real    0m0.451s
user    0m0.423s
sys     0m0.012s

好的，500 毫秒，我可以忍受。

于 2009-05-29T10:35:48.040 回答
1

我为编程竞赛解决了一个类似的问题，该竞赛用各种形状的瓷砖平铺了一条长长的走廊。我使用了动态编程：给定任何面板，有一种方法可以通过一次放置一行来构建它。每行的末端可以有有限多个形状。因此，对于每个行数，每个形状，我计算有多少种方法可以制作该行。（对于底行，每个形状只有一种方法。）然后每一行的形状决定了下一行可以采用的形状数量（即永远不要排列空格）。这个数字对于每一行都是有限的，事实上，因为你只有两种尺寸的砖，它会很小。因此，您最终会在每行花费固定的时间，并且程序会很快完成。

为了表示一个形状，我只需制作一个 4 和 6 的列表，然后使用这个列表作为表中的键来存储在第i行中为每个i制作该形状的方法的数量。

于 2009-05-27T02:58:51.750 回答