n*w
发帖数: 3393 | 1 N个人。编号0到N-1.
每次随机叫两个人猜拳（固定k次）。
过了一段时间，所有人的结果放在一个两维数组 R[N][2].
比如 R[3][0]= 8, R[3][1] = 7的话，表示第3人总共赢了8次，输了7次。
写程序把谁和谁猜过拳列出来。如果有多种可能，算出所有可能。 |
g**e
发帖数: 6127 | 2 这个是NP吧
【在 n*w 的大作中提到】
: N个人。编号0到N-1.
: 每次随机叫两个人猜拳（固定k次）。
: 过了一段时间，所有人的结果放在一个两维数组 R[N][2].
: 比如 R[3][0]= 8, R[3][1] = 7的话，表示第3人总共赢了8次，输了7次。
: 写程序把谁和谁猜过拳列出来。如果有多种可能，算出所有可能。
|
n*w
发帖数: 3393 | 3 应该是。这只是题目的一部分。
说是np是不是可以不用写程序？
【在 g**e 的大作中提到】
: 这个是NP吧
|
p***o
发帖数: 1252 | 4 A network flow problem on K_{N,N} less N edges.
A feasible solution can be found by running a max flow.
Almost impossible to explicitly list all possible solutions.
【在 n*w 的大作中提到】
: N个人。编号0到N-1.
: 每次随机叫两个人猜拳（固定k次）。
: 过了一段时间，所有人的结果放在一个两维数组 R[N][2].
: 比如 R[3][0]= 8, R[3][1] = 7的话，表示第3人总共赢了8次，输了7次。
: 写程序把谁和谁猜过拳列出来。如果有多种可能，算出所有可能。
|
p***o
发帖数: 1252 | 5 Never claim you know what is P and what is NP,
though by chance this problem is NP and finding
one solution is actually P.
【在 n*w 的大作中提到】
: 应该是。这只是题目的一部分。
: 说是np是不是可以不用写程序？
|
a****9
发帖数: 418 | 6 NP问题是指对该类问题验证一组解对不对需要多项式时间
而其求解过程则可能是多项式可能是指数时间
我猜你想说的是NP-hard.或者NP-complete
【在 g**e 的大作中提到】
: 这个是NP吧
|
n*w
发帖数: 3393 | 7 这类问题用functional language来解决是不是要容易点？
【在 p***o 的大作中提到】
: A network flow problem on K_{N,N} less N edges.
: A feasible solution can be found by running a max flow.
: Almost impossible to explicitly list all possible solutions.
|
p***o
发帖数: 1252 | 8 You either google the code or write the code in the most familiar
language. I don't see any advantage of functional languages when
solving network flow problems.
【在 n*w 的大作中提到】
: 这类问题用functional language来解决是不是要容易点？
|
