组合数学编程题: 放水三人组的数量_数学吧

数学吧关注：918,960贴子：8,844,901

有n人两两比赛，比赛结果只有胜负，没有平。
如果ABC三人出现A胜B,B胜C,C胜A的情况，认为这三人放水。
n人编号为1至n
输入一个n*n的矩阵M，Mij为1时指i胜j,Mij为-1时指i输j, 所有Mii为0
输出放水三人组的数量，要求算法复杂度为O(n^2)

送TA礼物

IP属地:安徽

1楼2020-02-22 15:06回复

如果找到所有三人组一一判断，复杂度是n^3，因为所有三人组数量是nC3=n*(n-1)*(n-2)/6

IP属地:安徽

3楼2020-02-22 15:12

收起回复

不感兴趣

开通SVIP免广告

答案是这样
最大可能组数为n*(n-1)*(n-2)/6
对每个人i, ta的获胜场数为Wi, 则从最大可能组数里减去Wi(Wi-1)/2
n*n的矩阵循环一遍，复杂度是O(n^2)
这里不清楚
对每个人i, ta的获胜场数为Wi, 则从最大可能组数里减去Wi(Wi-1)/2

IP属地:安徽

4楼2020-02-22 15:27

求解释

IP属地:安徽

5楼2020-02-22 15:28

有大佬给我解答了：三人组如果有人赢了两场，则没有放水
对每个人，选择ta获胜的两场比赛，对应一个不放水三人组
所以放水三人组=nC3-Σ(WiC2)

IP属地:安徽

6楼2020-02-22 16:36

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴