C++-开关控制电灯

C++-开关控制电灯

想挽留 发布于 2017-09-21 字数 547 浏览 1201 回复 1

有n个灯L 和 n个开关 S
每个开关控制一盏灯(即开关和灯有一一对应关系)
现在问:至少知道多少个条件,可以求出这些对应关系?

比如 有 灯 L1,L2 开关S1、S2
如果知道 S1控制L1,就可以知道S2控制L2,因此需要一个条件即可

比如有灯 L1、L2、L3 开关S1、S2、S3
如果知道S1控制L1、S2控制L2 就可以求出一一对应关系,因此需要2个条件

比如 L1、L2、L3、L4 S1、S2、S3、S4
如果知道S1、S2 控制 L1、L2
S1、S3控制L1、L3
就可以求出 一一对应关系 因此需要2个条件

现在 求n个灯和n个开关 需要知道的条件个数

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

夜无邪 2017-09-26 1 楼

用分治法,把n个问题转换为两个n/2的问题,依次下去,最终答案应该是 logN。