有趣数学题(s)

Friday, April 23, 2021

谁是CEO?

现在有函数f(a,b)={true , false},a,b属于有限集合A,已知A集合里面有个元素CEO满足对于任意a属于A,f(CEO,a)=false, 但是f(a,X)=true,怎么调用最少次数的f求出来CEO是啥呢

正常版本: 某公司里面ceo谁也不认识,其他人都认识ceo;求ceo。

其他名字:社会名流

思路 CEO存在于所有人认识的人的交集

既然是交集,选一个人x来询问其他人x认不认得的话,可以得到x的朋友圈。此时ceo一定在x的朋友圈里面。 如果朋友圈里面有人有认识的人,那那个人一定不是ceo。

最坏情况是x的朋友圈是全公司的人,这意味着每次加人近朋友圈的时候应该尽可能保证加进来的人不认识其他人。

这个解法在稀疏图里面比较奏效,因为朋友圈比较小,可以快速锁定ceo。

  1. i = 1->n, if f(x,i)==1, x = i;
  2. check if x is CEO

TBC

数学

Hackpku2021

异性恋爱博士