验证“病了总会好起来的”

aimisiyou

有一条虫子，它的整个身体由 n 节构成，每一节要么是有瑕疵的 1 ，要么是没有瑕疵的 0 ，因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次，你可以砍掉虫子最右侧的一节，同时虫子会在最左侧长出新的一节，以保持虫子的总长度不变。如果你砍掉的是一个 1 ，那么你可以指定虫子在最左侧长出的是 1 还是 0 ；但如果你砍掉的是一个 0 ，那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ，也可能会长出 1 ，因而你不得不假定，概率总是会和你做对，上天会竭尽全力地阻挠你。我们的问题是：不管虫子的初始状态是什么，你总能保证在有限步之内让虫子变成 000...00 吗？

aimisiyou

(defun f (n)
  (defun ff (j)
    (setq lst '((0 5 1)(5 10 0)) vlst nil)
    (repeat n
        (setq num (fix (rem (getvar "CPUTICKS") 11)))
        (setq vlst (cons (car (vl-remove nil (mapcar '(lambda (x) (if (<= (car x) num (cadr x)) (last x) nil)) lst))) vlst))
    )
   )
   (princ (ff n))
   (while (/= 1 (apply '* vlst))
          (if (= (last vlst) 0)
               (progn
                  (setq vlst (cons 1  (reverse (cdr (reverse vlst)))))
                  (princ vlst)
               )
              (progn
                  (setq vlst (cons (car (ff 1)) (reverse (cdr (reverse vlst)))))
                  (princ vlst)
               )
           )
  )
  (princ vlst)
)

liunian0524

原谅我没看懂

yangjian001

证明：经过有限次切除手术，虫子每节都会变成正常。

aimisiyou

liunian0524 发表于 2017-8-4 08:03

就是验证下会不会死循环。

Lisphk

楼主，这个有数学的证明吗？ 我怎么感觉最坏的情况下，病好不了呢。