I*******g
发帖数: 7600 | 1 【 以下文字转载自 Military 讨论区 】
发信人: IFloating (Floating Freely), 信区: Military
标 题: 来， 做题了。
发信站: BBS 未名空间站 (Fri May 19 17:15:07 2017, 美东)
有一群好莱坞名人， 假设为100人。
你现在要做东邀请这帮人， 想想在宴会上不让客人们尴尬，或者都只是几个人互相聊
天， 其他人大眼瞪小眼。
你现在邀请的人符合以下条件：
所邀的人必须认识所邀总数中5个或者5个以上的其他客人。
假设你事先有一个list知道谁和谁是认识相好的。
你怎么从100人选出客人名单。
要求用JAVA（C++)写出时间空间都优化的程序。（45分钟内完成， 没有BUG). |
H********g
发帖数: 43926 | 2 输出实例：
This program first randomly generates a friend map of 15 people (with a
probability of 0.5), then selects those who know
s 5 people in the party.
Here is a 15 by 15 matrix showing who knows who:
[ 0] 0 1 0 0 1 0 0 1 1 1 1 1 1 0 0
[ 1] 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0
[ 2] 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0
[ 3] 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0
[ 4] 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0
[ 5] 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1
[ 6] 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0
[ 7] 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1
[ 8] 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1
[ 9] 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1
[ 10] 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0
[ 11] 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1
[ 12] 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0
[ 13] 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1
[ 14] 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0
Now select ones who knows 5 friends in party:
round 1
[ 0] (invite?:1) 0 1 0 0 1 0 - 1 1 1 1 1 1 0 0
[ 1] (invite?:1) 1 0 1 1 0 1 - 0 0 0 0 1 0 1 0
[ 2] (invite?:1) 0 1 0 1 1 0 + 1 1 0 1 0 1 1 0
[ 3] (invite?:1) 0 1 1 0 1 0 - 1 0 1 1 0 0 1 0
[ 4] (invite?:1) 1 0 1 1 0 0 - 0 0 1 0 1 0 1 0
[ 5] (invite?:1) 0 1 0 0 0 0 - 0 1 1 1 0 0 0 1
[ 6] (invite?:0) - - + - - - - + - + + - - - -
[ 7] (invite?:1) 1 0 1 1 0 0 + 0 0 0 0 1 0 1 1
[ 8] (invite?:1) 1 0 1 0 0 1 - 0 0 0 1 1 0 0 1
[ 9] (invite?:1) 1 0 0 1 1 1 + 0 0 0 0 0 1 1 1
[ 10] (invite?:1) 1 0 1 1 0 1 + 0 1 0 0 1 0 0 0
[ 11] (invite?:1) 1 1 0 0 1 0 - 1 1 0 1 0 1 0 1
[ 12] (invite?:1) 1 0 1 0 0 0 - 0 0 1 0 1 0 1 0
[ 13] (invite?:1) 0 1 1 1 1 0 - 1 0 1 0 0 1 0 1
[ 14] (invite?:1) 0 0 0 0 0 1 - 1 1 1 0 1 0 1 0
14 candidates left
round 2
[ 0] (invite?:1) 0 1 0 0 1 0 - 1 1 1 1 1 1 0 0
[ 1] (invite?:1) 1 0 1 1 0 1 - 0 0 0 0 1 0 1 0
[ 2] (invite?:1) 0 1 0 1 1 0 + 1 1 0 1 0 1 1 0
[ 3] (invite?:1) 0 1 1 0 1 0 - 1 0 1 1 0 0 1 0
[ 4] (invite?:1) 1 0 1 1 0 0 - 0 0 1 0 1 0 1 0
[ 5] (invite?:1) 0 1 0 0 0 0 - 0 1 1 1 0 0 0 1
[ 6] (invite?:0) - - + - - - - + - + + - - - -
[ 7] (invite?:1) 1 0 1 1 0 0 + 0 0 0 0 1 0 1 1
[ 8] (invite?:1) 1 0 1 0 0 1 - 0 0 0 1 1 0 0 1
[ 9] (invite?:1) 1 0 0 1 1 1 + 0 0 0 0 0 1 1 1
[ 10] (invite?:1) 1 0 1 1 0 1 + 0 1 0 0 1 0 0 0
[ 11] (invite?:1) 1 1 0 0 1 0 - 1 1 0 1 0 1 0 1
[ 12] (invite?:1) 1 0 1 0 0 0 - 0 0 1 0 1 0 1 0
[ 13] (invite?:1) 0 1 1 1 1 0 - 1 0 1 0 0 1 0 1
[ 14] (invite?:1) 0 0 0 0 0 1 - 1 1 1 0 1 0 1 0
14 candidates left
guests to invite:
[0]
[1]
[2]
[3]
[4]
[5]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14] |
H********g
发帖数: 43926 | 3 老邢的站根本贴不了程序
贴点说明：
先建立一个n x n 的朋友表
#defaults:10 ren, 5 friends, generate friend map with probablity of 0.5
#parameters can be changed, example:
# perl guest.pl 15 4 0.3
#means 15 ren, minimum 4 friends in party, generate map with probability of
0.3
#step 1 generates a friend map
#@a is the the friendship array.
#Perl only allows 1D array, so row i column j is $a[$i*$n+$j].
#n by n of zeros, then randomly fill it with 1s (ofc, symmetrically).
my @a=(0)x ($n * $n);
if($i!=$j and rand(1)<=$proba){
$a[$i*$n+$j]=1;
$a[$j*$n+$i]=1;
}
print "Here is a $n by $n matrix showing who knows who:\n";
然后一行行地数朋友，朋友少于5个的标记成踢出，他所在的列作废，不再参与计数。
重复数，直到剩下的人数不再变化。
#Step 2, count each persons friend left in party. If less than $f, reject
this person.
#Array @r is a register of candidates. 1 means still candidate
#Array @s stores friends count. This array is only for QC.
step 3 输出。 |
H********g
发帖数: 43926 | 4 最后还能有几个人参加是很随机的。跟一开始朋友分布非常相关。所以要多跑几次才有
人参加。而且一旦开始踢人，通常会造成雪崩效果，比如这次运行，第一轮筛出去5个
，导致第二轮筛出去9个，最后一轮当然1个人怎么也没法认识5个（所以循环终止条件
可以设成人数不再变化或者人数小于5）。
This program first randomly generates a friend map of 15 people (with a
probability of 0.5), then selects those who kno
s 5 people in the party.
Here is a 15 by 15 matrix showing who knows who:
[ 0] 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0
[ 1] 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0
[ 2] 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0
[ 3] 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1
[ 4] 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1
[ 5] 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1
[ 6] 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0
[ 7] 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0
[ 8] 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0
[ 9] 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1
[ 10] 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1
[ 11] 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0
[ 12] 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0
[ 13] 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0
[ 14] 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0
Now select ones who knows 5 friends in party:
round 1
[ 0] (invite?:1) 0 0 - 0 0 1 + 1 - 1 0 - 0 + 0
[ 1] (invite?:1) 0 0 - 1 1 0 + 0 - 0 1 - 1 - 0
[ 2] (invite?:0) - - - + - + - + + - - - - - -
[ 3] (invite?:1) 0 1 + 0 0 0 - 1 + 1 0 - 1 - 1
[ 4] (invite?:1) 0 1 - 0 0 1 - 1 - 0 0 + 1 - 1
[ 5] (invite?:1) 1 0 + 0 1 0 - 1 - 1 1 + 1 + 1
[ 6] (invite?:0) + + - - - - - - - - + - - + -
[ 7] (invite?:1) 1 0 + 1 1 1 - 0 - 0 1 + 0 - 0
[ 8] (invite?:0) - - + + - - - - - - - - + - -
[ 9] (invite?:1) 1 0 - 1 0 1 - 0 - 0 1 - 1 + 1
[ 10] (invite?:1) 0 1 - 0 0 1 + 1 - 1 0 - 1 - 1
[ 11] (invite?:0) - - - - + + - + - - - - - + -
[ 12] (invite?:1) 0 1 - 1 1 1 - 0 + 1 1 - 0 + 0
[ 13] (invite?:0) + - - - - + + - - + - + + - -
[ 14] (invite?:1) 0 0 - 1 1 1 - 0 - 1 1 - 0 - 0
10 candidates left
round 2
[ 0] (invite?:0) - - - - - + + + - + - - - + -
[ 1] (invite?:0) - - - + + - + - - - + - + - -
[ 2] (invite?:0) - - - + - + - + + - - - - - -
[ 3] (invite?:0) - + + - - - - + + + - - + - +
[ 4] (invite?:0) - + - - - + - + - - - + + - +
[ 5] (invite?:1) + - + - + 0 - + - + + + + + +
[ 6] (invite?:0) + + - - - - - - - - + - - + -
[ 7] (invite?:0) + - + + + + - - - - + + - - -
[ 8] (invite?:0) - - + + - - - - - - - - + - -
[ 9] (invite?:0) + - - + - + - - - - + - + + +
[ 10] (invite?:0) - + - - - + + + - + - - + - +
[ 11] (invite?:0) - - - - + + - + - - - - - + -
[ 12] (invite?:0) - + - + + + - - + + + - - + -
[ 13] (invite?:0) + - - - - + + - - + - + + - -
[ 14] (invite?:0) - - - + + + - - - + + - - - -
1 candidates left
round 3
[ 0] (invite?:0) - - - - - + + + - + - - - + -
[ 1] (invite?:0) - - - + + - + - - - + - + - -
[ 2] (invite?:0) - - - + - + - + + - - - - - -
[ 3] (invite?:0) - + + - - - - + + + - - + - +
[ 4] (invite?:0) - + - - - + - + - - - + + - +
[ 5] (invite?:0) + - + - + - - + - + + + + + +
[ 6] (invite?:0) + + - - - - - - - - + - - + -
[ 7] (invite?:0) + - + + + + - - - - + + - - -
[ 8] (invite?:0) - - + + - - - - - - - - + - -
[ 9] (invite?:0) + - - + - + - - - - + - + + +
[ 10] (invite?:0) - + - - - + + + - + - - + - +
[ 11] (invite?:0) - - - - + + - + - - - - - + -
[ 12] (invite?:0) - + - + + + - - + + + - - + -
[ 13] (invite?:0) + - - - - + + - - + - + + - -
[ 14] (invite?:0) - - - + + + - - - + + - - - -
0 candidates left
guests to invite:
no body |
H********g
发帖数: 43926 | 5 100人里选5个，最常见的情况是一个都不请或者请97-100个 （朋友密度～0.1）。 |
H********g
发帖数: 43926 | 6 1000人的时候，朋友密度0.007，来大概700人，朋友密度0.008，来大概800人，朋友密
度0.009，来大概900人。
猜测当人多的时候，来的朋友总数是朋友密度的函数。 |
H********g
发帖数: 43926 | 7 5000人，朋友概率0.001（每个人大概5个朋友），通常请不到人。
5000人，朋友概率0.0013（每个人大概6.5个朋友），经常请不到人。
5000人，朋友概率0.0014（每个人大概7个朋友），经常请到3500人左右。
5000人，朋友概率0.0015（每个人大概7.5个朋友），经常请到4100人左右。
5000人，朋友概率0.002（每个人大概10个朋友），经常请到4800人左右。
5000人经常需要筛10圈。人少的时候通常3圈之内就筛完了。10000人说内存不够（perl
）。 |
H********g
发帖数: 43926 | 8 猜测最后剩下的人群大小是 （人均朋友数-5）的函数，而且人均朋友数必须大于5 才
能有比较大的概率能请到人。
perl
【在 H********g 的大作中提到】
: 5000人，朋友概率0.001（每个人大概5个朋友），通常请不到人。
: 5000人，朋友概率0.0013（每个人大概6.5个朋友），经常请不到人。
: 5000人，朋友概率0.0014（每个人大概7个朋友），经常请到3500人左右。
: 5000人，朋友概率0.0015（每个人大概7.5个朋友），经常请到4100人左右。
: 5000人，朋友概率0.002（每个人大概10个朋友），经常请到4800人左右。
: 5000人经常需要筛10圈。人少的时候通常3圈之内就筛完了。10000人说内存不够（perl
: ）。
|
H********g
发帖数: 43926 | 9 x个人里，每人平均有p个朋友，然后组织party，要求请到的人最少有y个朋友，最后请
到q个人。
这个问题是不是馄饨系统？ |
m********n
发帖数: 3812 | 10 the question never say how many guests to invite? |
H********g
发帖数: 43926 | 11 没，就是邀请符合条件的。所以根据我的程序模拟的结果，如果平均每人没有6个以上
的朋友，可能完全请不到人，如果平均每人7个以上的朋友，基本上人人都可以来。。
【在 m********n 的大作中提到】
: the question never say how many guests to invite?
|
