着色N段

Question

問題：我有編號從1到N和M顏色也編號從1到M.
現在，有兩個數字U和V定義爲N個連續節段：

• U =顏色（ⅰ）+顏色（J）
• V =顏色（J）+顏色（K）
• U，V是互質。

其中1 < = I，J，K < = N和
J = + 1，K = J + 1個

問題是要找到的方式，所有的N個片段可以是數上色屬性適用於所有i，j，k。
是否有針對此問題的動態編程解決方案？它是什麼？

Answer 1

我有一個遞歸但非[動態編程]實現這一點，應該幫助你在正確的方向。它在Common Lisp中實現，因爲沒有指定語言。

的方式來擴展它是一個動態規劃的解決辦法是增加一個緩存。

count-all-coprime-triple-colorings構建在存儲器中的所有着色劑，然後檢查它們中的每用於滿足互質條件三倍。

count-all-coprime-triple-colorings-lazy試圖積極修剪色彩，我們甚至考慮排除帶有不滿足互質條件的前綴的色彩。

這種辦法可以通過注意只有前綴的最後兩個元素是有關提高，所以你可以用它來填充緩存。

(defun coprime-p (a b) 
    "check whether a and b are coprime" 
    (= (gcd a b) 1)) 

(defun coprime-triple-p (a b c) 
    "check whether (a+b) and (b+c) are coprime" 
    (coprime-p (+ a b) (+ b c))) 

(defun coprime-triple-sequence-p (seq) 
    "check whether seq is a sequence of corpime triples" 
    (cond 
    ;; if the length is less than 2 then 
    ;; every triple is trivially coprime 
    ((<= (length seq) 2) t) 
    (t (let 
     ((a (nth 0 seq)) 
      (b (nth 1 seq)) 
      (c (nth 2 seq)) 
      (tail (cdr seq))) 
     (if (coprime-triple-p a b c) 
      (coprime-triple-sequence-p tail) 
      nil))))) 

(defun curry-cons (x) 
    "curried cons operator" 
    (lambda (list) (cons x list))) 

(defun all-colorings (sections colors) 
    "generate all possible #colors-colorings of sections" 
    (assert (>= sections 0)) 
    (assert (>= colors 1)) 
    (cond 
    ;; if there are no sections 
    ;; then there are no colorings 
    ((= sections 0)()) 
    ;; when we have one section there is one coloring 
    ;; for each color 
    ((= sections 1) (loop for i from 1 upto colors collecting (list i))) 
    (t 
     ;; wildly inefficient 
     (loop for i from 1 upto colors appending 
      (mapcar (curry-cons i) (all-colorings (1- sections) colors)))))) 

(defun count-all-coprime-triple-colorings (sections colors) 
    "count all the colorings that have coprime triples" 
    (loop for i in (all-colorings sections colors) counting (coprime-triple-sequence-p i))) 

(defun coprime-triple-check-boundary (reversed-prefix suffix) 
    "prefix = [...a, b] ; suffix = [c,...] ; check 
    gcd(a+b, b+c) != 1" 
    ;; if there aren't enough elements in reversed-prefix and suffix 
    ;; then we admit the list 
    (if (and (nth 1 reversed-prefix) (nth 0 suffix)) 
    (let 
     ((b (nth 0 reversed-prefix)) (a (nth 1 reversed-prefix)) (c (nth 0 suffix))) 
     (coprime-triple-p a b c)) 
    t)) 

(defun count-all-coprime-triple-colorings-lazy (sections colors reversed-prefix) 
    "count the number of sequences with coprime triples with a particular number 
    of sections and colors with a particular reversed-prefix." 
    (let 
    ((sections-- (1- sections))) 
    (cond 
     ((= sections 0) 1) 
     (t (loop for i from 1 upto colors summing 
      (if (coprime-triple-check-boundary reversed-prefix (list i)) 
       (count-all-coprime-triple-colorings-lazy sections-- colors (cons i reversed-prefix)) 
       0)))))) 

(defun summarize-coloring (i j) 
    "summarize the given coloring number" 
    (print (list "triples" i "colors" j 
       (count-all-coprime-triple-colorings-lazy i j nil)))) 

(loop for i from 1 upto 9 doing 
     (loop for j from 1 upto 9 doing (summarize-coloring i j)))