43 抛砖引玉一下 刚刚闲来没事想说用暴力法画出 N = 2~5 的 state diagram 在列出来之前要先说明一个大前提 就是说要得到全部0的A目标是以最少次数达到目标 阻止A的B自然也不会无缘无故帮助A更快达到目标 因为画出完整的 state diagram 有些麻烦 所以我用下面的数列呈现 N = 2 00110 N = 3 0001110100 N = 4 0000111101100101000 N = 5 000001111101110011010110001010010000 ------------------------------------------------- 下面解释数列怎样形成的 以 N = 3 为例 有 000, 001, 010, 011, 100, 101, 110, 111 8种可能 000 (end) | 000 001 > 000 (> 100 不合前提) | 001 010 | 010 < 101 (< 001 不合前提) 011 > 001 (> 101 不合前提) | 011 100 | 100 101 | 101 110 | 110 < 111 (< 011 不合前提) 111 > 011 (> 111 不合前提) | 111 化简後 100 010 < 101 110 < 111 > 011 > 001 > 000 显然 101 > 110 (> 010 loop 不合前提) 所以 010 < 101 > 110 < 111 > 011 > 001 > 000 最後 100 < 010 (< 110 不合前提) 结果便产生一个数列 100, 010, 101, 110, 111, 011, 001, 000 整理後 100 010 101 110 111 011 001 000 ---------- 0001110100 就是前面 N = 3 的数列 换句话说 N = 4 的数列 0000111101100101000 用另一种呈现方式就是 1000, 0100, 1010, 0101, 0010, 1001, 1100, 0110, 1011, 1101, 1110, 1111, 0111, 0011, 0001, 0000 ------------------------------------------------- 从 N = 2 ~ 5 可以看到几点有趣的现象: 1) 在大前提成立下 看不出有什麽可以阻止A胜出的方法 2) 第一项永远都是 1000.....000 这大概就是让A步数最多的解吧 3) 个人比较喜欢下面的呈现方式 虽然说还看不出有什麽规则就是... 1000 1100 1110 1111 0100 0110 0111 1010 1011 0011 0101 1101 0001 0010 0000 1001 附上 N = 5 的情形 10000 11000 11100 11110 11111 01000 01100 01110 01111 00100 10110 10111 00111 10010 01011 11011 00011 01001 10101 11101 00001 10100 11010 00000 01010 01101 00101 00110 00010 10011 10001 11001 4) 每组数字 0000 ~ 1111 都有出现在数列里 总觉得这种数列应该很有名才对吧 但怎麽查都查不到 以上 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.109.135.110