Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: [合集]遍历所有指示灯的亮灭组合
发信站: 哈工大紫丁香 (2002年08月28日17:27:11 星期三), 站内信件


────────────────────────────────────────
 SoonFaye (宠辱偕忘)                  于 2002年08月26日08:58:58 星期一 说道:

10个开关分别控制10个指示灯，开始全是亮的。
问：最少要扳动多少次开关遍历所有指示灯的亮灭组合？
    ~~~~

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日09:38:22 星期一 说道:

2^10-1
而且这个结论可以推广

────────────────────────────────────────
 SoonFaye (宠辱偕忘)                  于 2002年08月26日09:39:55 星期一 说道:

可不是累加器，呵呵。
怎么证明的？

────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月26日09:47:52 星期一 说道:

n位的Gray码和这个是一个道理吧

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日09:51:07 星期一 说道:

一位的时候就是 0 1
n位的时候设为 0..0(n个0), X , ... , Y ，相邻状态之间只改变一位
n+1位可以这样构造：
00..0 （一共n+1个）,
改变第一位：
10..0
然后保持第一个1不变，按n位的情况把后面变一圈，直到
1Y ,
随后变为
0Y
再保持第一个0不变，倒着变一圈回去到
0X
这样，每次状态改变只需要搬动一个开关， 所以 ： 2 ^ n - 1

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日09:53:34 星期一 说道:

=.=b 不了解Gray码的说...

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日09:58:12 星期一 说道:

这样做的话，从0..0可以一直变化一圈回到0..0,每次一个开关

────────────────────────────────────────
 SoonFaye (宠辱偕忘)                  于 2002年08月26日10:26:06 星期一 说道:

弓虽！

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日10:33:20 星期一 说道:

//blush

────────────────────────────────────────
 Lucubrator (彻夜孤灯)                于 2002年08月26日15:38:29 星期一 说道:

Gray码就是2^n个n位二进制数相邻两之间只有一位不同
和这题一个道理

────────────────────────────────────────
 sino (茶水)                          于 2002年08月26日17:36:38 星期一 说道:

原来如此，那就是一样了

────────────────────────────────────────
--
※ 修改:·Lerry 於 08月28日17:32:17 修改本文·[FROM: 218.7.33.123]