硬币移除问题的算法

问题：硬币移除问题的算法
描述:

问题： 现有n个硬币排成一排。只允许对硬币进行以下操作：

移除一个正面向上的硬币，同时翻转与其相邻的硬币。

问有哪些排列是可以达到移除所有的硬币的。

---

例如，反正正正反 是可以移除的（正空反正反，空空反正反，空空正空正，空空空空正）。但是像 反正反正反 是没法移除的。

我尝试编程解决这个问题，但是感觉有点吃力。似乎还和移除的顺序有关。例如上面的 反正正正反 如果先移除当中的一个硬币，就变成 反反空反反 了，然后就无法移除了。这样枚举的时候就不能随意移除一枚正面硬币了……

求指教。任意语言、伪代码都行。（不知道这个问题在数学上有没有什么特殊的方法求解？

---

解决方案1:

明显是数学问题，稍微推倒一下可以发现：
f(n) = f(n - 1) + 2(n - 2) + 1
=>
f(2n) = 2f(2n - 1)
f(2n + 1) = 2f(2n) + 1
或者简单地说
f(n) = 2f(n - 1) + n%2
f(n)是答案。

突然发现太严格的证明我也写不出来，简单说下思路吧。
这个递归大部分都非常的显然。
定义f(n)为答案，考虑，令集合S(n)为长度为n的答案集合，显然f(n) = Card(S(n))
那么对于长度为n - 1的S(n - 1)，把1放到S(n - 1)中的每个序列后面，同时反转1前面的东西，这显然是一个方案。

然后……考虑在S(n - 2)的尾巴放两个0和10……以及一个很特殊的情况就是00000...11
得到递归式子S(n) = S(n - 2) + 00 | S(n - 2) +10 | S(n - 1) + 1 | 000...11
于是f(n) = f(n - 1) + 2f(n - 2) + 1注意n > 2各种乱搞之后得到前面的式子。。

实际上f(n)的二进制形式就是101010101...010当n为偶数，1010101010...101当n为奇数。
最后就得到f(n) = 2f(n - 1) + n % 2. 差不多是这样的，中间有一些什么不重复之类的就没有严格证明了……如果有兴趣的话随便玩玩吧。

解决方案2:

个人觉得不会留空，如果是竖向堆叠的话，会在重力的作用下掉下去……

如果有留空，则会出现第三种状态，所以先按2种状态来做吧。

1

思路首先最简单的，罗列从{}到{1,1,1,1,1}的所有可能性。然后根据f(A)=B的关系将它们连线。大概会组成一个这样的关系：

这样问题就变成了遍历一棵树了。然后时间复杂度和空间复杂度都是O(n²)

语言是JavaScript。为了最快实现用了递归=w=所以时间复杂度和空间复杂度俺都不知道……

var NUM_OF_COINS = 5,
    data = [""],
    dir_con = {} ,
    possibles = {} ;

function reverse(str) {
    if ( typeof str !== "undefined" ) {
        return Number(str) ? "0" : "1" ;
    }
    return undefined;
}

function fn( str, at ){
    var tmp ;
    if( str.charAt(at) == "1" ) {
        tmp = str.split("");
        tmp[at+1] = reverse(tmp[at+1]) ;
        tmp[at-1] = reverse(tmp[at-1]) ;
        tmp.splice(at,1);
        tmp = tmp.join("") ;
    }
    return tmp;
}

// 循环生成所有状态
// 从""到"11111"
for( var j = 0 ; j <= NUM_OF_COINS ; j++ ) {
    for( var i = 0 ; i < ( 2<<j - 1 ) ; i ++ ) {
        var a = i.toString(2) ;
        a = (a / Math.pow(10, j)).toFixed(j).substr(2);// 在前方补充0
        data.push( a ) ;
    }
}

// 循环每一步的可能性，链接相应状态
for( var i = data.length - 1 ; i >= 0 ; i -- ) {
    var cur = data[i] ;
    for( var j = 0 ; j < cur.length ; j ++ ) {
        var result = fn(cur,j) ;
        if( typeof result !== "undefined" ) {
            if ( typeof dir_con[result] !== "object" ) {
                dir_con[result] = [] ;
            }
            dir_con[result].push(cur) ;
        }
    }
}

// 目标状态""，递归查找
// 其实在dir_con里已经表示了一个树
function getOriginState( str ){
    var arr = dir_con[str] ;
    for(var i = 0 , next = arr[i] ; i < arr.length; i++ , next = arr[i] ) {
        if ( next.length < NUM_OF_COINS ) {
            getOriginState(next) ;
        } else if ( next.length == NUM_OF_COINS ) {
            possibles[next] = true ;
        }
    }
}

getOriginState("") ;
var resultarr = [] ;
for (var i in possibles ) {
    resultarr.push(i) ;
}

resultarr
-> ["10000", "10010", "10011", "10101", "10111", "11000", "11001", "11010", "11100", "11101", "11110", "01001", "01111", "01110", "00111", "01011", "01100", "00100", "00011", "00110", "00001"]

解决方案3:

我来练习下 Scheme :-)

编译与运行：

$ csc -O2 turn-coins.scm
$ ./turn-coins 0 1 1 1 0

0 表示反面，1 表示正面，2 表示空位。

(require-extension amb)
(require-extension vector-lib)

(define (turned x)
  (case x
    ((1) 0)
    ((0) 1)
    ((2) 2)))

(define (list-and args)
  (if (null? args)
    #t
    (and (car args) (list-and (cdr args)))))

(define (remove-coin coins index)
  (printf "Coins: ~a, index: ~a.\n" coins index)
  (if (finished coins)
    #t
    (let ((coins (vector-copy coins)))
      (if (>= index (vector-length coins))
        (amb))
      (if (= 1 (vector-ref coins index))
        (amb (begin
              (if (not (= index 0))
                (let ((pos (- index 1)))
                  (vector-set! coins pos (turned (vector-ref coins pos)))))
              (let ((pos (+ index 1)))
                (if (not (>= pos (vector-length coins)))
                  (vector-set! coins pos (turned (vector-ref coins pos)))))
              (vector-set! coins index 2)
              (remove-coin coins 0))
            (remove-coin coins (+ index 1)))
        (remove-coin coins (+ index 1))))))

(define (finished coins)
  (list-and (map (lambda (x) (= x 2)) (vector->list coins))))

(define (main args)
  (if (amb-find (remove-coin (list->vector (map string->number args)) 0)
                #f)
    (printf "Mission Complete!\n")
    (printf "Mission Failed!\n")))

(main (command-line-arguments))

---

再补充一个 Haskell 版的：

import System.Environment (getArgs)

data CoinState = Front | Back | Empty deriving (Show, Eq)

instance Read CoinState where
  readsPrec a (x:rest) = case x of
    '0' -> [(Back, rest)]
    '1' -> [(Front, rest)]
    '2' -> [(Empty, rest)]

flipOne Front = Back
flipOne Back = Front
flipOne Empty = Empty

flipMiddle coins i =
  take (i-1) coins ++
  [flipOne (coins !! (i-1)), Empty, flipOne (coins !! (i+1))]
  ++ drop (i+2) coins

doIt :: [CoinState] -> Int -> [[CoinState]]
doIt coins i = 
  if i + 1 < length coins
     then case coins !! i of
       Front -> let new = flipMiddle coins i
                in new : doIt coins (i+1) ++ doIt new 1
       _ -> doIt coins (i+1)
     else [coins]

main = do
  args <- getArgs
  let cases = flip doIt 1 $ Empty : map read args ++ [Empty]
  let solution = filter (all (== Empty)) cases
  if null solution
     then putStrLn "No luck."
     else putStrLn "There is a way!"